Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
12  
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 Feb 7 '12 at 17:19
1  
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 Feb 7 '12 at 22:42
    
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 Feb 8 '12 at 15:55
add comment

3 Answers 3

up vote 26 down vote accepted

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.)

share|improve this answer
1  
Great answer! But who invented state machines? Galbraith was apparently using flowcharts as early as 1921. –  reinierpost Mar 14 '12 at 15:07
    
@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). –  Artem Kaznatcheev Sep 17 '13 at 13:44
add comment

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)

share|improve this answer
4  
Downvoters, please consider telling the poster why you think his answer is bad. –  Raphael Feb 9 '12 at 21:02
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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