19
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 13
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Feb 7, 2012 at 17:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mohammad Al-Turkistany
    Feb 7, 2012 at 22:42
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Feb 8, 2012 at 15:55

3 Answers 3

Reset to default
28
$\begingroup$

Neither!

The best way to see this independence is to read the original papers.

  • Turing's 1936 paper introducing Turing machines does not refer to any simpler type of (abstract) finite automaton.

  • McCulloch and Pitts' 1943 paper 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, 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, 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 (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, in which both Kleene's paper on regular experssions and Moore's paper on finite-state transducers 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 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.)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Great answer! But who invented state machines? Galbraith was apparently using flowcharts as early as 1921. $\endgroup$
    – reinierpost
    Mar 14, 2012 at 15:07
  • $\begingroup$ @JɛffE 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. 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). $\endgroup$
    – Artem Kaznatcheev ♦
    Sep 17, 2013 at 13:44
-1
$\begingroup$

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

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)

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ Downvoters, please consider telling the poster why you think his answer is bad. $\endgroup$
    – Raphael
    Feb 9, 2012 at 21:02
-3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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