Funciones RP

Question 1

Esquema de recursión primitiva tipo I

Answer 1

Sea h ∶ N → N
Sea g ∶ N^2 → N
Decimos que h se obtiene a partir de g por un ERI si se puede escribir de la siguiente forma:
h(0) = k ∈ N
h(n + 1) = g(n, h(n))

Teorema 26
Si h se obtiene a partir de g por un ERI y g es computable, entonces h es computable.

DEMO

Question 2

Esquema de recursión primitiva tipo II

Answer 2

Sea h ∶ N^n+1 → N
Sea g ∶ N^n+2 → N
Sea q ∶ N^n → N
Decimos que h se obtiene por ERII a partir de g y q si puede escribirse:

h(x1, x2, . . . , xn, 0) = q(x1, . . . , xn)
h(x1, x2, . . . , xn, y + 1) = g(x1, . . . , xn, y, h(x1, . . . , xn, y))

Teorema 27
Sea g ∶ N^n+2 → N
Sea q ∶ N^n → N
Sea h ∶ N^n+1 → N tal que se obtiene por ERII a partir de q y g.
Si q y g son computables ⇒ h es computable.

DEMO

Question 3

Recursividad primitiva

Answer 3

Una función es RP si es inicial o se obtiene aplicando finitas “operaciones válidas” a las Funciones iniciales, siendo las operaciones válidas:
composición, ERI y ERII.

Question 4

fuunciones inciales

Answer 4

Sea P^ n+1un predicado RP (computable).