Primitive Recursive Functions Flashcards
What is a primitive recursive function?
(1) Zero, (2) successor, (3) projections, (4) composition, and (5) primtive recusive
BlooP
Primtive Recursive Functions
Base Case
- Zero: Z(n) = 0 - (“Simplist function from N to N”)
- Successor: S(n) = number following n in the natural number series
- Projections: (“Simplist function from N^k to N”)
Primitive Recursive Functions
Inductive clause
How to define complex functions from (base) functions
Composition and Primitive Recursion (Schema)
How to know n function is P.R.?
How to give def corresponds to the recursive definition
When something is finite => reduce something to a base case.
Primtive Recursive Functions
Final Clause
Only functions obtained from the base/Inductive clauses are Primitive Recursive
P.R.
Identity: (a)
id(x) = P^1_1(x)
P.R.
Addition (b)
plus(0, x) = P11(x)
plus(n + 1, x) = S(P13( plus(n, x) n, x))
P.R.
(d) Predecessor Function: pred(x)
pred(0) = 0
pred(n + 1) = n, where h(v, w) = P22(v, w)
P.R.
(f) The conditional function
cond{x, y, z}
Depends condition of “x”
P.R.
(g) Finite sums and products:
If upper and lower limit, then sum/product is primitive recursive
What is a characteristic function?
Function of n-ary predicate or relation
Logical operations on primitive recursive predicaters
P.R.
(h) Defintion by cases
Given n disjoint primitive recursive conditions ( = predicates), A1, …, An and n primitive recursive functions h1, …, h2 define following P.R. function:
Are all (computable) functions primititive recursive?
No.
Show: find functions not P.R.
(1) Proof by contradition / (2) diagolanization
P.R.
Bounded minimization (j):
“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.
P.R.
Predicates
Predicates: True/false value
Bounded existence and universality
