[Prev][Next][Index][Thread]
RE: Lambda calculus w/theory of computation

To: kim@cs.williams.edu, types@cis.upenn.edu

Subject: RE: Lambda calculus w/theory of computation

From: "Sandeep K. Shukla" <skshukla@ics.uci.edu>

Date: Wed, 1 May 2002 19:09:35 0700

Importance: Normal

Inreplyto: <200205020030.g420Ui7t014907@saul.cis.upenn.edu>

MMDFWarning: Parse error in original version of preceding line at gremlinrelay.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.
Regards
Sandeep Shukla
http://www.ics.uci.edu/~skshukla