i.e.
χ
χ
χ
{ }
{ }
{ }
( )
(
)
sgn( ( ))
0
0
0
0 1
1
=
+ =
x
p x
R
where pre de ces sor func tion p x
R ( ) is given by
p x
x
x
x
R ( )
,
,
=
−
≠
=



1
0
0
0
.
Hence χ { } ( )
0 x is primitive recursive.
Now, we have
χ
χ
χ
χ
α α
α
α
α
α
{ , ,
}
{ }
{ }
{ } .
1 2
1
2
K
LL
n
n
=
+
+
+
Since we have proved that χ α
{ }
1
is primitive recursive and also the fact that the
sum of primitive functions is also primitive recursive, it is proved that the
characteristic function of a finite subset of N is primitive recursive. Hence
proved.
6.5 ACKERMANN’S FUNCTION
Ackermann’s function is an example of a function that is mu-recursive but not
primitive recursive. Mu-recursive functions are said to have the power of a
Turing machine. It is defined as follows:
A y
y
A x
A x
A x y
A x
A x y
( , )
( , )
(
, )
( , )
(
, ( ,
))
0
1
0
11
1
1
= +
=
−
=
−
−
It is oth er wise defined as
A y
y
A x
A x
A x
y
A x A x
y
( , )
(
, )
( , )
(
,
)
( , (
, ))
0
1
10
1
1
1
1
= +
+
=
+
+ =
+
A(x, y) can be computed for every (x, y). Hence A (x,y) is a total function. But
Ackermann’s function is not primitive recursive but recursive.
Ì Exam ple 6.5.1: Calculate A(1, 1) and A(1, 2) where A(x, y) represents
Ackermann’s function.
Solu tion
We have Ackermann’s function given by
A y
y
( , )
0
1
= +
(1)
A x
A x
(
, )
( , )
+
=
10
1
(2)
A x
y
A x A x
y
(
,
)
( , (
, ))
+
+ =
+
1
1
1
(3)
Computability
229