Stone: Section 17

From CSWiki

Here, we finally get to the big proofs of equivalence between Turing machines and recursive functions. In particular, once we account for encoding character strings as numbers, the partially recursive sets are precisely the Turing-recognizable sets, and the recursive sets are precisely the Turing-decidable sets.

However, our simulation of Turing machines was horribly inefficient, with even the very simple Turing machine in the example on page 6 has an encoding on the order of . This inefficiency clashes with our practical, from working with Scheme, that recursive functions can actually be an efficient means of solving problems. Of course, it helps that in Scheme car and cdr are primitive operations, whereas in the recursive function theory we have been developing we must resort to very large encodings to even make use of lists. If we were to make car, cdr, and list-recursion into primitive operations, would recursive functions start to have reasonable efficiencies? Are Turing machines inherently more efficient than recursive functions, no matter how many primitive operations we allow? These will be some interesting questions to think about as we move into the last section of the course, on complexity theory.