A mathematically mature introduction to Turing Machines and Computability [reference-request]

Question

In the computer science course for mathematicians held at my university Turing Machines have been presented very briefly. So much so that I didn't quite get why they are relevant to mathematics. I did understand what a Turing Machine is, but I feel that the presentation given was (for schedule reasons) quite naive and simplified. So I would like to ask if you can point out a good reference for a mathematically mature introduction to turing machines and computability.

Answer 1

Classics:

Introduction to Metamathematics by S.C. Kleene. One of the first books about computation theory. General introduction to the mathematical logic. Includes very basic set theory, first order logic, formal number theory (including Gödel), recursive functions and Turing machines. Centered around the logic. See Teach Yourself Logic, #8. The Big Books — starting with Kleene 1952.

Computability and Unsolvability by Martin Davis. Turing machines, computable/recursive functions, several applications of the general theory: the words problem for semigroups, Hilbert's 10th probrem, incompleteness, classification of unsolvable decision problems... More centered in computer science.

Modern:

The Pillars of Computation Theory by Arnold L.Rosenberg. Finite automata, Turing machines, formal languages, the halting problem, nondeterministic Turing machynes, introduction to the compexity theory.

Added by popular demand:

Computability and logic by Boolos, Burgess and Jeffrey.

Answer 2

I have found that this pdf http://www.staff.science.uu.nl/~ooste110/syllabi/compthmoeder.pdf helps give a mature & brief theoretical introduction. Oosten also includes detailed proofs of the main theorems in recursive function theory that are necessary for carrying out rigorous details in every domain of mathematical logic related to the use of recursive functions, including the $s^m_n$ theorem acting on the programs of Turing machines, the recursion theorem, and the fixed point theorem (all located in section 2.4 of the pdf).

A more encyclopedic direction which covers a great deal is Odifreddi's Classical Recursion Theory (2 volumes). A quick search on amazon or even google may have an online pdf, but I have not checked into this.

Hope this helps!

Answer 3

I'm partial to Ullman, Hopcroft's text. Jeff Ullman runs a Coursera course on Automata theory, and I have heard very good things from someone I know who is a linguist. The text gives a very comprehensive overview of formal languages and automata, as well as issues of computability and complexity. I think it is very thorough and well done, plus having a Coursera course to work through can be helpful. More here: http://infolab.stanford.edu/~ullman/pub/ialctoc.txt

Michael Sipser is another standard text on the subject, and he is one of the foremost experts in the field. I haven't used this book, but I've heard good things. It also looks pretty comprehensive. http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X