Information Technology Reference
In-Depth Information
and three operations on functions, composition, primitive recursion, and minimalization. Al-
though we do not have the space to show this, the functions computed by Turing machines are
exactly the partial recursive functions. In this section, we show one half of this result, namely,
that every partial recursive function can be encoded as a RAM program (see Section
3.4.3
)that
can be executed by Turing machines.
We begin with the primitive recursive functions then describe the partial recursive func-
tions. We then show that partial recursive functions can be realized by RAM programs.
5.9.1 Primitive Recursive Functions
Let
=
{
0, 1, 2, 3,
...
}
be the set of non-negative integers. The partial recursive functions,
f
:
n
m
,map
n
-tuples of integers over
to
m
-tuples of integers in
for arbitrary
n
and
m
. Partial recursive functions may be partial functions. They are constructed from
threebasefunctiontypes,the
successor function
S
:
→
→
,where
S
(
x
)=
x
+
1,
the
predecessor function
P
:
,where
P
(
x
)
returns either 0 if
x
=
0orthe
integer one less than
x
,andthe
projection functions
U
j
:
n
→
n
,where
U
j
(
x
1
,
x
2
,
...
,
x
n
)=
x
j
. These basic functions are combined using a finite number of
applications of function composition, primitive recursion, and minimalization.
Function composition
is studied in Chapters
2
and
6
.Afunction
f
:
n
→
,1
≤
j
≤
→
of
n
arguments is defined by the composition of a function
g
:
m
→
of
m
arguments with
m
functions
f
1
:
n
,
f
2
:
n
,
...
,
f
m
:
n
→
→
→
,eachof
n
arguments, as
follows:
f
(
x
1
,
x
2
,
...
,
x
n
)=
g
(
f
1
(
x
1
,
x
2
,
...
,
x
n
)
,
...
,
f
m
(
x
1
,
x
2
,
...
,
x
n
))
Afunction
f
:
n
+
1
→
of
n
+
1 arguments is defined by
primitive recursion
from a
function
g
:
n
of
n
arguments and a function
h
:
n
+
2
→
→
on
n
+
2arguments
if and only if for all values of
x
1
,
x
2
,
...
,
x
n
and
y
in
:
f
(
x
1
,
x
2
,
...
,
x
n
,0
)=
g
(
x
1
,
x
2
,
...
,
x
n
)
f
(
x
1
,
x
2
,
...
,
x
n
,
y
+
1
)=
h
(
x
1
,
x
2
,
...
,
x
n
,
y
,
f
(
x
1
,
x
2
,
...
,
x
n
,
y
))
In the above definition if
n
=
0, we adopt the convention that the value of
f
is a constant.
Thus,
f
(
x
1
,
x
2
,
...
,
x
n
,
k
)
is defined recursively in terms of
h
and itself with
k
replaced by
k
−
1unless
k
=
0.
DEFINITION
5.9.1
The class of
primitive recursive functions
is the smallest class of functions
that contains the base functions and is closed under composition and primitive recursion.
Many functions of interest are primitive recursive. Among these is the
zero function
Z
:
,where
Z
(
x
)=
0. It is defined by primitive recursion by
Z
(
0
)=
0and
Z
(
x
+
1
)=
U
2
(
x
,
Z
(
x
))
Other important primitive recursive functions are addition, subtraction, multiplication, and
division, as we now show. Let
f
add
:
2
→
,
f
sub
:
2
,
f
mult
:
2
→
→
→
,and
f
div
:
2
denote integer addition, subtraction, multiplication, and division.
For the
integer addition function
f
add
introduce the function
h
1
:
3
→
on three
arguments, where
h
1
is defined below in terms of the successor and projection functions:
h
1
(
x
1
,
x
2
,
x
3
)=
S
(
U
3
(
x
1
,
x
2
,
x
3
))
→
Search WWH ::
Custom Search