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

To: types@cis.upenn.edu

Subject: Lambda calculus w/theory of computation

From: Kim Bruce <kim@cs.williams.edu>

Date: Mon, 15 Apr 2002 17:23:34 0400

Organization: Williams College

ReplyTo: kim@cs.williams.edu

UserAgent: Mozilla/5.0 (Macintosh; U; PPC; enUS; rv:0.9.4.1) Gecko/20020318 Netscape6/6.2.2
This question is a bit off topic, but I hope it is of sufficient
interest [because of lambda calculus] to this group anyway.
I will be teaching our Theory of Computation course this coming fall,
again. The topics are the standard: regular sets and finite automata,
contextfree languages and pushdown automata, Turing machines and
decidability.
I personally find Turing machines to be a very unsatisfying model of
computation, and would prefer to rely on other models. My favorites
would be lambda calculus, RAM's, and imperative language models (e.g.,
the LOOP language). My belief is that students would find the three of
these easier to relate to than Turing machines. However, I have been
unable to find a book for our undergraduate (juniorlevel) course that
covers these models. Occasionally, a book will cover the RAM model as a
sidelight, but I have been unable to find a book, for example, that
covers lambda calculus.
Does anyone have any suggestions for books (or even detailed lecture
notes) that cover the basic topics relating to languages (regular and
contextfree grammars and machines) and undecidablility as well as a
less "traditional" approach to computability? [Though of course the
lambda calculus was contemporaneous  or even earlier than  Turing
machines.] Reply directly to me and I will summarize later if there is
interest.
Kim Bruce
Williams College