RE: Lambda calculus w/theory of computation
To: firstname.lastname@example.org, email@example.com
Subject: RE: Lambda calculus w/theory of computation
From: "Sandeep K. Shukla" <firstname.lastname@example.org>
Date: Wed, 1 May 2002 19:09:35 -0700
MMDF-Warning: Parse error in original version of preceding line at gremlin-relay.ics.uci.edu
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.