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?
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):
That should provide a very brief introduction to most of the computational models people talk about. 2: 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). 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. As a starting place, I'd recommend reading about the following topics (in the order listed): 1. 1: http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1