The Theory of Computation

Because most of these solutions require a fair amount of notation, the first version of this solution manual provides only Postscript files. In the near future, an HTML version should be available, but it will require Netscape with some modifications in order to be readable, since mathematics support remains minimal under HTML.

Exercises from the text are referred to by their number; additional exercises use numbers matching those given in the list of additional exercises. For convenience, each entry below also gives a few keywords for each exercise to help in locating a specific exercise.

Files use plain fonts (Computer Modern) and formatting rather than the fonts and format of the text and so are small for fast downloading.

Text Exercises

• within the text
  • Exercise 1 (p. 126) formal definitions for some primitive recursive functions
  • Exercise 2 (p. 128) formal definition of course-of-values recursion
  • Exercise 3 (p. 128) formal definition of definition by cases
  • Exercise 4 (p. 129) primitive recursive definitions for several functions
  • Exercise 5 (p. 129) encoding of primitive recursive definitions
  • Exercise 6 (p. 129) primitive recursive definition of bounded quantifiers
  • Exercise 7 (p. 131) primitive recursive definition of building block for Ackerman's function
  • Exercise 8 (p. 136) diagonalization over total functions and over recursive functions
  • Exercise 9 (p. 144) composition of TMs is primitive recursive
  • Exercise 10 (p. 147) existence of a step function in any programming system
• in the exercise section
  • Exercise 11 formal definitions for some primitive recursive functions
  • Exercise 12 iteration is primitive recursive
  • Exercise 13 variant of recursion is primitive recursive
  • Exercise 14 program Ackermann's function
  • Exercise 15 reductions from K
  • Exercise 16 classify a number of sets as recursive, r.e., non-r.e.
  • Exercise 17 the busy beaver problem is undecidable
  • Exercise 18 r.e. sets are closed under r.e. union
  • Exercise 19 r.e. sets need not be closed under r.e. intersection
  • Exercise 20 infinite r.e. sets have injective enumerators
  • Exercise 21 infinite recursive sets and monotonic enumerators
  • Exercise 22 is "computes the same function as" decidable?
  • Exercise 23 recursively inseparable sets
  • Exercise 24 mapping finite subsets of naturals to naturals
  • Exercise 25 the Rice-Shapiro theorem
  • Exercise 26 undecidability using the recursion theorem
  • Exercise 27 a productive set
  • Exercise 28 prove that productive sets have an infinite r.e. subset
  • Exercise 29 cylindrification
  • Exercise 30 one-one reductions

Additional Exercises

• Additional Exercise 1 practive with primitive recursive definitions
• Additional Exercise 2 practice classifying sets as recursive, r.e., or non-r.e.
• Additional Exercise 3 closure properties of r.e. sets
• Additional Exercise 4 every infinite r.e. set has a nonrecursive r.e. subset
• Additional Exercise 5 every infinite recursive set has a non-r.e. subset
• Additional Exercise 6 images and inverse images of recursive and r.e. sets
• Additional Exercise 7 any r.e. set that obeys Rice's theorem is creative