228 COMPUTABILITY THEORY
Enumeration of Partial Recursive Functions and R.E. Sets. For each
string ti E (0, l}, we let A& be the DTM in A4 such that IZ: is one of its
codes. Recall that L{O,~) (n) is the nth string in (0, 1)’ under the lexicographic
ordering. If x = ~{o,&), we also write A& for A&. In the rest of this chapter,
we write L for ~(o,l) and do not distinguish the integer n from the string L(n).
For each k > 1, we write 4; or 4;(n)
((0, l})k to (0,1}*
to denote the partial function from
computed by A&. That is, for every input (~1, x2,... , xk),
if A& halts on it with the final configuration (h, yB) - for some y c (0, l}*, then
~,(21,~2,-v~k) k = y; and if A& does not halt on this input, then 4: (x1,
x2, “‘9 xk) is undefined. (If Mn halts on input (x1, x2,... , xk) with a final
configuration (h,uc~Q that is not of the form (h, yB) - for some y E {O,l}*, we
arbitrarily define its output to be u1 where u1 is the longest suffix of u that
is in (0, l}*.) Th e class (4: 1 k > 1,n > 0)
recursive functions over (0, 1). - -is exactly the class of partial
Every machine h& accepts a language
L(Mn) = {x E (0, I}* 1 (Ql,XB) kj, (qn,uav) for SOme a E bw E r*},or, equivalently, L(A&) is the domain of 4:. We write l4& or W,(,) to denote
the set L(&). Then, {PKn 1 n > - 0) is exactly the class of r.e. sets over
alphabet (0, 1}.2
The above coding system shows that there are only countably many DTMs
in M and hence there are only countably many Turing-computable functions.
On the other hand, there are uncountably many functions from a countable
domain C (see Example 5.18). Thus, most functions are noncomputable.
Proposition 5.2 Let C be any finite alphabet.
(a) There exists a function f : C* + C* that is not partial recursive.
(b) There exists a set A G C* that is not r.e. (and hence not recursive).Universal Turing Machines. Once we have a coding system for DTM’s in
M, we c&n construct a universal Turing machine that can read the code y of
a DTM MY and a string x and simulate & on input x. In other words, a
universal DTM works, in the modern computer terminology, like an interpreter
of the programs written in our coding system. In this programming system,
a programmer does not have to build a specific DTM by hardware; instead,
he/she needs only a single set of hardware, the universal DTM U, and can
write a program for any DTM and submit the program together with its inputs
to the machine U and let U simulate it. It is interesting to mention that this
2 We may als o d efine, for each k > 2, the set w,k to be {(xl,... , xk) 1 M, halts on input
(Xl? l ’ ’ 9 xk)}. However, since we can always use pairing functions to encode a finite number
of strings into one, the computability theory of these sets are the same as that of sets Mr,,
and we will not discuss this separately.