Where does this argument showing there are uncountably many TMs fail?

Question

This argument comes up once every while on Lambda the Ultimate. I want to know where the flaw is.

Take a countable number of TMs all generating different bitstreams. Construct a Cantor TM which runs every nth TM upto the nth bit and outputs the reversed bit.

Now I have established there are uncountably many TMs.

(The argument is that every bitstream is a unique real in the set [0,1]. Since every TM can be seen to be represented by that real, we can use Cantor's construction to prove that there are uncountably many TMs.)

Where does it go wrong?

Answer 1

There are uncountably many Turing machines, if you allow them to use oracles (which are real numbers, really).

But if you disallow that, then the only way that this process gives back a Turing machine is if the enumeration itself is computable. So what you have shown is that the set of Turing machines is not computable (albeit it is recursively enumerable, but that is not enough).

This "liberal assumption" is the only assumption that you make which does not imply "most infinite sets related mathematics is inconsistent", by Occam razor arguments alone it shows that the assumption might be a bit too liberal after all.

As for the suggestion that we make an enumeration for enumerating the rational numbers, sure, you just get (more or less) an irrational number. Showing that one countable set doesn't include all the Turing machines is not a contradiction.

Answer 2

There are uncountably many countable sets of Turing machines, and only countably many of these can be enumerated by a Turing machine (since there are, in fact, only countably many Turing machines). So for most such subsets, your Cantor TM can't exist.

Answer 3

There are only a countable number of constructible reals. The Cantor TM only proves that any enumeration can be extended with an extra element. Since it didn't start of with a bijection between the natural numbers and the reals, the construction doesn't prove that that bijection doesn't exist.

(I answered my own question by summarizing the answers.)

Answer 4

There are a couple of issues here. To begin, I'll assume that by a Turing Machine we mean a Turing Machine with unary input alphabet $\{ \mathsf{1} \}$, and tape alphabet $\{ \mathsf{1} , \mathsf{-} \}$, where $\mathsf{-}$ is the blank symbol. The natural number $k$ is inputted into such a Turing Machine in the usual unary manner: $\overbrace{\mathsf{1}\cdots\mathsf{1}}^{k\text{ times}}$.

To view such a Turing Machine as generating a bitstream, we'll say that the $k$th bit generated by $M_n$ is $1$, if $M_n$ halts reading a $\mathsf{1}$ on input $k$, and is $0$ if $M_n$ halts reading a blank on that same input.

Now take your enumeration $\{ M_0, M_1 , \ldots \}$ of all these Turing machines, and devise a Turing machine $M_*$ so that on input $k$ it outputs the reverse of whatever $M_k$ outputs on input $k$. Now, if $M_* = M_k$ for some $k$, then we have the following

• if the $k$th bit outputted by $M_k$ is $1$, then the $k$th bit outputted by $M_*$ is $1$, and so by our description the $k$th bit outputted by $M_k$ is $0$, and similarly,
• if the $k$th bit outputted by $M_k$ if $0$, then the $k$th bit outputted by $M_k$ is $1$.

But there is a third possibility that hasn't even been counted upon, and that is that $M_k$ may not halt on input $k$. If $M_k$ does not halt on input $k$, then we say nothing of what $M_*$ does. In fact, when we say that a TM $M$ uses the output of another TM $M^\prime$ to determine its output, we generally mean that $M$ simulates $M^\prime$ on the desired input (or that $M^\prime$ is a "subroutine" of $M$). If $M_k$ does not halt on input $k$, then $M_*$ will also not halt on this input. Notice that we've alleviated the supposed contradiction to the countability of TMs quite nicely.

But, you may ask, what if we assume that our enumeration is set up so that for each $k$ the TM $M_k$ halts on input $k$? Well, you're not going to get all the TMs in this manner, because there are TMs that do not halt on any input (and so cannot be part of this enumeration). Also, for each $k$ there would be infinitely many TMs that halt only on input $k$. So this route is a bit of a non-starter.

But let's try to be even more generous and suppose that $\{ M_0, M_1 , \ldots \}$ is an enumeration of all TMs that halt on all inputs. Now $M_*$ also halts on all inputs, and we appear to have arrived at a contradiction. But to what?

Well, we now get into a matter that has been overlooked. In order for $M_*$ to simulate any of the infinitely many $M_k$ it must be that the enumeration is given to $M_*$ in such a way that it can algorithmically convert the input $k$ into a description of $M_k$. So our beginning enumeration is not arbitrary, but must be computable. The contradiction we run into now is that there is no computable enumeration of all TMs which halt on all inputs.

Answer 5

There are several problems with this argument. If you want to use contradiction to prove the set of all TM's is uncountable you must first assume there is an enumeration of all TM's. This "proof" only assumes we have a countably infinite set of TM's with unique output. There are a lot of such sets. One such is the set of TM's that output the binary representation of an unique rational number. Using a diagonal argument to prove there is a TM that outputs the representation of an irrational number proves nothing about the size of this set of rational output TM's.

The argument fails even if we assume we have an enumeration of all TM's. To make things simpler, assume we have an enumeration of all busy beavers (BB) and want to prove there is an uncountable number of BB's. There are $((4*(n+1))^{2n}$ possible 2 symbol BB's with $n$ states. We can encode all $n$ states of a specific machine into a natural number. Once we specify an encoding we can enumerate all the valid numbers that encode a BB. This gives us an enumeration of all BB's.

The argument says to construct a BB that runs the BB encoded as $n$ for $n$ steps and reverses the output. A BB has to output something on every step. If the BB halts before step $n$ we can assume it outputs $0$ on step $n$.

This is the second major flaw in this argument. There is no way to construct such a BB. We are assuming on step $n$ this BB outputs the opposite of the $nth$ BB. Obviously, no BB can emulate the first $n$ steps of another BB in less than $n$ steps. This magical BB would have to know in advance what to output on step $n$.

The argument still fails if we try to construct a BB that outputs the anti-diagonal. We can construct such a BB for the first $n$ machines. A BB that outputs the anti-diagonal for all BB's would have to have an infinite number of states. By definition, a BB can only have a finite number of states.