<p>you mention PDAs specifically. note a Turing machine is equivalent to a PDA with two stacks. PDAs original rationale seems to have been closely related to the development of "language theory" ala chomsky.</p>

<p>see eg <a href="http://books.google.com/books/about/Structure_of_language_and_its_mathematic.html" rel="nofollow">Syntactic Analysis and the Pushdown Store," Proceedings of Symposia in Applied Mathematics (Vol. 12). Providence, RI: American Mathematical Society, 1961  </a></p>

<p>this is has one of the earliest references Ive seen by Oettinger, "Automatic syntactic analysis and the pushdown store" p104, dont know if there are earlier refs to the PDA.</p>

<p>it took many years of study of all the interelated automata to start to devise a unifying theory (still being constructed). the Turing complete concepts were devised around the late 30s or so when it was seen that the lambda calculus (developed independently by Church) was equivalent to Turing machines &amp; equivalence to Post machines was shown around the same time (although these 3 models were devised somewhat independently &amp; not immediately realized to be Turing equivalent on their original construction).</p>

<p>new models are still being devised eg Cellular Automata have a much more recent history and have been shown to be in various senses Turing complete.</p>

<p>it seems fair to say that most working in computer science were familiar with Turings seminal 1936 paper &amp; that it highly influenced all later formulations of automata constructions (particularly the concept of the state transition table which seems to have been introduced by Turing)</p>

CC BY-SA 3.0
2012-02-09T21:02:39.190Z
Downvoters, please consider telling the poster why you think his answer is bad.
Raphael
CC BY-SA 3.0
2012-02-08T16:25:02.667Z
2012-02-08T16:32:47.453Z
2012-02-08T16:32:47.453Z
vzn
<p>Just for the hell of it:</p>

<blockquote>
  <p>Looking back, what would you say was the significance of Turing's 1936
  Entscheidungs-problem paper?</p>
  
  <p>I always felt people liked to make a song and dance. Something like
  the doctrine of the Trinity involved whereas to an engineer you've
  only got to be told about the stored program idea and you'd say at
  once "That's absolutely first-rate, that's the way to do it." That was
  all there was to know.</p>
  
  <p>There was no distinction in that paper that had any practical
  significance. He was lucky to get it published at all but I'm very
  glad he did. I mean [Alonzo] Churchl had got the same result by other
  methods.</p>
  
  <p>I liked Turing; I mean we got on very well together. He liked to lay
  down the law and that didn't endear him to me but he and I got on
  quite well. People sometimes say I didn't get on with Turing but it's
  just not true. But then I was very careful not to get involved.</p>
</blockquote>

<p>Maurice Wilkes.
 <a href="http://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext" rel="nofollow">http://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext</a></p>

CC BY-SA 3.0
2012-03-11T22:14:16.450Z
2012-03-11T22:14:16.450Z
yodaiken
<p><strong>Neither!</strong></p>

<p>The best way to see this independence is to read <a href="http://classes.soe.ucsc.edu/cmps130/Spring09/Papers.html">the original papers</a>.</p>

<ul>
<li><p><a href="http://classes.soe.ucsc.edu/cmps130/Spring09/Papers/turing-1936.pdf">Turing's 1936 paper</a> introducing Turing machines does not refer to any simpler type of (abstract) finite automaton.</p></li>
<li><p><a href="http://classes.soe.ucsc.edu/cmps130/Spring09/Papers/mculloch-pitts.pdf">McCulloch and Pitts' 1943 paper</a> introducing "nerve-nets", the precursors of modern-day finite-state machines, proposed them as simplified models of neural activity, not computation per se.</p></li>
</ul>

<p>For an interesting early perspective, see the <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4051186">1953 survey by Claude Shannon</a>, which has an entire section on Turing machines, but says nothing about finite automata as we would recognize them today (even though he cites Kleene's 1951 report).</p>

<p>Modern finite automata arguably start with <a href="http://classes.soe.ucsc.edu/cmps130/Spring09/Papers/kleene_1956.pdf">a 1956 paper of Kleene</a>, originally published as a RAND technical report in 1951, which defined regular expressions.  Kleene was certainly aware of Turing's results, having published <a href="http://www.springerlink.com/content/p11t718324483v87/">similar results himself</a> (in the language of primitive recursive functions) at almost the same time.  Nevertheless, Kleene's only reference to  Turing is an explanation that Turing machines are not finite automata, because of their unbounded tapes.  It's of course possible that Kleene's thinking was influenced by Turing's abstraction, but Kleene's definitions appear (to me) to be independent.</p>

<p>In the <a href="http://books.google.com/books?id=oL57iECEeEwC">1956 survey volume edited by Shannon and McCarthy</a>, in which both <a href="http://classes.soe.ucsc.edu/cmps130/Spring09/Papers/kleene_1956.pdf">Kleene's paper on regular experssions</a> and <a href="http://people.mokk.bme.hu/~kornai/MatNyelv/moore_1956.pdf">Moore's paper on finite-state transducers</a> were finally published, finite automata and Turing machines were discussed side by side, but almost completely independently.  Moore also cites Turing, but only in a footnote stating that Turing machines aren't finite automata.</p>

<p>(<a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5477410">A recent paper of Kline</a> recounts the rather stormy history of this volume and the associated Dartmouth conference, sometimes called the "birthplace of AI".)</p>

<p>(An even earlier version of neural nets is found in Turing's work on "type B machines", as reprinted in the book "The essential Turing", from about 1937 I think.  It seems likely that many people were playing with the idea at the time, as even today many CS undergrads think they have "invented" it at some point in their studies before discovering its history.)</p>

CC BY-SA 3.0
2012-03-14T15:07:38.070Z
Great answer!  But who invented state machines?  Galbraith was apparently using flowcharts as early as 1921.
reinierpost
CC BY-SA 3.0
2013-09-17T13:44:14.257Z
@JɛﬀE are you sure about the 1937 date for Turing's neural nets? I was under the impression that was [presented in an unpublished paper in 1948](http://cogsci.stackexchange.com/q/1263/29). Also does McCulloch & Pitts' model incorporate learning? I thought that B-type neural nets were historically interesting because they incorporated a "fire together, wire together" sort of learning before Hebb (1949) discovered it empirically, or Rosenblatt's model (1957).
Artem Kaznatcheev
CC BY-SA 3.0
2012-02-08T14:17:30.143Z
2012-11-22T14:55:21.793Z
2012-11-22T14:55:21.793Z
Jeffε
<p>I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"?</p>

<p>I didn't know the answer of course, but I'm curious to find out. The Turing Machine is basically a slightly more sophisticated version of a Push-Down Automata. From that I would assume that the Turing Machine was derived from automata, however I have no definitive proof or explanation. I might just be plain wrong... perhaps they were developed in isolation.</p>

<p>Please! Free this mind from everlasting tangents of entanglement.</p>

CC BY-SA 3.0
2012-02-07T17:19:02.803Z
Turing invented his machines in mid-1930s, and as far as I know, other kind of automata, like PDA or finite automata, started to appear in the 1950s, when Turing’s work was already well known.
Emil Jeřábek
CC BY-SA 3.0
2012-02-07T22:42:47.367Z
Turing invented his machine when he tried to model a human "computer". At the time, the word computer was a job title for a person who performs calculations for a living. He idealized the machine by assuming the machine has access to an infinite memory.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-02-08T15:55:50.123Z
PDAs seem to have a lot of connection to language theory ala chomsky in other words they might have even been introduced to understand human languages.
vzn
<fl.formal-languages><computability><automata-theory><turing-machines><ho.history-overview>
Is the concept of the Turing Machine derived from automata?
Emmanuel M. Smith
# Is the concept of the Turing Machine derived from automata?

(Asked by: username_0 on 2012-02-07)

I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"?

I didn't know the answer of course, but I'm curious to find out. The Turing Machine is basically a slightly more sophisticated version of a Push-Down Automata. From that I would assume that the Turing Machine was derived from automata, however I have no definitive proof or explanation. I might just be plain wrong... perhaps they were developed in isolation.

Please! Free this mind from everlasting tangents of entanglement.

**Tags:** fl.formal-languages, computability, automata-theory, turing-machines, ho.history-overview
> **Comments:**
> **username_1**: Turing invented his machines in mid-1930s, and as far as I know, other kind of automata, like PDA or finite automata, started to appear in the 1950s, when Turing’s work was already well known.  
> **username_2**: Turing invented his machine when he tried to model a human "computer". At the time, the word computer was a job title for a person who performs calculations for a living. He idealized the machine by assuming the machine has access to an infinite memory.  
> **username_3**: PDAs seem to have a lot of connection to language theory ala chomsky in other words they might have even been introduced to understand human languages.  

---

## 3 answers

### Answer by username_6 on 2012-02-08. Score: 28 | Accepted answer

**Neither!**

The best way to see this independence is to read [the original papers](http://classes.soe.ucsc.edu/cmps130/Spring09/Papers.html).

* [Turing's 1936 paper](http://classes.soe.ucsc.edu/cmps130/Spring09/Papers/turing-1936.pdf) introducing Turing machines does not refer to any simpler type of (abstract) finite automaton.
* [McCulloch and Pitts' 1943 paper](http://classes.soe.ucsc.edu/cmps130/Spring09/Papers/mculloch-pitts.pdf) introducing "nerve-nets", the precursors of modern-day finite-state machines, proposed them as simplified models of neural activity, not computation per se.

For an interesting early perspective, see the [1953 survey by Claude Shannon](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4051186), which has an entire section on Turing machines, but says nothing about finite automata as we would recognize them today (even though he cites Kleene's 1951 report).

Modern finite automata arguably start with [a 1956 paper of Kleene](http://classes.soe.ucsc.edu/cmps130/Spring09/Papers/kleene_1956.pdf), originally published as a RAND technical report in 1951, which defined regular expressions. Kleene was certainly aware of Turing's results, having published [similar results himself](http://www.springerlink.com/content/p11t718324483v87/) (in the language of primitive recursive functions) at almost the same time. Nevertheless, Kleene's only reference to Turing is an explanation that Turing machines are not finite automata, because of their unbounded tapes. It's of course possible that Kleene's thinking was influenced by Turing's abstraction, but Kleene's definitions appear (to me) to be independent.

In the [1956 survey volume edited by Shannon and McCarthy](http://books.google.com/books?id=oL57iECEeEwC), in which both [Kleene's paper on regular experssions](http://classes.soe.ucsc.edu/cmps130/Spring09/Papers/kleene_1956.pdf) and [Moore's paper on finite-state transducers](http://people.mokk.bme.hu/~kornai/MatNyelv/moore_1956.pdf) were finally published, finite automata and Turing machines were discussed side by side, but almost completely independently. Moore also cites Turing, but only in a footnote stating that Turing machines aren't finite automata.

([A recent paper of Kline](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5477410) recounts the rather stormy history of this volume and the associated Dartmouth conference, sometimes called the "birthplace of AI".)

(An even earlier version of neural nets is found in Turing's work on "type B machines", as reprinted in the book "The essential Turing", from about 1937 I think. It seems likely that many people were playing with the idea at the time, as even today many CS undergrads think they have "invented" it at some point in their studies before discovering its history.)

> **Comments:**
> **username_7**: Great answer!  But who invented state machines?  Galbraith was apparently using flowcharts as early as 1921.  
> **username_8**: @JɛﬀE are you sure about the 1937 date for Turing's neural nets? I was under the impression that was [presented in an unpublished paper in 1948](http://cogsci.stackexchange.com/q/1263/29). Also does McCulloch & Pitts' model incorporate learning? I thought that B-type neural nets were historically interesting because they incorporated a "fire together, wire together" sort of learning before Hebb (1949) discovered it empirically, or Rosenblatt's model (1957).  

---

### Answer by username_3 on 2012-02-08. Score: -1

you mention PDAs specifically. note a Turing machine is equivalent to a PDA with two stacks. PDAs original rationale seems to have been closely related to the development of "language theory" ala chomsky.

see eg [Syntactic Analysis and the Pushdown Store," Proceedings of Symposia in Applied Mathematics (Vol. 12). Providence, RI: American Mathematical Society, 1961](http://books.google.com/books/about/Structure_of_language_and_its_mathematic.html)

this is has one of the earliest references Ive seen by Oettinger, "Automatic syntactic analysis and the pushdown store" p104, dont know if there are earlier refs to the PDA.

it took many years of study of all the interelated automata to start to devise a unifying theory (still being constructed). the Turing complete concepts were devised around the late 30s or so when it was seen that the lambda calculus (developed independently by Church) was equivalent to Turing machines & equivalence to Post machines was shown around the same time (although these 3 models were devised somewhat independently & not immediately realized to be Turing equivalent on their original construction).

new models are still being devised eg Cellular Automata have a much more recent history and have been shown to be in various senses Turing complete.

it seems fair to say that most working in computer science were familiar with Turings seminal 1936 paper & that it highly influenced all later formulations of automata constructions (particularly the concept of the state transition table which seems to have been introduced by Turing)

> **Comments:**
> **username_4**: Downvoters, please consider telling the poster why you think his answer is bad.  

---

### Answer by username_5 on 2012-03-11. Score: -3

Just for the hell of it:

> Looking back, what would you say was the significance of Turing's 1936
> Entscheidungs-problem paper?
>
> I always felt people liked to make a song and dance. Something like
> the doctrine of the Trinity involved whereas to an engineer you've
> only got to be told about the stored program idea and you'd say at
> once "That's absolutely first-rate, that's the way to do it." That was
> all there was to know.
>
> There was no distinction in that paper that had any practical
> significance. He was lucky to get it published at all but I'm very
> glad he did. I mean [Alonzo] Churchl had got the same result by other
> methods.
>
> I liked Turing; I mean we got on very well together. He liked to lay
> down the law and that didn't endear him to me but he and I got on
> quite well. People sometimes say I didn't get on with Turing but it's
> just not true. But then I was very careful not to get involved.

Maurice Wilkes.
<http://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext>


---

