768
Modeling Arithmetic, Computation, and Languages
If T is begun in standard initial configuration on the tape
b
...
1
1
1 b ...
then T will halt with final configuration
b 1 1 1 1 b
1
Therefore, T defines a one-variable function T
1
that maps 2 to 3. In general, T
maps n to n + 1, so T
1
(n) = n + 1, a total function of one variable.
In Example 42, we began with a Turing machine and observed a particular
function it computed, but we can also begin with a number-theoretic function and
try to find a Turing machine to compute it.
Definition Turing-CompuTable FunCTion
A Turing-computable function is a number-theoretic function computed by
some Turing machine.
A Turing-computable function f can in fact be computed by an infinite number of
Turing machines. Once a machine T is found to compute f, we can always include
extraneous quintuples in T, producing other machines that also compute f.
eXample 43
We want to find a Turing machine that computes the function f defined as follows:
f (n 1 , n 2 ) = e
n 2 − 1
if n 2 ≠ 0
undefined if n 2 = 0
Thus f is a partial function of two variables. Let’s consider the Turing machine
given by the following quintuples.
(0, 1, 1, 0, R)
(0, * , * , 1, R)
f  Passes right over n 1 to n 2
(1, 1, 1, 2, R)
(2, b, b, 3, R)
Counts first 1 in n 2 .
n 2 = 0; halts.
Erases last 1 in n 2 .
(2, 1, 1, 4, R)
(4, 1, 1, 4, R)
(4, b, b, 5, L)
¶  Finds the right end of n 2 .
(5, 1, b, 6, L)
(6, 1, 1, 6, L)
(6, * , b, 7, L)
f  Passes left to n 1 , erasing * .
(7, 1, b, 7, L)
(7, b, b, 8, L)
Erases n 1 .
n 1 erased; halts with n 2 − 1 on tape.