Uncountably Many Turing Machines

[Dragonfall]

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 $$2^{\aleph_0}$$ ways of listing the TMs. On the face of it there must therefore be $$2^{\aleph_0}$$ 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.

 

[Dragonfall]

So why are there not uncountably many TMs?

 

[Coin]

So why are there not uncountably many TMs?

A turing machine has a finite description. There is a canonical way of writing that description down in terms of sets of transitions, states, and tape symbols; failing that, any turing machine can in principle be described using english words.

The set of all strings-- that is, anything that you could type on a keyboard, ever-- is countable. You can order the set of all possible strings alphabetically, and there, you have a counting. The set of [all strings uniquely specifying turing machines] is a subset of all strings, and obviously there is a one-to-one map between a turing machine and its specification. So an ordering of the strings gives us an ordering of the turing machines.

I don't think the halting machine M, or anything else really, "depends on" the ordering of this counting. The point of the ordering is just that it exists. It is a reference point. It allows us to say, we can order the turing machines, and at some finite index in this ordering we will find our halting machine M. We can choose different orderings, and although there are uncountably-many orderings this does not matter because all orderings contain the same set of machines and all are the same in the only important respect: they are a countable ordering.

Now perhaps what you're saying is this: M "depends on" on a particular ordering. There are uncountably many orderings. Therefore, there should be uncountably many Ms, because you should need a different M for each ordering. I'm not sure if this is, strictly speaking, correct reasoning; but it sounds reasonable enough.

However, even if so, what you have just done is proved there are uncountably many Ms. This does not prove there uncountably many turing machines-- because M is impossible! M does not exist as a turing machine with a finite description-- no M does, regardless of ordering. This is the entire point of assuming M's existence in the first place-- the intent of the proof is, we want to show that assuming M leads to a contradiction. Therefore, if you have indeed found a contradiction from assuming M's existence, then all this means is that you have completed the proof!

 

[Dragonfall]

Now perhaps what you're saying is this: M "depends on" on a particular ordering. There are uncountably many orderings. Therefore, there should be uncountably many Ms, because you should need a different M for each ordering. I'm not sure if this is, strictly speaking, correct reasoning; but it sounds reasonable enough.

That's what I'm having trouble with. There seems to be something wrong with the argument but I can't quite find it.

 

[Coin]

That's what I'm having trouble with. There seems to be something wrong with the argument but I can't quite find it.

Well:

1. It's not that there's something wrong with it, it's just that it doesn't follow. You say that M "depends on the listing". Why does M depend on the listing? You haven't proven this, you haven't demonstrated it. For all I know it's wrong. This is a proof, so nothing's true until you prove it...

2. Again, even if the argument is correct, it doesn't tell us anything about turing machines. M is not a turing machine! The very result of the proof is to demonstrate that no turing machine with M's characteristics exists.