Information Technology Reference
In-Depth Information
5.9.3 Partial Recursive Functions are RAM-Computable
There is a nice correspondence between RAM programs and partial recursive functions. The
straight-line programs result from applying composition to the base functions. Adding primi-
tive recursion corresponds to adding for-loops whereas adding minimilization corresponds to
adding while loops.
It is not difficult to see that every partial recursive function can be described by a program
in the RAM assembly language of Section
3.4.3
. For example, to compute the zero function,
Z
(
x
)
, it suffices for a RAM program to clear register R
1
. To compute the successor function,
S
(
x
)
, it suffices to increment register R
1
. Similarly, to compute the projection function
U
j
,
one need only load register R
1
with the contents of register R
j
. Function composition it is
straightforward: one need only insure that the functions
f
j
,1
m
, deposit their values
in registers that are accessed by
g
. Similar constructions are possible for primitive recursion
and minimalization. (See Problems
5.29
,
5.30
,and
5.31
.)
.......................................
Problems
THE STANDARD TURING MACHINE MODEL
≤
j
≤
5.1 Show that the standard Turing machine model of Section
5.1
and the model of Sec-
tion
3.7
are equivalent in that one can simulate the other.
PROGRAMMING THE TURING MACHINE
5.2 Describe a Turing machine that generates the binary strings in lexicographical order.
The first few strings in this ordering are 0, 1, 00, 01, 10, 11, 000, 001,
....
5.3 Describe a Turing machine recognizing
x
i
y
j
x
k
{
|
i
,
j
,
k
≥
1and
k
=
i
·
j
}
.
5.4 Describe a Turing machine that computes the function whose value on input
a
i
b
j
is
c
k
,where
k
=
i
j
.
5.5 Describe a Turing machine that accepts the string
(
u
,
v
)
if
u
is a substring of
v
.
5.6 The
element distinctness language
,
L
ed
, consists of binary strings no two of which
are the same; that is,
L
ed
=
·
w
i
∈B
∗
and
w
i
{
2
w
1
2
...
2
w
k
2
|
=
w
j
,for
i
=
j
}
.
Describe a Turing machine that accepts this language.
EXTENSIONS TO THE STANDARD TURING MACHINE MODEL
5.7 Given a Turing machine with a double-ended tape, show how it can be simulated by
one with a single-ended tape.
5.8 Show equivalence between the standard Turing machine and the one-tape
double-
headed
Turing machine with two heads that can move independently on its one tape.
5.9 Show that a pushdown automaton with two pushdown tapes is equivalent to a Turing
machine.
5.10 Figure
5.14
shows a representation of a Turing machine with a two-dimensional tape
whose head can move one step vertically or horizontally. Give a complete definition of
a two-dimensional TM and sketch a proof that it can be simulated by a standard TM.
Search WWH ::
Custom Search