Primitive Rec, Ackerman’s Function, Decidable

Exercise Informally show that the following functions are computable:

• 
  Given x, determine the number of states in M_x.
  

• 
  Given x, determine the number of symbols in the alphabet of M_x.
  
• 
  Given numbers x, y, s, determine if M_x halts on y in less than s steps.
  
• 
  Given numbers x and y, produce the code for the Turing Machine that computes the composition of the functions computed by M_x and M_y.
  

Our coding has some very nice properties that we now state as theorems. There is nothing inherently good about the coding we used, virtually any coding one might come up with has these properties. The properties essen- tially say that we can treat the indices of a Turing Machines as though they were programs. We will be using these theorems informally, without explicit reference to them, for most of this course.


Theorem 5.3 (s-1-1 Theorem) There exists a primitive recursive function
s_1-1 such that for all x, y, and z

1-1
M_x(y, z) = M_{s (x,y)}(z)


.

Intuitively this is saying that parameters and code are interchangeable. If JAVA was being used instead of Turing Machines, the s-1-1 function would merely be replacing a READ statement with a CONST statement.

The above theorem is better known in its generalized form: