Práctica 8: Funciones Primitivas Recursivas (Lógica y Computabilidad)

Ejercicio 01

• a) No es recursiva primitiva. Me falta decir porqué, pero parece que el termino y + 1 no se achica en cada paso recursivo

• b) Si. Sea h(x) = ψ(x) y $g(x,y,z)=z+\varphi$.

f(x,0) = h(x)

f(x, y + 1) = g(x,y,f(x,y))

• c) Si. Sea $h(x)=\varphi (0,x)$ y $g(x,y,z)=\varphi (z,y+1)$.

f(x,0) = h(x)

f(x, y + 1) = g(x,y,f(x,y))

Ejercicio 02

• a. Defino máximo recursivamente como:

max(x,0) = x
max(x,y+1) = 1 + max(p(x), y)

donde p(x) es la función primitiva recursiva predecesor.

• b. Mínimo:

• c. Par:

par(0) = 1
par(t+1) = 1 - par(t)

• d. Hf (half):

hf(0) = 0
hf(t+1) = par(t) . hf(t) + [1 - par(t)] . [hf(t) + 1]

• e. Sqrt, raiz cuadrada entera:

$sqrt(x)=min_{0\leq i\leq x}(i\times i>x)-1$

• f. psq, predicado cuadrado:

$psq(x)=(sqrt(x)\times sqrt(x)=x)$

Ejercicio 03

• a)

f(x,0) = 1

f(x, y+1) = g(x,y,f(x,y))

con g(x,y,z) = z * x

• b)

Definimos $H(n,m)=n^{n^{.^{.^{n}}}}$ m veces $H(n,0)=0$

notar que $f(n)=H(n,n)$

Vemos que H es RP:

$H(n,0)=0$

$H(n,m+1)=n^{H(n,m)}=g(n,m,H(n,m))$

con $g(n,m,p)=n^{p}$

Como g es RP, H es RP y f es RP.

Ejercicio 04

• a

f(0) = 0

$f(n)=\psi ^{n}(n)=H(n,n)$

Sea $H(n,m)=\psi ^{m}(n)$ definida por recursión como:

H(n,0) = 1

$H(n,m+1)=\psi ^{H(n,m)}(n)=g(n,m,H(n,m))$

con $g(n,m,p)=\psi ^{p}(n)$

g es RP -> H es RP -> f es RP

Otra resulución: $g(x,y)=\psi ^{(x)}(y)$

$g(0,y)=y$ $g(x+1,y)=\psi (g(x,y))$

$f(x)=g(x,x)=\psi ^{(x)}(x)$

• b. Lo mismo pero con + 1

• c

g(x,y,z,0) = x $g(x,y,z,w+1)=\phi (g(x,y,z,w),z-x)$

- es el menos natural (con puntito arriba)

$f(x,y)=g(x,y,y,y+1)$

Ejercicio 05

• a) $f(x)=\sum _{i=0}^{x}(g(i)>3)$

• b) $f(x,y)=\prod _{i=y}^{x}(g(i+1)>g(i))$

• c) $f(x,y,w)=\alpha (x-y)\times \prod _{i=x}^{y}(w\geq g(i))$

donde el menos (-) es el menos con puntito arriba.