13. Give examples for primitive recursive functions
(a) f
x y x y
add ( , ) = +
(b) f x x
( ) =
2
(c) sgn( )
,
,
x
x
x
=
=
>



0
0
1
0
14. Are the following functions primitive recursive?
(a) R x y
( , ) = Remainder (x/y).
(b) f x y
x y
( , )
( , )
= Max
(a) YES
(b) YES
15. Are the following functions primitive recursive?
(a) p x
x
x
x
R ( )
,
,
=
−
≠
=



1
0
0
0
(b) χ { } ( )
,
,
0
0
0
1
0
x
x
x
=
≠
=



(a) YES
(b) YES
16. Give an example of a function that is mu-recursive but not primitive
recursive.
Ackermann’s function.
17. Define the Ackermann’s function.
A y
y
A x
A x
A x
y
A x A x
y
( , )
(
, )
( , )
(
,
)
( , (
, ))
0
1
10
1
1
1
1
= +
+
=
+
+ =
+
18. Is Ackermann’s function recursive/primitive recursive?
It is recursive not primitive recursive.
19. What is a formal system?
A system which is complete and consistent is a formal system.
20. What are the initial functions?
(a) Zero function.
(b) Successor function.
(c) Projector function.
234
Theory of Automata, Formal Languages and Computation