I feel the notion \"there are countably many Turing machines\" is wrong. Suppose

Question

I feel the notion "there are countably many Turing machines" is wrong. Suppose there is a Turing machine whose input alphabet is {0}. If we replace the input alphabet {0} with {a} and replace every occurrence of "0" with "a" in the transition table, then we get another Turing machine. Obviously, these two machines are different beacause they recognize different languages, but using any one reasonable encoding sheme, they could be encoded into the same string. So claiming Turing machines are countable only by enumerating their encodings is wrong, because actually there isn't a bijection between Turing machines and their encodings. Is my opinion right?

Explanation / Answer

You are technically right. The correct phrasing should be that there are countably many TMs up to isomorphism of the tape alphabet and the state-space.

Indeed, if you say that a TM with states {q,r} is different than the same TM with states named {1,2}, then not only are TMs not a countable collection, they are not even a set in the ZFC axiom system. This follows from the fact that the collection of all sets is not a set itself.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.