Good resources to learn about models of computation?

Question

Out of curiosity, I am trying to identify what model of computation a system I work with is functionally equivalent to, and prove the equivalence. The longer I spend on this problem the more I suspect the system isn't Turing-equivalent. My understanding of Turing Machines and recursively enumerable languages is good but I don't know much about automata with lesser capabilities (e.g. pushdown automata), so I am not sure how to proceed.

First, can anyone recommend a good resource for learning about different models of computation? I'm interested in grammars, languages and automata, and how to prove equivalence and difference between all of them. Ideally the resource would break down all the elements of each model in great detail and compare them.

Second, is there a general approach or framework that should be used when trying to fit a system onto any of these computational models?

Answer 1

I'd recommend a good textbook on computer science (In my Uni course, I'm studying from Sipser's Introduction to the Theory of Computation, which is very good in my opinion. You might also find a free textbook which teaches the same, but I don't have any experience with one so I can't recommend).

The other approach would probably be just to read up on Wikipedia. You can actually get a lot of mileage out of the Wikipedia articles, if you know what you're looking for and in what order. Also, if anything is unclear, you can usually Google it and find more resources about that particular subject.

Of course, this will not be as good as a real textbook, but it's a good place to get started right now, and it's free.

As a starting point, I'd recommend reading about the following topics (in the order listed):

1. Deterministic Finite Automaton
2. Nondeterministic Finite Automaton, and their equivalence to DFAs.
3. Regular Languages, and their equivalence to DFAs.
4. Pushdown Automata
5. Context-free Grammars, and their equivalence to Pushdown Automata.
6. Chomsky Hierarchy
7. Turing Machines

That should provide a very brief introduction to most of the computational models people talk about.

Answer 2

The video lectures from the following link gives good introduction to theory of computation. This is one of the best resources on this topic.

Video Lectures on Theory of Computation by Prof. Shai Simonson

Answer 3

An older text that may be hard to find is Hopcroft and Ullman's "Introduction to Automata Theory, Languages, and Computation". There are a number of editions --- I have heard that '79 is the best, in as much as it pulls the fewest punches in introducing complex stuff. It a legitimate, albeit small textbook, and it introduces the whole field, not just what you're looking for. I suggest this on the likely vain hope that maybe one of those "trickier" proofs other sources leave out may be your key.

As a gentler starting point, there are a few handy "benchmark" languages.

• If your model can recognize the language of all strings where there are the same number of As and Bs in a string, then it is at least more powerful than FSM.
• If it can't, then it may be equivalent to FSM.
• Similarly, if your model can recognize the language of all strings where the are the same number of As, Bs, and Cs in a string, then it is more powerful than a CFG, or PDA.

These "benchmark languages" are really just functions in disguise --- the first is basically asking if 2 unary numbers are equal, the second is asking if 3 unary numbers are equal. They are nice and simple, and are well-known to be above or below the capabilities of particular models. I don't know simple ones for the more complex machines, so you may be on your own.

Note that for the model "LBA", linearly bounded automata, I believe that there is no known natural language that is computable with a TM, but NOT an LBA. This statement is drawn from hazy memories, so don't take it as a formal proof. :)

Note (lastly) that the "benchmark" languages ARE NOT ESTABLISHING EQUALITY. That is to say, if your model cannot compare 2 unary numbers, that does not mean it is necessarily equivalent to a FSM, it could be even weaker. The languages would only establish what it is greater than in power, or less than in power.

On a completely (completely) different track, Sipser's book does do proofs of equivalence between regexes and FSM, as well as between PDAs and CFGs. I'm not sure how helpful that will be, as you are quite vague on what sort of model of computation you're considering, but if you're dead-set on equivalence, those may be good starting points.