Recuerda que en las ciencias informáticas un problema puede tener más de una resoluciones, no obstante enseñaremos lo más óptimo y mejor.
Solución:
No son equivalentes. El ejemplo estándar es la función de Ackermann, que es recursiva (total), pero no recursiva primitiva. Pero si eres un programador, aquí tienes otra forma de pensar en la diferencia entre funciones recursivas totales y recursivas primitivas. Discutiré esto en términos de un lenguaje de programación imperativo idealizado que se ejecuta en una computadora idealizada (sin límites de memoria o almacenamiento). Puede pensar en términos de cualquier lenguaje imperativo estándar, como C o Java.
Una función recursiva total es cualquier función que puede escribir y que siempre termina.
Una función recursiva primitiva es cualquier función que puede escribir donde los únicos bucles son los de la forma “para i = 1 an do …” Aquí $ n $ se fija de antemano (antes de que comience el bucle), y no puede ( explícitamente) cambie $ i $ ni $ n $ dentro del ciclo. Entonces, el número de veces que se ejecuta el ciclo se determina de antemano. Esta es la única estructura de bucle permitida. No tiene un bucle while, que termina en función de una condición, o una instrucción goto que puede volver a un punto arbitrario en el código, o llamadas de función recursivas. Estas condiciones hacen que los bucles infinitos sean imposibles.
Un ejemplo de un lenguaje de programación que solo admite funciones recursivas primitivas es BlooP (esto significa Bounded Loop). Es imposible escribir un bucle infinito en BlooP, mientras que es indecidible si un programa general termina.
Sin embargo, aunque todos los programas BlooP terminan, hay programas terminados que no se pueden escribir en BlooP. La función de Ackermann es una de ellas. El ejemplo más simple, sin embargo, es el Intérprete BlooP. Este es un programa que toma como entrada un programa BlooP más cualquier entrada que requiera el programa BlooP, luego ejecuta el programa BlooP y produce su salida. Dado que los programas BlooP siempre terminan, el intérprete siempre termina también. Pero no se puede escribir en BlooP, mediante un argumento de diagonalización.
A grandes rasgos, el argumento de la diagonalización es el siguiente: Para simplificar, asumiremos que todas las funciones asignan números naturales a números naturales. (Se pueden simular otros tipos de entradas mediante una codificación de Goedel). Sea $ B_1, B_2, ldots $ una lista recursiva de todos los programas BlooP y establezca $ f (n) = B_n (n) + 1 $. Dado que cada $ B_n $ termina, $ f $ siempre termina también y, por lo tanto, es totalmente recursivo. Pero $ f ne B_n $ para cualquier $ n $, ya que difieren en el valor $ n $ por construcción. Entonces $ f $ ya es un ejemplo de una función recursiva total, no recursiva primitiva (es decir, no expresable en BlooP). Pero dado que el único obstáculo para calcular $ f $ es el cálculo de $ B_n (n) $, que puede ser realizado por un intérprete, se deduce que el intérprete BlooP no se puede escribir en BlooP.
Hay otro ejemplo de una función computable no primitiva recursiva pero total que explica mejor lo que implica la definición restringida de recursividad primitiva.
Cada función recursiva primitiva está definida por un conjunto finito particular de ecuaciones de recursión, en términos de un conjunto fijo de funciones básicas. Podemos usar esto para definir un esquema efectivo para indexar todas las funciones recursivas primitivas. Sea $ (f_e: e in mathbb N) $ una indexación efectiva de las funciones recursivas primitivas unarias, lo que significa que
-
Cada función recursiva primitiva unaria tiene la forma $ f_ e_f (n) $ para algunos $ e_f $ fijos.
-
Hay un solo algoritmo para calcular $ f_e (n) $ dados $ e $ y $ n $.
Sea $ g (e, n) $ la función que calcula $ f_e (n) $. Llamamos $ g $ a universal función binaria. Es universal en el sentido de que encapsula todas las funciones recursivas primitivas unarias.
La función $ g (e, n) = f_e (n) $ es ciertamente una función computable total. Pero no es recursivo primitivo:
Suponga que $ g (e, n) $ es primitivo recursivo. Entonces, la función $ f (n) = g (n, n) + 1 $ también es primitiva recursiva, como puede verificar. Pero esta función $ f (n) $ no puede tener la forma $ g (e, n) $ para cualquier $ e $ fijo, porque por cada $ e $ tenemos $ f (e) = g (e, e) + 1 not = g (e, e) $, según la definición de $ f $. Por tanto, $ g $ es total computable pero no primitivo recursivo.
Esta prueba de diagonalización se puede utilizar en cualquier sistema que se cierre bajo unas pocas operaciones básicas. La moraleja de esta construcción es una key hecho en la teoría de la computabilidad:
Un sistema de funciones en el que cada función es total, y que tiene ciertas propiedades de cierre básicas, no puede incluir una función binaria universal (total). Las propiedades básicas del cierre son las que se utilizan en la prueba anterior.
El punto es que existe una incompatibilidad fundamental entre el objetivo de hacer un sistema lo suficientemente concreto como para que cada función sea total, y hacer un sistema lo suficientemente fuerte como para que incluya funciones universales para sí mismo. Solo se puede lograr uno de estos objetivos a la vez.
Existe una función parcial binaria universal para el conjunto de funciones computables totales unarias. De hecho, existe una función parcial binaria universal para el conjunto de funciones computables parciales unarias, una clase más grande. Este hecho es esencialmente equivalente a la existencia de una máquina de Turing universal.
La función de Ackermann, por ejemplo, es recursiva, pero no es recursiva primitiva. De hecho, “crece más rápido” que cualquier función recursiva primitiva. A partir de la definición del enlace, no es difícil escribir un programa explícito que calcule la función de Ackermann. Hay muchos otros ejemplos concretos. La clase de funciones recursivas primitivas es una pequeña subclase de la clase de funciones recursivas.
Agradecemos que quieras corroborar nuestra labor poniendo un comentario y dejando una valoración te damos la bienvenida.