Re: Lambda calculus w/theory of computation
Kim Bruce <kim@...
2002-05-02 00:27:24 GMT
Thanks to the many (over 40) people who responded to my question about
materials for teaching theory of computation using lambda calculus,
RAM's, or imperative language models (WHILE or LOOP languages) rather
than Turing machines. My hope was to find a book that used one or more
of these models and also covered the standard language and machine
Unfortunately, it does not appear that there are many options for this.
The one good fit seems to be
Computability, Complexity, and Languages : Fundamentals of Theoretical
Computer Science (Computer Science and Applied Mathematics), 2nd
edition, by Martin D. Davis, Ron Sigal, Elaine J. Weyuker, 1994
My only question on this book is whether or not it would be suitable for
undergraduates (in my case, Junior CS majors).
The following book by Neil Jones also got a number of recommendations.
Unfortunately for me, it covers complexity rather than machines and
languages after the computability chapters. Computability is done from
the point of view of WHILE programs and a functional languages, and
looks quite attractive:
N.D. Jones,Computability and Complexity: From a Programming Perspective.
MIT Press, 1997. ISBN 0262100649
Other books mentioned include two out-of-print texts:
Brainerd, Landweber: Theory of Computation, Wiley, 1974.