Recursion - Primitive

Question 1

What does it mean if a function is primitively recursive

Answer 1

can be built up using the base functions and the operations of composition and primitive recursion

Question 2

Primitive recusion base functions

Answer 2

z x = 0
s x = x + 1
projection:

p x y = x & p x y = y

Question 3

Composition operation

Answer 3

f x y = g ((h1 x y), (h2 x y))

Question 4

What does it mean for a function to be computable

Answer 4

Godel = Function f is computable iff it is general recursive

Question 5

general recursive

Answer 5

partial functions taking finite tuples of natural numbers and return a single natural number

Question 6

What are the primitive recursive functions

Answer 6

x + y
x * y
x ^ y
x !

Question 7

Ackerman function

Answer 7

Computable but not prim recursive

next values of the function depends on calls with larger parameters