This may be a bit vague, as I don't remember all the details.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Uncountably Many Turing Machines

**Physics Forums | Science Articles, Homework Help, Discussion**