Primitive Recursive Functions

Question 1

What is a primitive recursive function?

Answer 1

(1) Zero, (2) successor, (3) projections, (4) composition, and (5) primtive recusive

BlooP

Question 2

Primtive Recursive Functions

Base Case

Answer 2

1. Zero: Z(n) = 0 - (“Simplist function from N to N”)
2. Successor: S(n) = number following n in the natural number series
3. Projections: (“Simplist function from N^k to N”)

Question 3

Primitive Recursive Functions

Inductive clause

How to define complex functions from (base) functions

Answer 3

Composition and Primitive Recursion (Schema)

Question 4

How to know n function is P.R.?

Answer 4

How to give def corresponds to the recursive definition
When something is finite => reduce something to a base case.

Question 5

Primtive Recursive Functions

Final Clause

Answer 5

Only functions obtained from the base/Inductive clauses are Primitive Recursive

Question 6

P.R.

Identity: (a)

Answer 6

id(x) = P^1_1(x)

Question 7

P.R.

Addition (b)

Answer 7

plus(0, x) = P11(x)

plus(n + 1, x) = S(P13( plus(n, x) n, x))

Question 8

P.R.

(d) Predecessor Function: pred(x)

Answer 8

pred(0) = 0
pred(n + 1) = n, where h(v, w) = P22(v, w)

Question 9

P.R.

(f) The conditional function

Answer 9

cond{x, y, z}

Depends condition of “x”

Question 10

P.R.

(g) Finite sums and products:

Answer 10

If upper and lower limit, then sum/product is primitive recursive

Question 11

What is a characteristic function?

Answer 11

Function of n-ary predicate or relation

Logical operations on primitive recursive predicaters

Predicate is primitive recursive, if its characteristic function is

Question 12

P.R.

(h) Defintion by cases

Answer 12

Given n disjoint primitive recursive conditions ( = predicates), A1, …, An and n primitive recursive functions h1, …, h2 define following P.R. function:

Question 13

Are all (computable) functions primititive recursive?

Answer 13

No.
Show: find functions not P.R.

(1) Proof by contradition / (2) diagolanization

Question 14

P.R.

Bounded minimization (j):

Answer 14

“the least y less or equal than n, such that h(x, y) = 0 if there is on; n otherwise”
f yields the minimum value of y for which h holds.

Question 15

P.R.

Predicates

Answer 15

Predicates: True/false value
Bounded existence and universality

Question 16

What is a BlooP program?

Answer 16

Same as Primitive Recursive functions.

Simple (computer) language for representing predictably terminable computations

Characterized by boundedness

Expressions in capital TYPEWRITER (part of lang); epxressions in <angular brackets> meta-variables.

Question 17

How is BlooP characterized by the boundedness of the loop?

Answer 17

LOOP <mathematical expression> TIMEs

Therefore, corresponds to class of primitive recursive functions