Diferencia entre revisiones de «Práctica 8: Funciones Primitivas Recursivas (Lógica y Computabilidad)»

De Cuba-Wiki
Sin resumen de edición
 
Sin resumen de edición
Línea 1: Línea 1:
==Ej 4==
==Ej. 2==
*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:
 
<math>sqrt(x) = min_{0 \le i \le x}(i \times i > x) - 1 </math>
 
*f. psq, predicado cuadrado:
<math>psq(x) = (sqrt(x) \times sqrt(x) = x)</math>
 
==Ej. 3==
*a)
f(x,0) = 1
 
f(x, y+1) = g(x,y,f(x,y))
 
con g(x,y,z) = z * x
 
*b)
Definimos <math>H(n,m) = n^{n^{.^{.^{n}}}}</math>  m veces
<math>
H(n,0) = 0</math>
 
notar que <math>f(n) = H(n,n)</math>
 
Vemos que H es RP:
 
<math>H(n,0) = 0</math>
 
<math>H(n, m+1) = n^{H(n,m)} = g(n,m,H(n,m))</math>
 
con <math>g(n,m,p) = n^p</math>
 
Como g es RP, H es RP y f es RP.
 
==Ej. 4==
*a
*a


<math>g(x,y) = \psi^(x) (y)</math>
<math>g(x,y) = \psi^{(x)}(y)</math>


<math>g(0,y) = y</math>
<math>g(0,y) = y</math>
<math>g(x+1, y) = \psi(g(x,y))</math>
<math>g(x+1, y) = \psi(g(x,y))</math>


<math>f(x) = g(x,x) = \psi^(x) (x)</math>
<math>f(x) = g(x,x) = \psi^{(x)}(x)</math>


*b. Lo mismo pero con + 1
*b. Lo mismo pero con + 1

Revisión del 22:56 27 nov 2006

Ej. 2

  • 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:

  • f. psq, predicado cuadrado:

Ej. 3

  • a)

f(x,0) = 1

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

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

  • b)

Definimos m veces

notar que

Vemos que H es RP:

con

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

Ej. 4

  • a

  • b. Lo mismo pero con + 1
  • c

g(x,y,z,0) = x

- es el menos natural (con puntito arriba)