Estoy presentemente estudiando las definiciones de funciones recursivas (primitivas, totales, parciales) a la par que conjuntos recursivos y recursivamente enumerables y me surgió la siguiente duda. Según comprendo, un conjunto \( A \) es recursivo si existe una función recursiva total \( f : \mathbb{N} \to 2 \) tal que \( A = f^{-1}(1) \) y \( A^\mathsf{c} = f^{-1}(0) \) (i.e. ésta es capaz de decidir si un cierto argumento natural pertenece o no al conjunto). A su vez, un conjunto \( A \) es recursivo enumerable si éste es el dominio de una función recursiva \( f \) (posiblemente parcial). Aquí tengo, no obstante, mis dudas, puesto que lo he visto también definirse como la imagen de una función recursiva total. ¿Es esto acaso equivalente?
Sí, en la propia página de wikipedia a la que haces referencia luego te dice que es equivalente. La idea es que si \( A \) es la imagen de la función recursiva total \( f \), entonces es el dominio de la función recursiva parcial \( g(n) = \mu m\, f(m)=n \). Recíprocamente, si \( A \) es el dominio de la función recursiva parcial \( g \), eso significa que (salvo un pequeño tecnicismo) existe una relación recursiva \( R \) tal que \( g(n) = \mu m\, R(n,m) \). Entonces puedes enumerar el conjunto \( A \) calculando en un cierto orden todas las relaciones \( R(n, m) \) y, cada vez que una resulta cumplirse, poner \( n \) en la enumeración.
Mi duda principal es respecto a la enumerabilidad recursiva de las funciones recursivas primitivas. Según entiendo, puede mostrarse que éstas son recursivamente enumerables.
Dicho así, resulta confuso, y en estos temas, cuanto menos confuso sea lo que se diga, mejor. Un conjunto recursivamente enumerable es un conjunto de números naturales, y las funciones recursivas primitivas no son, en principio, números naturales, así que no tiene sentido plantearse si son recursivamente enumerables.
Lo que sucede es que a cada función recursiva parcial \( f \) (en particular a las funciones recursivas totales y a las recursivas primitivas) se les puede asignar un código \( \hat f \) (o un número de Gödel, si prefieres llamarlo así), que es un número natural de modo que a partir de \( \hat f \) se puede reconstruir el algoritmo que calcula \( f \), y lo que se cumple es que el conjunto de los códigos de las funciones recursivas primitivas es recursivo.
Aquí hay un matiz sutil que puede ser relevante: Si llamamos \( C \) al conjunto de códigos de funciones recursivas primitivas, toda función recursiva primitiva tiene un código en \( C \), pero eso no excluye que un código de una función recursiva parcial, o recursiva total que no esté en \( C \) defina una función que podría ser recursiva primitiva, aunque no podamos asegurarlo.
Esto te permite enumerar en la práctica todas las funciones recursivas primitivas: si \( c_0, c_1, c_2, \ldots \) son los códigos de funciones recursivas primitivas, las funciones que determinan son una enumeración de todas las funciones recursivas primitivas.
En particular, que existe una función recursiva total (según sostiene Wikipedia) tal que éstas resultan ser su imagen.
Una vez más, conviene que seas preciso con estas cosas. La imagen de una función recursiva total es un conjunto de números naturales, luego no puede ser el conjunto de todas las funciones recursivas primitivas. Lo que sí que puedes enumerar es el conjunto de los códigos de funciones recursivas primitivas (y, por tanto, las funciones en sí). De hecho, ese conjunto es recursivo, no sólo recursivamente enumerable, pero eso no significa que, dada una función recursiva parcial, puedas saber si es o no recursiva primitiva, sino que dado un código de una función recursiva parcial, puedes saber si está o no en el conjunto \( C \) de códigos de funciones recursivas primitivas (los códigos que corresponden a definiciones que no usan minimización), pero si el código no está en \( C \), eso no te asegura que la función que codifica no sea recursiva primitiva, porque el uso de la minimización podría ser evitable.
Por un argumento por diagonalización, puede mostrarse que las funciones recursivas totales no son recursivamente enumerables. Si bien entiendo, puede argüirse de forma similar para mostrar que no existe ninguna función recursiva primitiva que enumere todas las funciones recursivas primitivas.
Sin embargo, este patrón en que la diagonalización excede los estratos crecientes de recursividad parece acabarse una vez se llega a las funciones recursivas (totales y parciales), acaeciendo que éstas sí son recursivamente enumerables (hecho que Gödel mismo describió como nada menos que un milagro).
Nuevamente, lo que sucede es que los códigos de las funciones recursivas parciales forman un conjunto recursivo. En particular, puedes enumerarlo: \( c_0, c_1, c_2,\ldots \) y la sucesión de funciones codificadas por ellos, \( f_0, f_1, f_2, \ldots \) es una enumeración de todas las funciones recursivas parciales que es calculable en la práctica. Más aún, puedes dar una función recursiva parcial \( F(m,n) \) tal que \( F(m, n) = f_m(n) \).
Mi intuición de por qué esto resulta plausible es, grosso modo, que ser capaz de decidir si una dada función recursiva f es total es una tarea dificultosa,
Dificultosa es decir poco. Es imposible en muchos casos.
que esencialmente requiere de medios externos/por fuera de la algoritmia (i.e. de una prueba). El problema es que, si bien los pasos para formar funciones recursivas nos están dados de manera recursiva, no somos capaces de saber a priori con certeza si, al aplicar la operación de minimización \( \mu \), la función resultado que obtendremos seguirá siendo total. Cuando consideramos todas las funciones (totales o parciales), esto ya no es un problema, puesto que sólo debemos entonces enumerar (siguiendo los pasos definicionales recursivos dados) cada una de las posibles construcciones.
Así es. Podemos enumerar todas las funciones recursivas parciales y todas las funciones recursivas primitivas, pero no todas las funciones recursivas, porque eso requiere distinguir si una función parcial es o no total. En el caso de las funciones recursivas primitivas no aparece el problema porque no se usa la minimización y las definiciones sin minimización siempre dan funciones totales.
Esta intuición es, a su vez, la que me lleva a pensar que el conjunto de las funciones recursivas primitivas debería ser recursivo (i.e. decidible), lo cual parece no ser cierto...
El conjunto de los códigos de funciones recursivas primitivas es recursivo, con el matiz que te he puesto antes.
Mi intuición es la siguiente: Al igual que con las funciones recursivas parciales, no debemos preocuparnos de "salirnos" del ámbito de las funciones recursivas primitivas si nos atenemos sólo a las construcciones recursivas que se nos ofrecen para definirlas. Puesto que comenzamos con unas ciertas funciones "base" (cero, sucesor, sendas proyecciones) y construimos recursivamente las demás funciones recursivas primitivas a partir de su empleo y la conjunción con las operaciones de composición y recursión primitiva, ¿qué exactamente nos impide decidir, dada una cierta función, si ésta efectivamente es —o no— recursiva primitiva?
Depende de cómo tienes determinada la función. Si la tienes definida de acuerdo con la definición de función recursiva primitiva, entonces obviamente es recursiva primitiva. Pero si la tienes definida usando minimización, puede ser recursiva primitiva, o no, y no tiene por qué ser fácil (o siquiera posible) determinarlo. Por ejemplo, considera la función: \( f(n) = \) el mínimo \( m \) tal que \( m \) es el número de Gödel de una demostración de que \( 0\neq 0 \) en ZFC más el axioma que afirma que existen \( n \) cardinales inaccesibles, y sea \( g(n) = c(f(n)) \), donde \( c \) es la función que siempre vale \( 0. \) Entonces \( g(n) \) es una función recursiva parcial que está definida (y vale 0) si y sólo si la teoría axiomática ZFC más la existencia de \( n \) cardinales inaccesibles es contradictoria. Si resulta que estas teorías son todas contradictorias, entonces es recursiva primitiva, pues es la función constante 0, que es recursiva primitiva, pero si alguna de ellas es consistente, entonces \( g \) es recursiva parcial estrictamente (es decir, no es total), pero es absolutamente imposible razonar cuál de los dos casos se da.
Mi idea es: Cualquier función recursiva primitiva tiene un "largo" o tamaño que podríamos definir en base a su número de variables (teniendo en cuenta el número infinito de funciones proyección base) y, claro, la cantidad de "composiciones" (en el sentido intuitivo) que ésta involucra. Entonces, dado un código que pretende (o no) representar una cierta función, ¿no podría examinarse el "tamaño" del mismo, y realizarse una búsqueda acotada por éste de todas las funciones recursivas primitivas hasta la altura designada, terminando por devolver \( 1 \) en caso de hallarse alguna que coincida con el argumento, y \( 0 \) de lo contrario?
No entiendo esto, pero, como hablas de funciones de varias variables, aprovecho para aclarar que, por simplicidad, he considerado funciones de una variable, pero todo lo que he dicho vale igualmente si consideramos funciones de varias variables, con cambios mínimos.
