46
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 8, 2010 at 20:23
  • $\begingroup$ 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. $\endgroup$
    – Evan
    Dec 8, 2010 at 20:31
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Dec 8, 2010 at 23:41

5 Answers 5

48
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Please let me know if I have got something wrong. $\endgroup$
    – Kaveh
    Dec 8, 2010 at 23:37
  • 1
    $\begingroup$ 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). $\endgroup$
    – Evan
    Dec 9, 2010 at 0:01
  • $\begingroup$ You are welcome, hopefully I haven't got it wrong. :) $\endgroup$
    – Kaveh
    Dec 9, 2010 at 0:15
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jun 25, 2012 at 2:14
19
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Also, TM programs aka transition tables are not really humanly readable. $\endgroup$
    – Raphael
    Dec 11, 2010 at 12:31
13
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.
$\endgroup$
5
  • $\begingroup$ 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). $\endgroup$
    – Evan
    Dec 9, 2010 at 0:03
  • $\begingroup$ Your reasons do not exclude register machines, for example. $\endgroup$
    – Raphael
    Dec 9, 2010 at 9:42
  • $\begingroup$ 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. $\endgroup$ Dec 9, 2010 at 11:15
  • 1
    $\begingroup$ 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 $\endgroup$
    – Rob
    Apr 9, 2011 at 8:03
  • $\begingroup$ I'm on the PL side, but pure lambda-calculus is not an obvious model of arithmetic computation (think of the predecessor function). In lambda-calculus you have less in the definition, but it takes more effort to understand the implications of the definition. $\endgroup$ Jan 8, 2015 at 13:31
0
$\begingroup$

It was the first to have impact and thus has been established, especially in complexity theory. This is a weak reason, but people work that way. We work on old open problems first instead of declaring new ones.

$\endgroup$
3
  • 8
    $\begingroup$ "We work on old open problems first instead of declaring new ones." <-- I think, if anything, the opposite is true, especially in a field where the old questions are extremely hard. There are relatively few people working in circuit complexity for instance (though perhaps there will be more now!). People need to work on problems they can solve in order to publish; this generates a constant flow of newly-declared solvable problems. $\endgroup$ Dec 9, 2010 at 2:56
  • $\begingroup$ I was a bit hasty in my wording there. I feel that oftentimes people rather stick to an established model than building a new one (and proving its basic properties) if there is no overwhelming reason for it. That feeling might be off, obviously. In particular, there are of course people who hunt models in the first place. $\endgroup$
    – Raphael
    Dec 9, 2010 at 9:40
  • $\begingroup$ Well, lambda calculus came first. But Turing showed that Turing machines model accurately the basics of humans doing computations; this was only done for lambda calculus when proving equivalence. Moreover, this equivalence is only true for first-order computation: cstheory.stackexchange.com/q/1117/989 - higher-order data does not really exist on paper. It doesn't even exist in computer's memories, but it can be perfectly simulated. $\endgroup$ Mar 24, 2014 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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