Ejemplo: Función de Ackerman
F(i,x) = (i=0) ? x+1 : ((x=0) ? F(i-1,1) :
F(i-1,F(i,x-1)))
Ejemplos:
F(0,x) = x+1
F(1,1) = F(0,F(1,0)) = F(0,F(0,0)) = F(0,1) = 2
F(1,2) = F(0,F(1,1)) = F(0,2) = 3
F(1,x) = F(0,F(1,x-1)) = … = F(0,x) = x+1
F(2,1) = F(1,F(2,0)) = F(1,F(1,1)) = F(1,2) = 3
F(2,x) = F(1,F(2,x-1)) = … = F(1,2x-1) = 2x+1
…
Definiciones recursivas primitivas
Ejemplo con un argumento:
F(x+1) = 2*F(x) F(x+1) = g(F(x))
F(0) = 1 F(0) = h
Definición general:
F(x1+1, x2, …, xn) = g(F(x1, x2, …, xn), x1, x2, …, xn)
F(0, x2, …, xn) = h(x2, …, xn)
Ejemplos: La definición de Ackerman no lo es
F(x+1,y) = F(x, y)+2
F(0,y) = y+2
Funciones recursivas primitivas: Funciones básicas
Las funciones recursivas básicas numéricas son:
Sucesor: s(x) = x+1
Anulación: n(x) = (x=0) ? 1 : 0
Proyecciones: uin(x1, …, xn) = xi
Funciones recursivas primitivas
Se pueden definir a partir de las básicas mediante recursión primitiva y composición
Ejemplos:
F(x) = s(s(x))
G(x+1, y) = F(G(x, y))
G(0,y) = F(y)
Composición
En general, si f(x1,…,xn), g1(y1,…,ym),…, gn(y1,…,ym) son funciones, diremos que la función
h(y1,…,ym) = f(g1(y1,…,ym),…,gn(y1,…,ym))
se obtiene a partir de ellas mediante composición.
En realidad corresponde a la composición de G con f, donde G es la función vectorial con coordenadas g1, …, gn.
Totalidad y computabilidad de las funciones recursivas primitivas
Si f es RP, es total
La función prev: N – { 0 } ? N definida mediante
prev(x+1) = x
no es total (y tampoco RP)
Las funciones RP son computables, pues tanto f(x)=y como f(x)?y se pueden determinar algorítmicamente en tiempo finito.
EJERCICIOS: Demostrar que las siguientes funciones son RP
[RPN1] fk(x) = k
[RPN2] suma(x, y)
[RPN3] restap(x, y) // Da 0 si y > x
[RPN4] producto(x, y)
[RPN5] restaabs(x, y) // |x-y|
[RPN6] positivo(x) // x > 0 ? 1 : 0
[RPN7] max(x, y)
[RPN8] min(x, y)
[RPN9] factorial(x)
[RPN10] potencia(x, y) // xy
[RPN11] par(x) // x = 2*(x/2) ? 1 : 0
EJERCICIOS: Demostrar que las siguientes funciones son RP
[RPN12] cocientedefecto(x, 2)
[RPN13] cocientedefectop(x, y) // (x, 0) ? 0
[RPN14] iguales(x, y)
[RPN15] menoroigual(x, y)
[RPN16] menor(x, y)
[RPN17] divisor(x, y)
[RPN18] primo(x)
[RPN19] restodivision(x, y)
[RPN20] primomayor(x) // Primero mayor
[RPN21] mcd(x, y)
[RPN22] mcm(x, y)
Funciones recursivas primitivas sobre cadenas de caracteres
Las funciones recursivas básicas sobre cadenas de caracteres son:
Anteposición: s?(x). Ejemplo: sa(“abc”)=“aabc”
Vacuidad: v?(x) = (x=?) ? ? : ?
Proyecciones uin(x1, …, xn) = xi
Ejemplos:
f??(x) = s?(s?(x))
g(?,y) = fab(y)
g(sa(x),y) = fab(g(x,y))
g(sb(x),y) = fba(g(x,y))
Funciones recursivas primitivas sobre cadenas de caracteres
Una recursión primitiva sobre cadenas está formada por |?|+1 reglas:
f(s?(w1),x2,…,wn) = g?(f(w1,w2,…,wn),w1,w2,…, wn)
f(0, w2, …, wn) = h(w2, …, wn)
donde cada g? y h son funciones recursivas primitivas.
Las funciones recursivas primitivas sobre cadenas también son totales y computables
Funciones recursivas primitivas sobre cadenas de caracteres
La función resto: ?+ ? ?* que elimina el primer carácter no es total ni, por lo tanto, recursiva primitiva
EJERCICIOS: Demostrar que las siguientes funciones son RP
[RPC1] fv(w) = v
[RPC2] start(v) // start(“ab”)=“a”, start(0) = 0
[RPC3] fin(v) // end(“ab”)=“b”, end(0)=0
[RPC4] cuenta?(v) // cuentaa(“abbaba”)=“aaa”
[RPC5] concatena(v, w)
[RPC6] invierte(v)
[RPC7] esPalíndrome(v)
[RPC8] esVacía(v)
EJERCICIOS: Demostrar que las siguientes funciones son RP
[RPC9] iguales(v, w)
[RPC10] contiene(v, w)
// contiene(“abcba”, “bcb”) = “a”
// contiene(“abcba”, “bab”) = 0
[RPC11] sustituye(u, v, w)
[RPC12] longitud(v)
// longitud(“abc”) = “aaa”
Funciones recursivas primitivas: Suma recursiva
Suponemos que f(n) es recursiva primitiva
g(m) = f(0) + f(1) + … + f(m)
g(0) = 0
g(m+1) = suma(g(m), f(s(m)) = h(g(m),m)
donde
h(x,y) = suma(x,f(s(y))
es primitiva recursiva, luego g también lo es.
Ejercicios
Suponemos que f(m) es recursiva primitiva. Demostrar que las siguientes funciones también lo son: [RPA1], [RPA2], [RPA3], [RPA4]
g(m,x) = min(f(0), f(1), …, f(m))
g(m,x) = f(f(…f(f(x))…)) // m concatenaciones de f
g(x) = 1 si ?m?x, f(m)=0, y g(x) = 0 en caso contrario
g(x) = 1 si ?m?x, f(m)=0, y g(x) = 0 en caso contrario
Totalidad y computabilidad de la función de Ackerman
F(i,x) = (i=0) ? x+1 : ((x=0) ? F(i-1,1) :
F(i-1,F(i,x-1)))
Es total
Es computable
Sin embargo, no es recursiva primitiva:
Fj(x) = F(j, x) = Fj-1(Fj-1(…(Fj-1(0)…))
Fx(x) crece más rápido que cualquier función de la sucesión f0(x)=x+1, fj+1(x)=fj(fj(…(fj(0)…))
Las funciones R.P. crecen como alguna de las funciones anteriores
Página siguiente  |