# Historical reasons for adoption of Turing Machine as primary model of computation.

It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more widely-used than other theoretically equivalent (to my knowledge) models, for instance Kleene's μ-Recursion or the Lambda Calculus (I understand that the former didn't appear until later on and the latter wasn't originally designed specifically as a model of computation, but it shows that alternatives have existed from the start).

All I can think of is that the TM model more closely represents the computers we actually have than its alternatives. Is this the only reason?

-
while they are not directly on the same topic, the questions cstheory.stackexchange.com/questions/625/… and cstheory.stackexchange.com/questions/1117/… explore the relationship between TMs and the $\lambda$-calculus, and have some historical elements. –  Suresh Venkat Dec 8 '10 at 20:23
Yes, I saw those. I understand fairly well the literal histories of the various theories, but I'm more interested in the developments over time that led to the current "preferences" in the field, if you will. –  Evan Dec 8 '10 at 20:31
Actually there are models which are (arguably) closer to real computers, see this question. Generally the best model depends on the needs and they are different from one area to another. –  Kaveh Dec 8 '10 at 23:41

This seems to be true in the context of (some areas of) computer science but not generally.

One reasons has to do with the Church's Thesis. The main reason is that some experts like Godel didn't think that the arguments that previous/other models of computation capture exactly the intuitive concept of computation were convincing. There are various arguments, Church had some, but they did not convince Godel. On the other hand Turing's analysis was convincing for Godel so it was accepted as the model for effective computation. The equivalences between different models is proven later (I think by Kleene).

The second reason is technical and a later development related to the study of complexity theory. Defining the complexity measures like time, space, and nondeterminism seems to be easier using Turing machines than other models like $\lambda$-calculus and $\mu$-recursive functions.

On the other hand, $\mu$-recursive functions were and are still used as the main way of defining computability in logic and computability theory books. They are easier to work with when one only cares about effectiveness and not about complexity. Kleene's book "Metamathematics" was very influential for this development. Also $\lambda$-calculus seems to be more common in CMU/European style computer science like programming languages and type theory. Some authors prefer the RAM and Register Machine models. (It seems to me that for some reason Americans adopted Turing's semantic model and Europeans adopted Church's syntactic model, Chruch was American and Turing was British. This a personal opinion/observation and others have a different view. Also see these papers by Viggo Stoltenberg-Hansen and John V. Tucker I,II.)

### Some resources for further reading:

Robert I. Soare has a number of articles on the history of these developments, I personally like the one in the Handbook of Computability Theory. you can find more by checking the references in that paper.

Another good resource is Neil Immerman's computability article on SEP, see also Church-Turing Thesis article by B. Jack Copeland.

Godel's collected works contains lots of information on his views. Specially introductions to his articles are extremely well-written.

Kleene's "Metamathematics" is a very nice book.

Finally, if you are not still satisfied check the archives of the FOM mailing list, and if you cannot find an answer in the archive post a an email to the mailing list.

-
Please let me know if I have got something wrong. –  Kaveh Dec 8 '10 at 23:37
Wow, this is great info. Thanks for the resources, I'll check them out (I was planning to read Metamathematics -- I'll bump it up the queue). –  Evan Dec 9 '10 at 0:01
You are welcome, hopefully I haven't got it wrong. :) –  Kaveh Dec 9 '10 at 0:15
There was a recent talk by Robert Soare at INI. As I understand it, the main reason for changing to Turing model and computability from recursive functions and recursion theory for him is the following: it is hard to understand and work in recursion theory to the point where no one was understanding what was going on except a few, the change to computability made it much easier to understand and revived the area. –  Kaveh Jun 25 '12 at 2:14

I would like to weaken the claim that TMs are the primary model of computation, or at least point towards another dimension of the question. Clearly TMs are dominant in the more complexity- and algorithmically-oriented parts of computer science, but in programming language theory and practise, they are not particularly dominant. There are various reasons for this, but maybe the most important is that TMs or programs running on TMs (unlike e.g lambda-calculi or process-calculi) are not constructed in an algebraic manner. This makes it difficult to develop type-theories, which have been the mainstay of programming language theory.

-
Also, TM programs aka transition tables are not really humanly readable. –  Raphael Dec 11 '10 at 12:31

One of the nice things about Turing machines is that they work on strings instead of natural numbers or lambda terms, because the input and the output of many problems can be naturally formulated as strings. I do not know if this counts as a “historical” reason or not, though.

-

Beside the fact that Turing machines are a convincing model of pen-and-paper computation (the “intuitive notion of computation”), I think they possess a series of features that are often useful, particularly when proving theorems about them:

• they are easy to describe formally and have simple operational semantics;
• it’s easy to give a concrete definition of their time and space complexity;
• more realistic (and complex) models of electronic computers, such as random access machines, can be simulated by TMs with a polynomial overhead, and vice versa.
-
Sometimes the facility of description seems to hinder the usefulness of TMs, since descriptions can quickly devolve into plain-English explanations if you're not careful (at least, if I'm not careful... Admittedly I'm a novice). –  Evan Dec 9 '10 at 0:03
Your reasons do not exclude register machines, for example. –  Raphael Dec 9 '10 at 9:42
Well, that depends on the precise notion of “register machine” you consider. For instance, those having only increment, decrement and jump operations cannot simulate TMs in polynomial time. –  Antonio E. Porreca Dec 9 '10 at 11:15
I suspect that TMs are more intuitive only because they are presented as machines, rather than as abstract mathematical operations. If $\lambda$-calculus was presented as a "term rewriting" machine, then it would be (more) intuitive. Note the Alligator Eggs childrens' game for teaching them $\lambda$-calculus worrydream.com/AlligatorEggs –  Rob Apr 9 '11 at 8:03