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 |