3 ms·
I’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
by srcreigh 3y ago
I’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.