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?
$\begingroup$
$\endgroup$
4
-
10$\begingroup$ Yeah, but what you discovered is not that anything is wrong with Turing machines, or that there aren't countably many. Rather you discovered that humans are sloppy when they speak. There are countably many Turing machines once we fix the alphabet and the pick a reasonable set to represent states. By the way, humans have good reasons to be sloppy. $\endgroup$– Andrej BauerCommented Sep 22, 2013 at 16:49
-
6$\begingroup$ You can play this game ad nausam, as for most structures there is a proper class of isomorphic copies of them. We are not interested in any particular one, but rather in the strucutral properties that they all share. $\endgroup$– Andrej BauerCommented Sep 22, 2013 at 16:51
-
$\begingroup$ I agree with your opinion "humans are sloppy when they speak". In fact, my question is not about isomophism. As for a turing machine, choosing different state names and different tape symbols except for those in the input alphabet could actually produce isomophic machines, but the change of symbols in input alphabet will led to different machines from the perspective of language recognization, because the change of input alphabet will cause them to recognize different langages. So I feel the accurate phrase should be "there are countably many turing machines over a specific input alphabet. $\endgroup$– user10270Commented Sep 23, 2013 at 10:48
-
2$\begingroup$ Isn't that what I said? $\endgroup$– Andrej BauerCommented Sep 23, 2013 at 11:03
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
-
4$\begingroup$ +1 "up to isomorphism" should be the first thing that pops into anyone's mind when we read about uniqueness or the cardinality of a set of objects that are subject to encoding. $\endgroup$– G. BachCommented Sep 22, 2013 at 14:59
-
1$\begingroup$ If we are invoking ZFC, we can also say that the labels of the TMs have to be a number, and since a number is simply a set, we don't need isomorphisms to obtain countability. $\endgroup$ Commented Sep 23, 2013 at 20:15
$\begingroup$
$\endgroup$
Maybe a more straightforward illustration of the "up to isomorphism" thing: take a TM with 1 state and no transitions, then you can generate uncountably many TMs by assigning the state some subset of $\mathbb{N}$ as its label. Since you get uncountably many labels this way, you have uncountably many, obviously isomorphic TMs.
$\begingroup$
$\endgroup$
10
I believe neither of the other two answers are correct, they are falling prey to the same logical mistake : that there are
"uncountably many labels this way"
in the collection of subsets of $\mathbb{N}$.
However, only finite subsets should count. If the subset/language is finite, (or even finitely describable,) there are only countably many of them. See Wikipedia in particular: this sentence.
Theorem: The set of all finite subsets of the natural numbers is countable.
So
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.
is wrong.
The way I like to think of countable is
If every element of the set can be theoretically written down unambiguously in a large enough finite book, then the set is countable. This should be self evident:)
Examples:
The set of rationals. Every rational can be written down finitely.
The set of algebraic numbers. Every algebraic number can be described by writing out the equation along with a number and an ordering scheme to define which value is meant.(I.e $x^2=0$ has both $x=\sqrt{2}$ and $x=-\sqrt{2}$.)
So unless you are using languages that cannot be defined finitely and therefore shouldn't count, your set of Turing machines is still countable.
If anyone can think of a reason why a machine that fails this test of "finitely describable" should count in a set of Turing machines when it can't be built and run, I'd be happy to hear about it.
-
2$\begingroup$ What you are suggesting is essentially to change the definition of a TM such that the set of states and the alphabet are subsets of $\mathbb{N}$. Under this definition - indeed, there are countably many TMs, and this is what both answers above explain. While your definition is a legitimate definition, it is not the standard definition. Also, "finitely describable" is not the same thing as TM-recognizable. It greatly depends on your definition of "describable". $\endgroup$– ShaullCommented Sep 23, 2013 at 15:41
-
$\begingroup$ @Shaull I only used N because one of the other answers referred to it. This would work just as well with any "finitely describable" labels. My issue was the assumption that "anything" works as a label. Even if you count all every "{q,r}" and similar for finite length groups of letters and other symbols, that still ends up countable. Can you show me where a standard definition of a TM lets the alphabet be drawn from an uncountable set? $\endgroup$– ikeCommented Sep 23, 2013 at 15:58
-
2$\begingroup$ It doesn't matter what set the states are drawn from. In the standard definition, the state space can be any (finite) set. However, the collection of all finite sets is not a set (and in particular not a countable set). The phrase "finite length" you refer to is meaningless - we are not discussing the amount of descriptions of TMs (which is clearly countable, as a subset of e.g. $\{0,1\}^*$), but rather the amount of TMs, as mathematical objects. $\endgroup$– ShaullCommented Sep 23, 2013 at 16:09
-
$\begingroup$ @Shaull I found this formal definition which says:A Turing machine can be thought of as a infinite state machine sitting on an infinitely long tape containing symbols from some finite alphabet . $\endgroup$– ikeCommented Sep 23, 2013 at 16:16
-
1$\begingroup$ So we are simply talking about different things. A TM, as a mathematical object, can be defined using arbitrary sets, not only sets which we can write down or describe finitely. It is a nice property that every TM has an "isomorphic" TM that can be described. However, it is a property, not part of the definition. $\endgroup$– ShaullCommented Sep 23, 2013 at 17:05