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.
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.
This was a great read, if you want a mathematical take on it, and some generalization too. https://arxiv.org/abs/math/0305282v1
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.
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.