164 TURING MACHINES
one-tape DTM iV’ = (Q U {s,t}, C, CU {B},& s), where s, t $ Q, and
(PAR)
“(” ‘) = { (h, B, L)if a # B, 4 E Q, anc~ J(q, a) = P,if a = B and q E F.
(Note: s/( q, B) is undefined if q @ F.) That is, AP first moves left until it
finds the leftmost symbol of the input, and then it simulates DFA &! until it
reads a blank B. Thus, for the same input 1x3, M’ halts on x in state h if and
only if M halts on x in a final state. It follows that L(M’) = L. cl
We observe that when a DTM M halts at state h, there may be some
nonblank symbols left in the tape. We call these symbols the output of the
machine M. Since a DTM can generate outputs, it can also be used as a
model for computing functions. Note that a DTM may not halt on some
inputs, and so the function computed by it may be undefined at some inputs.
In general, we call a function f : (C;)” + Ez a partial function if f is allowed
to be undefined at some (21,... , xk) E (C;)“, that is, if the real domain of f
is a subset of (Cy)“. W e call a function f : (C;)” -+ Cz a totd function if it is
defined at every (21,... , xk) E (xi)“, that is, if the real domain of f is exactly
(C;)“. We write f (x1,... , xk) .& to denote that f is defined at (xl,... , xk),
and f (xl,... , xk) T to denote that f is undefined at (xl,... , xk). Clearly, a
total function is a special case of partial functions.
We say a partial function f : (CT)” + IEz is computed by a one-tape DTM
M if for every (x1, x2,... , xk) E (xi)” such that f(x1, x2,... , xk) is defined,
(s, Bx1Bx2B l. l Bxk!i) 1-i (~&@),
where y = f (x1, x2, l.. , xk), and for every (x1, x2,... , xk) E (CT)” such that
f(x1, x2, l l l I xk) is undefined,
(s, BxlBx2B l l l BXkB) k; l l - (never halts).
A partial function f : (CT)” -+ Cz is called a Turing-computable function if it
is computed by a one-tape DTM.
A language L is Turing-decidable if its characteristic function
XL(X) =