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.

It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed independently of each other. So 'what' were the founding reasons of each of them? Why were they developed? What questions were each of the mathematical models aiming to answer?

I'm aware of TMs being created for answering the Entscheidungsproblem proposed by David Hilbert and it's leading to answer questions as to what is computable and what isn't. Then what about FAs? On another question an answer pointed me to a paper talking about nerve nets and Kleene's papers (both of which I hadn't read before. I didn't even know FAs were traced back to nerve nets.) So what was it that FAs were trying to answer at that time that wasn't answerable by TMs or was too cumbersome to do so? (I don't really know what nerve nets are and what FAs have to do with them. Perhaps the answer lies there?)

Reason for question: ToC is usually taught in a progression from D/N-FAs to PDAs to TMs but all of them were independently created, decades apart. The logical progression subconsciously implies a chronological sequence of 'discovery' but that isn't true and am trying to understanding their genesis better, out of curiosity. It'd be great to have the 'intentions/needs' of creating both of them in one place to better my understanding of the same. I'd also like to use this as a teaching aid if possible for the undergrads who fail to understand the essence of ToC

share|improve this question
This seems very much like your other question. Are you basically asking for the first paper on DFAs? –  Lev Reyzin Dec 23 '12 at 22:15
I like those kind of questions because the initial motivation or ... derivation of things/proofs/principles is often omitted in classes –  Ronny Brendel Dec 23 '12 at 22:48
@LevReyzin - In principle there is some overlap. I never knew that TMs predated FAs by almost 2 decades! Hence I'd like to know what led to their creation for historical and pedagogical reasons :) –  PhD Dec 24 '12 at 0:09
This has a short answer already. So? (cstheory.stackexchange.com/a/14816/7176) –  Kris Dec 24 '12 at 7:00
add comment

2 Answers

up vote 6 down vote accepted

There are different questions being asked here. It is important to keep in mind that most courses on this topic are designed to clearly communicate and deepen a student's understanding of the concept of computation.

Historical motivation and precedence is not usually required to communicate the current understanding of the concepts or even their current relevance. Moreover, historical and philosophical issues are often subtle and doing them academic justice requires time and training that is not usually part of a computer science curriculum.

  1. The creation of Turing Machines I think it is simplistic to believe that Turing Machines were created only to address the Entscheidungsproblem. The theory of computation was an idea whose time has arrived. There were several equivalent models of computation developed in that period with different motivation. The different models were not developed in isolation. Post developed a model of mechanical calculation in addition to more mathematical models of Church and Kleene. Electro-mechanical calculational devices were also in the background of such developments. Turing may have developed his model specifically motivated by a specific problem, but he did not work in a vacuum and his historical and intellectual context should not be discounted.
  2. The creation of Finite Automata I would disagree that finite-automata were over two decades apart from the development of computational devices. McCulloch and Pitts proposed a model similar to finite automata while studying human cognition in the early 40s. The modern heritage of finite automata goes back to Rabin and Scott. Their paper is a model of clarity and is one search away. The first two words "Turing machines" show that they were clearly aware of Turing machines.
  3. The modern presentation of computability theory It is not true that the material we learn and teach about finite automata was developed independently of work on Turing machines. The material you are taught was developed in the awareness of results of Turing machines and the motivation for these results is clearly available in the work of Rabin and Scott.

I appreciate the desire to know about historical origins, but it is very important to appreciate that this is a nuanced topic and you cannot always find simple answers. Often, we do not even know when or why a concept was developed.

Regarding your last paragraph, the historical origins are, in my opinion, not a good source of motivation for or understanding about the essence of computation. In fact, they are a pretty bad source for undergrads. There are many contemporary essays, books, talks and the like about why computation is important, universal, beautiful, fascinating, and deep. That's where you should be looking. Here are a few random starting points in no particular order.

  1. The Algorithm: Idiom of Modern Science
  2. The emotion universe
  3. The Computational Universe
  4. Great Ideas in Theoretical Computer Science
  5. The Computational Universe
  6. Computers Ltd. What They Really Can't Do
  7. The Unusual Effectiveness of Logic in Computer Science
  8. And Logic Begat Computer Science: When Giants Roamed the Earth
share|improve this answer
Thanks a ton (again). A small favor, would you happen to have links to the history of what happened when in ToC? Something like a chronological order of 'papers published' e.g. 1940 TM, 1959 Kleene's paper on FSMs etc (or is it hidden in one of the links above?) –  PhD Dec 24 '12 at 20:01
I do not know of a source that summarises this information directly. There are articles that cover Turing-complete models but I doubt there is something doing this for finite automata, PDAs, and the entire landscape. –  Vijay D Dec 24 '12 at 22:07
add comment

The logical progression subconsciously implies a chronological sequence of 'discovery'

I think the entire premise here is wrong. For example, the whole story of analysis is a ton of hard work in the 18th-19th century to "fix" the nonrigorous analysis of earlier times. And if you've ever taken a class that teaches riemannian geometry, it might even start with the category-theoretic view, which is clearly not chronologically accurate.

A logical progression, especially as taught in the classroom, emphasizes a viewpoint and statements about how the material fits together. It can sometimes reflect an orderly chronological understanding, but more often than not is a retroactive imposition of structure on a field that developed in a very unstructured way.

The FA to TM progression is a viewpoint: one that tries to explore the implications of increasing complexity in the computing device being used.

share|improve this answer
I am not saying it "is" chronologically accurate. I meant that students being introduced to ToC with a sequential structure from FA -> PDA -> TMs, may mistakenly assume a chronological order. Most courses don't do a good job of stating what came first and in what order. The viewpoint is "just presented" without any background of how we got there. I do not make a claim, I only said that it seems to apply chronological ordering (which is wrong). –  PhD Dec 24 '12 at 19:57
I don't know about "most courses", but I agree that it's useful to give a sense of the (often messy) history of a sequence of ideas rather than presenting it as a fait accompli. But more generally, your question asks for a good way to explain the FA->PDA->TM sequence, and the one I mentioned is such a way. –  Suresh Venkat Dec 24 '12 at 21:47
add comment

Your Answer


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.