~I. , ~, ~, a, fl) differs from cp(E, ~, ~, a, fi) in t h a t in the case when there is similarity the first a and/3 are erased. cpe(~, ~, a, fl). The sequence of symbols m a r k e d a is compared with the sequence m a r k e d ft. -> ~ if t h e y are similar. Otherwise -> ~I. Some of the symbols a and fl are erased.

Then it would have q, p(q), p (p(q)), p (p (p(q))), ... as m-configurations. Our interpretation rule then is this. We are given the names of the m-configurations of the machine, mostly expressed in terms of m-functions. We are also given skeleton tables. All we want is the complete table for the m-configurations of the machine. This is obtained by repeated substitution in the skeleton tables. ] Ox COMPUTABLE NUMBERS. 237 Further examples. (In the explanations the symbol " - > " is used to signify " t h e machine goes into the m-configuration .

In this we could replace el(q, [~, x) by q' and then give the table for f (with the right substitutions) and eventually reach a table in which no m-fmmtions appeared. p) f f Any Pr R, R pcl(ff-, fi) Pfi C 1((5) L C ~(~) R P) 1 t. None f"(~, ~, ~) f (r(~), ~, From ~e (C, fi) the machine prints fi at the end of the sequence of symbols and -+ (5. From f'(C, ~, a) it does the same as for f((5, ~, a) but moves to the left before-> ~. / c(E, ~, a). The machine writes at the end the first symbol marked a and ~ ~.