4 ms·
I would probably refer to this as "Cantor's diagonalization" to avoid the ambiguity with "matrix diagonalization" using the matrix eigendecomposition.
by ninepoints 3y ago
I would probably refer to this as "Cantor's diagonalization" to avoid the ambiguity with "matrix diagonalization" using the matrix eigendecomposition.
- srcreigh 3y agoI’d rather not call it diagonalization at all. Nothing about turings construction enumerates many machines and builds a new machine to flip some aspect of the other machines on the list. It’s more like the liar paradox akin to Gödel first incompleteness theorem.
- doomrobo 3y agoIt turns out that these are all kind of the same, the Liar's Paradox, Russell's Paradox, the Halting Problem, etc. And indeed the they rely on a "diagonal map" i.e., a map x -> (x, x) in the construction. This was a great read, if you want a mathematical take on it, and some generalization too. https://arxiv.org/abs/math/0305282v1 https://arxiv.org/abs/math/0305282v1
- hgsgm 3y agoSure, if you create a larger object it can contain two smaller objects. But that construction is so general that it contains all proofs of the from "There exists X that does not have not property Y" that proceed by constructing something that lacks the property, and stuffs the proof into the diagram.
- abdullahkhalids 3y agoIts not fully general. Many different types of undecidability proofs are basically proofs by diagonalization, but not all are. See some counter examples: https://mathoverflow.net/q/454105 https://mathoverflow.net/q/454105
- srcreigh 3y ago“I genuinely don’t have an operational definition for what it means to use diagonalization” - Terry Tao
- joaogui1 3y agoSo you are listing all TMs + inputs and creating a machine which does the opposite (from a halting perspective), which is like when Cantor lists the reals and creates a new one that has the opposite digit from the other reals
- hgsgm 3y agoNo, it's not like that at all. It's just an algorithm that contradicts itself, like Russell's Paradox.
- cvoss 3y agoBroaden your view of the Halting undecidability proof. Let T_i enumerate all Turing machines. Let E be a function that encodes a Turing machine as a tape. Suppose Halting is decidable, and let H_i,j be the table of bits such that H_i,j is 1 iff T_i halts on input tape E(T_j). There is some x such that H_x,j = !H_j,j for all j (we can construct/find such a machine by hypothesis). Therein lies the diagonalization, you see? We just identified a row such that the bit in column j differs from the jth bit on the the diagonal. The paradox you reference is what happens at bit H_x,x. But, in the bigger context, this argument proceeded by diagonalization.
- hgsgm 3y agoI tried to comment that on the article. But they use Disqus which is hostile to people making comments.
- xelxebar 3y agoHrm... Ambiguity only arises out of context. IMHO, there is ample enough context here to disambiguate, just as you seem to have successfully done. Matrix diagonalization and what you're calling Cantor's diagonalization can both be seen as instantiations of a more general diagonalization process. This latter process seems to be what the article is obliquely pointing at, cf my top-level comment for a video that introduces those details.
- housecarpenter 3y agoThe term I've seen most often is "diagonal argument".