Section 9.4 Turing Machines
767
example, is to move right until the end of the binary string is found, marked by
either a blank or an X, then turn the computation over to state 2. A change of state
should occur only when something significant happens. For example, a Turing
machine cannot pass right over an indeterminate number of 1s by changing state
at each move because its behavior would then be tied to a specific input tape. On
the other hand, if the machine needs to count over a certain fixed number of 1s,
then changing states at each move would accomplish this.
REMINDER
Give the states of your
Turing machine big
enough jobs to do so that
the machine will work
in general, not just for
special cases. Test using
a variety of input tapes.
Practice 59 Design a Turing machine to recognize the set of all strings of 0s and 1s ending in 00. (This
set can be described by the regular expression (0 ~ 1)*00, so you should be able to use a
Turing machine that changes no tape symbols and always moves to the right.) Be sure to
include comments.
■
Practice 60 Modify the Turing machine of Example 41 to recognize 50
n
1
2n
0 n ≥ 06.
■
Turing Machines as Function Computers
The second job for which we will use the Turing machine is to compute functions.
Given a particular Turing machine T and a string a of tape symbols, we begin T
in standard initial configuration on a tape containing a. If T eventually halts with
a string b on the tape, we may consider b as the value of a function evaluated at
a. Using function notation, T(a) = b. The domain of the function T consists of
all strings a for which T eventually halts. We can also think of T as computing
number-theoretic functions, functions from a subset of N
k
into N for any k ≥ 1.
We will think of a string of 1s of length n + 1 as the unary representation of the
nonnegative integer n; we’ll denote this encoding of n by n. (The extra 1 in the
encoding enables us to distinguish 0 from a blank tape.) Then a tape containing
the string n 1 * n 2 * … * n k can be thought of as the representation of the k-tuple
(n 1 , n 2 , … , n k ) of nonnegative integers. If T begun in the standard initial configuration on such a tape eventually halts with a final tape that is the representation
m of a nonnegative integer m, then T has acted as a k-variable function T
k
, where
T
k
(n 1 , n 2 , … , n k ) = m. If T begun in standard initial configuration on such a tape
either fails to halt or halts with the final tape not a representation of a nonnegative
integer, then the function T
k
is undefined at (n 1 , n 2 , … , n k ). There is no need to
identify final states when using the Turing machine as a function computer.
There is thus an infinite sequence T
1
, T
2
, … , T
k
, … of number-theoretic
functions computed by T associated with each Turing machine T. For each k, the
function T
k
is a partial function on N
k
, meaning that its domain may be a proper
subset of N
k
. A special case of a partial function on N
k
is a total function on N
k
,
where the function is defined for all k-tuples of nonnegative integers.
ExaMplE 42
Let a Turing machine T be given by the quintuples
(0, 1, 1, 0, R)
(0, b, 1, 1, R)
767
example, is to move right until the end of the binary string is found, marked by
either a blank or an X, then turn the computation over to state 2. A change of state
should occur only when something significant happens. For example, a Turing
machine cannot pass right over an indeterminate number of 1s by changing state
at each move because its behavior would then be tied to a specific input tape. On
the other hand, if the machine needs to count over a certain fixed number of 1s,
then changing states at each move would accomplish this.
REMINDER
Give the states of your
Turing machine big
enough jobs to do so that
the machine will work
in general, not just for
special cases. Test using
a variety of input tapes.
Practice 59 Design a Turing machine to recognize the set of all strings of 0s and 1s ending in 00. (This
set can be described by the regular expression (0 ~ 1)*00, so you should be able to use a
Turing machine that changes no tape symbols and always moves to the right.) Be sure to
include comments.
■
Practice 60 Modify the Turing machine of Example 41 to recognize 50
n
1
2n
0 n ≥ 06.
■
Turing Machines as Function Computers
The second job for which we will use the Turing machine is to compute functions.
Given a particular Turing machine T and a string a of tape symbols, we begin T
in standard initial configuration on a tape containing a. If T eventually halts with
a string b on the tape, we may consider b as the value of a function evaluated at
a. Using function notation, T(a) = b. The domain of the function T consists of
all strings a for which T eventually halts. We can also think of T as computing
number-theoretic functions, functions from a subset of N
k
into N for any k ≥ 1.
We will think of a string of 1s of length n + 1 as the unary representation of the
nonnegative integer n; we’ll denote this encoding of n by n. (The extra 1 in the
encoding enables us to distinguish 0 from a blank tape.) Then a tape containing
the string n 1 * n 2 * … * n k can be thought of as the representation of the k-tuple
(n 1 , n 2 , … , n k ) of nonnegative integers. If T begun in the standard initial configuration on such a tape eventually halts with a final tape that is the representation
m of a nonnegative integer m, then T has acted as a k-variable function T
k
, where
T
k
(n 1 , n 2 , … , n k ) = m. If T begun in standard initial configuration on such a tape
either fails to halt or halts with the final tape not a representation of a nonnegative
integer, then the function T
k
is undefined at (n 1 , n 2 , … , n k ). There is no need to
identify final states when using the Turing machine as a function computer.
There is thus an infinite sequence T
1
, T
2
, … , T
k
, … of number-theoretic
functions computed by T associated with each Turing machine T. For each k, the
function T
k
is a partial function on N
k
, meaning that its domain may be a proper
subset of N
k
. A special case of a partial function on N
k
is a total function on N
k
,
where the function is defined for all k-tuples of nonnegative integers.
ExaMplE 42
Let a Turing machine T be given by the quintuples
(0, 1, 1, 0, R)
(0, b, 1, 1, R)