FOM: Opinions on place to start considering computation....

[William Tait]

  Steve Stevenson (7/27/01) wrote

  >Suppose you have a colleague who just arrived from Mars. This
  >colleague is interested in knowing what Earth mathematicians consider
  >to be {\em computation}. They are impatient and want to read as few
  >pages as possible.
  >
  >Question: what is your reading list?
  >
  >Several people I have asked before said, "Chapters 1-3 of Hartley
  >Roger's Theory of {\em Recursive Functions and Effective
  >Computability}." Would you keep that? What would you add?

  I would add Joseph Shoenfield's short ``Recursion Theory'' [Lecture
  Notes in Logic, Springer-Verlag 1993], which builds the foundations
  for most topics in classical recursion theory in 78 pages.

  Bill Tait

--