<p>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.</p>

CC BY-SA 2.5
2010-12-11T12:31:34.513Z
Also, TM programs aka transition tables are not really humanly readable.
Raphael
CC BY-SA 2.5
2010-12-09T13:10:29.083Z
2010-12-09T15:17:49.167Z
2010-12-09T15:17:49.167Z
Martin Berger
<p>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:</p>

<ul>
<li>they are easy to describe formally and have simple operational semantics;</li>
<li>it’s easy to give a concrete definition of their time and space complexity;</li>
<li>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.</li>
</ul>

CC BY-SA 2.5
2010-12-09T00:03:59.353Z
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
CC BY-SA 2.5
2010-12-09T09:42:20.997Z
Your reasons do not exclude register machines, for example.
Raphael
CC BY-SA 2.5
2010-12-09T11:15:04.553Z
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
CC BY-SA 3.0
2011-04-09T08:03:22.870Z
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 http://worrydream.com/AlligatorEggs/
Rob
CC BY-SA 3.0
2015-01-08T13:31:21.037Z
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.
Blaisorblade
CC BY-SA 2.5
2010-12-08T23:44:59.520Z
2010-12-08T23:44:59.520Z
Antonio E. Porreca
<p>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.</p>

CC BY-SA 2.5
2010-12-08T20:26:15.967Z
2010-12-08T20:26:15.967Z
Tsuyoshi Ito
<p>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.</p>

CC BY-SA 3.0
2014-03-24T14:55:59.197Z
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: http://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.
Blaisorblade
CC BY-SA 2.5
2010-12-09T02:56:54.417Z
"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.
Aaron Sterling
CC BY-SA 2.5
2010-12-09T09:40:48.877Z
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.
Raphael
CC BY-SA 2.5
2010-12-08T23:35:53.963Z
2010-12-08T23:35:53.963Z
Raphael
<p>This seems to be true in the context of (some areas of) computer science but not generally.</p>
<p>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 <em>the</em> model for effective computation. The equivalences between different models is proven later (I think by Kleene).</p>
<p>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 <span class="math-container">$\lambda$</span>-calculus and <span class="math-container">$\mu$</span>-recursive functions.</p>
<p>On the other hand, <span class="math-container">$\mu$</span>-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 &quot;Metamathematics&quot; was very influential for this development. Also <span class="math-container">$\lambda$</span>-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 href="http://www.newton.ac.uk/programmes/SAS/" rel="noreferrer">a different view</a>. Also see these papers by Viggo Stoltenberg-Hansen and John V. Tucker <a href="http://portal.acm.org/citation.cfm?id=1024924" rel="noreferrer">I</a>,<a href="http://portal.acm.org/citation.cfm?id=309999.310039" rel="noreferrer">II</a>.)</p>
<h3>Some resources for further reading:</h3>
<p><a href="http://people.cs.uchicago.edu/%7Esoare/" rel="noreferrer">Robert I. Soare</a> 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.</p>
<p>Another good resource is Neil Immerman's <a href="http://plato.stanford.edu/entries/computability/" rel="noreferrer">computability</a> article on SEP, see also <a href="http://plato.stanford.edu/entries/church-turing/" rel="noreferrer">Church-Turing Thesis</a> article by B. Jack Copeland.</p>
<p>Godel's <a href="http://books.google.com/books?id=5ya4A0w62skC" rel="noreferrer">collected works</a> contains <em>lots</em> of information on his views. Specially introductions to his articles are extremely well-written.</p>
<p>Kleene's &quot;<a href="http://books.google.com/books?id=HZAjPwAACAAJ" rel="noreferrer">Metamathematics</a>&quot; is a very nice book.</p>
<p>Finally, if you are not still satisfied check the archives of the <a href="http://cs.nyu.edu/pipermail/fom/" rel="noreferrer">FOM mailing list</a>, and if you cannot find an answer in the archive post a an email to the mailing list.</p>

CC BY-SA 2.5
2010-12-08T23:37:42.810Z
Please let me know if I have got something wrong.
Kaveh
CC BY-SA 2.5
2010-12-09T00:01:36.847Z
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
CC BY-SA 2.5
2010-12-09T00:15:06.303Z
You are welcome, hopefully I haven't got it wrong. :)
Kaveh
CC BY-SA 3.0
2012-06-25T02:14:06.910Z
There was [a recent talk](http://www.newton.ac.uk/programmes/SAS/seminars/032216301.html) 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
CC BY-SA 2.5
2010-12-08T23:09:28.870Z
2010-12-09T16:57:38.950Z
2020-06-17T09:38:08.363Z
Kaveh
<p>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).</p>

<p>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?</p>

CC BY-SA 2.5
2010-12-08T20:23:14.257Z
while they are not directly on the same topic, the questions http://cstheory.stackexchange.com/questions/625/relationship-between-turing-machine-and-lambda-calculus and http://cstheory.stackexchange.com/questions/1117/realizability-theory-difference-in-power-between-lambda-calculus-and-turing-mach explore the relationship between TMs and the $\lambda$-calculus, and have some historical elements.
Suresh Venkat
CC BY-SA 2.5
2010-12-08T20:31:47.523Z
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
CC BY-SA 2.5
2010-12-08T23:41:37.203Z
Actually there are models which are (arguably) closer to real computers, see [this question](http://cstheory.stackexchange.com/questions/2656/which-model-of-computation-is-the-best). Generally the *best* model depends on the *needs* and they are different from one area to another.
Kaveh
<reference-request><soft-question><computability><turing-machines><ho.history-overview>
Historical reasons for adoption of Turing Machine as primary model of computation.
Evan
# Historical reasons for adoption of Turing Machine as primary model of computation.

(Asked by: username_0 on 2010-12-08)

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?

**Tags:** reference-request, soft-question, computability, turing-machines, ho.history-overview

> **Comments:**
> **username_1**: while they are not directly on the same topic, the questions http://cstheory.stackexchange.com/questions/625/relationship-between-turing-machine-and-lambda-calculus and http://cstheory.stackexchange.com/questions/1117/realizability-theory-difference-in-power-between-lambda-calculus-and-turing-mach explore the relationship between TMs and the $\lambda$-calculus, and have some historical elements.  
> **username_0**: 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.  
> **username_2**: Actually there are models which are (arguably) closer to real computers, see [this question](http://cstheory.stackexchange.com/questions/2656/which-model-of-computation-is-the-best). Generally the *best* model depends on the *needs* and they are different from one area to another.  

---

## 5 answers

### Answer by username_2 on 2010-12-08. Score: 48 | Accepted answer

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](http://www.newton.ac.uk/programmes/SAS/). Also see these papers by Viggo Stoltenberg-Hansen and John V. Tucker [I](http://portal.acm.org/citation.cfm?id=1024924),[II](http://portal.acm.org/citation.cfm?id=309999.310039).)

### Some resources for further reading:

[username_6ert I. Soare](http://people.cs.uchicago.edu/%7Esoare/) 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](http://plato.stanford.edu/entries/computability/) article on SEP, see also [Church-Turing Thesis](http://plato.stanford.edu/entries/church-turing/) article by B. Jack Copeland.

Godel's [collected works](http://books.google.com/books?id=5ya4A0w62skC) contains *lots* of information on his views. Specially introductions to his articles are extremely well-written.

Kleene's "[Metamathematics](http://books.google.com/books?id=HZAjPwAACAAJ)" is a very nice book.

Finally, if you are not still satisfied check the archives of the [FOM mailing list](http://cs.nyu.edu/pipermail/fom/), and if you cannot find an answer in the archive post a an email to the mailing list.

> **Comments:**
> **username_2**: Please let me know if I have got something wrong.  
> **username_0**: 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).  
> **username_2**: You are welcome, hopefully I haven't got it wrong. :)  
> **username_2**: There was [a recent talk](http://www.newton.ac.uk/programmes/SAS/seminars/032216301.html) by username_6ert 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.  

---

### Answer by username_3 on 2010-12-09. Score: 20

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.

> **Comments:**
> **username_4**: Also, TM programs aka transition tables are not really humanly readable.  

---

### Answer by username_5 on 2010-12-08. Score: 13

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.

> **Comments:**
> **username_0**: 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).  
> **username_4**: Your reasons do not exclude register machines, for example.  
> **username_5**: 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.  
> **username_6**: 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 http://worrydream.com/AlligatorEggs/  
> **username_7**: 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.  

---

### Answer by username_8 on 2010-12-08. Score: 13

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.


---

### Answer by username_4 on 2010-12-08. Score: 0

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.

> **Comments:**
> **username_9**: "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.  
> **username_4**: 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.  
> **username_7**: 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: http://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.  

---

