15
$\begingroup$

How large is the set of all Turing machines? I am confident it is infinitely large, but what kind of infinitely large is its size?

$\endgroup$
  • 1
    $\begingroup$ As noted in answers and comments to answers, the definition of Turing machine is in terms of some finite sets (of symbols and states notably). But the class of finite sets (and even that of singleton sets) is a proper class, so it cannot be measured by any cardinal. If you want to talk of a set of Turing machines, you need to rein in the trivial freedom of choosing these base sets, for instance by requiring them to be initial segments of the natural numbers. Only then does the question make sense. $\endgroup$ – Marc van Leeuwen Mar 7 '15 at 13:47
  • $\begingroup$ @Marc That's a good point. I asked this question because I'm trying to solve a problem (specifically, this one), and in that problem, I am primarily interested in Turing machines that process strings encoding pairs of integers. $\endgroup$ – Kevin - Reinstate Monica Mar 7 '15 at 20:01
25
$\begingroup$

By an informal argument, Turing machines roughly correspond to programs written in some programming language. Each program is a finite string in ASCII or unicode or binary (or another finite alphabet of some kind).

We might imagine writing a naive program that outputs all possible strings in lexographical order, running the compiler on each one, and throwing it out if there's an error. This program will ultimately list out every program (albeit, "hello world" would take a very long time to produce). Thus, we have a program which enumerates all programs. The set of all turing machines is countable.

$\endgroup$
  • 1
    $\begingroup$ Are we sure that all programs are finite? Turing machines were conceived as having have infinite length tape*, and any program approximating a Turing machine needs to incorporate input as well - which can easily be infinite in the case of stream processing. *(1948 essay, "Intelligent Machinery", Turing) $\endgroup$ – Gustav Bertram Mar 6 '15 at 11:13
  • 9
    $\begingroup$ @GustavBertram: Yes. Depending on your perspective, Turing machines may either always start with an empty tape or take a tape as input, but in the latter case the initial state of the tape is finite. You could presumably extend to allow infinite tapes as long as the initial contents are computable (i.e. representable by another Turing machine that starts with an empty tape and produces the initial tape on demand) but allowing an arbitrary infinite tape has no meaningful interpretation as a model of computation. $\endgroup$ – R.. Mar 6 '15 at 11:36
  • 1
    $\begingroup$ @GustavBertram Turing machines are finite in the sense that they have a finite number of states and use a finite alphabet, which means there is a finite number of possible transition functions. Transition functions are, basically, programs and they are what matters. $\endgroup$ – Bakuriu Mar 6 '15 at 13:56
  • $\begingroup$ Have you read Turing's original paper? One of the main conclusions is that your hypothetical "naive program" cannot exist: there is no Turing machine that can distinguish between "circle-free" (i.e. valid) machines (programs) and non-valid programs. But your program is unnecessary anyway: the fact that programs are finite strings in a finite alphabet means they are mappable to integers, and therefore countable. $\endgroup$ – Kyle Strand Mar 6 '15 at 18:35
  • 2
    $\begingroup$ @KyleStrand I think Tac-Tics' argument is that the compiler takes source code as input and outputs the machine that executes the same code. The programs that are thrown away are those with syntax errors, missing declarations, etc. (the kind of errors a compiler would catch anyway). $\endgroup$ – Davidmh Mar 6 '15 at 21:16
21
$\begingroup$

Have you seen that you can encode Turing machines by natural numbers? It is done on the way to showing there is a universal Turing machine. otherwise, each machine is a finite string of symbols from some alphabet

$\endgroup$
8
$\begingroup$

Tac-Tics's answer is almost correct, but the "naive program" argument is unnecessary and possibly incorrect (as per my comment).

The observation that Turing machines can be described by finite strings in a finite alphabet is sufficient: by mapping the letters of the alphabet to integers in some base (e.g. binary or, as Turing does, decimal without the use of digits 8 and 9), you can map all programs to integers. Thus the set of all (valid or non-valid)1 machines is mappable to a subset of the integers; thus both the set of all machines and the (smaller) set of all valid machines are countable.

1: By "valid," I mean either Turing's "circle-free" concept or the later equivalent-but-inverted "halting" concept (introduced when Turing's work was reframed as the "halting problem").

$\endgroup$
  • $\begingroup$ I think your answer and Tac-Tics's answer may actually be identical. Here's why. When you cite "the observation that Turing machines can be described by finite strings in a finite alphabet," I'm not quite sure what you mean, but the context suggests that you're positing an injective map from the set $M$ of Turing machines to the set $C^*$ of finite strings over some finite alphabet $C$. Many methods of constructing such a map will produce one whose range $P$ is a proper subset of $C^*$. $\endgroup$ – Vectornaut Mar 7 '15 at 5:03
  • $\begingroup$ Tac-Tics is talking about the same map, but thinking of it as a bijective map from $P$ to $M$. It's well known that you can arrange for $P$ to be a computable subset of $C^*$. Tac-Tics's "compiler" is a machine that tests whether a given element of $C^*$ is in $P$. $\endgroup$ – Vectornaut Mar 7 '15 at 5:03
  • $\begingroup$ @Vectornaut Agreed. My point is that you don't actually need to hypothesize a decision machine to evaluate the mapping in order to recognize that the set of machine-descriptions is a subset of the set of strings in the language. $\endgroup$ – Kyle Strand Mar 7 '15 at 5:06
  • $\begingroup$ It's true that you don't need one, but you might want one. As Tac-Tics alludes, the process of verifying that an element of $C^*$ lies in $P$ and then producing the corresponding Turing machine is very familiar to many people: it's the process of compiling a program. The reverse process, decompiling, is much more esoteric. So, I think the decision to focus on the compiling direction is very understandable from a pedagogical point of view. $\endgroup$ – Vectornaut Mar 7 '15 at 5:12
  • $\begingroup$ @Vectornaut Fair enough, but Tac-Tic's answer is phrased so as to make it seem that the compiling process is part of the countability argument. It is not, or at least ought not be. $\endgroup$ – Kyle Strand Mar 7 '15 at 8:42
8
$\begingroup$

It depends on how you define "distinct" in terms of turing machines. In general, two (one-tape) turing machines are not "distinct" if there is a component-wise bijection that goes from one's 7-tuple to the other's 7-tuple.(See http://en.wikipedia.org/wiki/Turing_machine#Formal_definition for the 7-tuple I am referring.). This leads to a countable number of turing machines. If instead if "distinct" is defined in a way that the 7-tuples have to be identical to be not "distinct", then there are uncountably many turing machines. In this case, there would not be a "set" of all turing machines, instead we would have a "class" of all turing machines.

$\endgroup$
  • 7
    $\begingroup$ The only way you could get an uncountable infinity of Turing machines is if you allow states or symbols to be chosen from an uncountable infinite set. If the set of tape symbols and the set of states are each required to be a subset of a countable infinite set of possible choices, then the set of possible Turing machines will also be a countable infinite set. $\endgroup$ – kasperd Mar 6 '15 at 8:35
  • $\begingroup$ @kasperd This is true. But, since any Turing machine has a finite number of states, people don't tend to be too fussy about what the "names" of those states are. So I think this answer makes a helpful point. $\endgroup$ – David Richerby Mar 6 '15 at 9:32
  • 5
    $\begingroup$ @David If names can be anything, there would still not be an uncountable set of all Turing machines, but rather a class of all Turing machines (larger than any set). $\endgroup$ – gmatht Mar 6 '15 at 13:41
  • $\begingroup$ @gmatht, I do believe it would be a class, not a set, but it would still be uncountable(in the sense that you cannot create a bijection from this class to the natural numbers) $\endgroup$ – SE318 Mar 6 '15 at 14:32
  • $\begingroup$ @gmatht's comment is nontrivial; please add it to the answer, SE318! $\endgroup$ – Kyle Strand Mar 6 '15 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.