How large is the set of all Turing machines?

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?

Solution 1:

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.

Solution 2:

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

Solution 3:

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.

Solution 4:

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)¹ 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").}