[Prev][Next][Index][Thread]

RE: Lambda calculus w/theory of computation

From my experience, Martin Davis and Weyuker book is the best among the
books you mentioned. I had it as my Undergraduate supplementary text, and
Graduate text for theory of Computation. It is wonderfully written book,
much better than any other introduction to recursive function theory. Also,
the WHILE/LOOP language to parallelly develop the intuition of recursive
function theory is excellent. It is also quite appropriate for undergrads in
my opinion. The alternatives  are Sipser (more AUtomata and Complexity
theory, not much recursion theory), and Aho, Hopcroft, Ullman (same
problem), Gurari (same problem), Landweber (not so good) etc.

However, I did not see the book by Cutland (Recursive FUnction Theory) on
your list. I think it is Cambridge Univ Press book, and it has a model of
UNiversal Register Machine to introduce the notion of computation, and then
does a very good job about how to use WHILE/LOOP type language to express
computation on that machine, etc. I liked it a lot.
Also there is a book by Cohen which is pretty good, and that comes with a
disk containing Turing machine simulator etc.

Regards

Sandeep Shukla
http://www.ics.uci.edu/~skshukla