- #1
Dragonfall
- 1,030
- 4
This may be a bit vague, as I don't remember all the details.
When proving Turing's halting problem, at some point you will say something along the lines of, "given a list of all Turing Machines, assume that there exists a Turing Machine M which decides whether machine A halts on input B".
The problem here is that M depends on the listing. There are [tex]2^{\aleph_0}[/tex] ways of listing the TMs. On the face of it there must therefore be [tex]2^{\aleph_0}[/tex] TMs. I guess hidden in the above statement is that not all permutations give unique TMs (in fact, most don't), but it is not obvious, and was never shown to me.
When proving Turing's halting problem, at some point you will say something along the lines of, "given a list of all Turing Machines, assume that there exists a Turing Machine M which decides whether machine A halts on input B".
The problem here is that M depends on the listing. There are [tex]2^{\aleph_0}[/tex] ways of listing the TMs. On the face of it there must therefore be [tex]2^{\aleph_0}[/tex] TMs. I guess hidden in the above statement is that not all permutations give unique TMs (in fact, most don't), but it is not obvious, and was never shown to me.
Last edited: