En mucho de la literatura he encontrado que las funciones recursivas primitivas son recursivamente enumerable (r.e.), pero el total de la recursivo no. Entonces, el conjunto al que pertenecen?
Me estoy preguntando desde que me enteré de que incluso la paralización problema está en r.e.
Gracias por la comprensión!
Resumen: el total de funciones recursivas no son recursivamente enumerables; la prueba de la siguiente manera a partir de un típico argumento diagonal.
"Recursivamente enumerable" es una propiedad de un conjunto de números enteros. "Parciales recursivas" o "total recursiva" o "primitivas recursivas" son propiedades de las funciones de enteros a enteros. Los conceptos no son exactamente en el mismo plano. Luego también está el VOLVER a la complejidad de la clase, que es una clase de funciones de algunos dominio del problema a booleanos; diciendo que la decisión de problema está en RE es equivalente a decir que el lenguaje que reconoce es recursivamente enumerable, si el idioma está codificado en los enteros.
No es posible codificar todas las funciones como enteros (por una diagonal argumento, el conjunto de todas las funciones de enteros a enteros es incontable y por lo tanto usted no puede encontrar una clara entero para cada función).
Por otro lado, es posible codificar todas las funciones recursivas parciales como los números enteros, por ejemplo, mediante la escritura de estas funciones en un lenguaje de programación y lectura de los bytes que componen el código fuente como los dígitos de un número entero en base 256 (hay muchos programas que implementan cada función, por supuesto, así que escoge el que le da el entero más pequeño). Tenga en cuenta que un sistema de codificación debe ser uno-a-uno, pero no tiene que ser surjective. Si usted toma un particular ejemplo de codificación (cualquier "sensible" a uno le dan resultados equivalentes en la final), entonces se puede considerar una clase de las funciones recursivas (la clase de todas las funciones recursivas parciales, la clase de las funciones recursivas primitivas, la clase de constante funciones, etc.) y preguntar qué tipo de propiedades el conjunto de todas las codificaciones de tales funciones.
El conjunto de codificaciones parciales de funciones recursivas es recursivamente enumerable. Como en el anterior, considere el código fuente de las funciones expresadas en una idealizada lenguaje de programación. Las fuentes de un programa son fáciles de enumerar: ordenar las cadenas de longitud, a continuación, en orden lexicographic, y omitir las que no son sintácticamente bien formadas (este es un decidable procedimiento). Una enumeración de las funciones recursivas parciales (cada función será alcanzado un número infinito de veces en la enumeración, ya que hay infinidad de maneras de implementarla).
Por otro lado, el conjunto de codificaciones del total de funciones recursivas no es recursivamente enumerable. Como a menudo, la prueba se basa en un argumento diagonal. Deje $E(f)$ ser la codificación de una función de $f$ $F(x)$ ser la preimagen de $x$ si es que existe (es decir,$E(F(x))=x$). Supongamos que hay una enumeración $r$ de todas las codificaciones de las funciones recursivas, es decir, una función recursiva $r : \mathbb{N} \mapsto \mathbb{N}$ tal que para cualquier total función recursiva $f$, no es un número entero $x$ tal que $r(x)=E(f)$. Definir una función $h : \mathbb{N} \mapsto \mathbb{N}$$h(x) = F(r(x))(x) + 1$. A continuación, $h$ no es una función recursiva (de lo contrario no sería un poco de $x$ tal que $h = F(r(x))$). Sin embargo, debido a $r$ es recursivo, $h$ total recursiva. La suposición de que el conjunto de codificaciones del total de funciones recursivas es recursivamente enumerable es, pues, falso.
Si usted toma la clase de todas las funciones recursivas primitivas, entonces resulta que el conjunto de codificaciones es recursivamente enumerable. En otras palabras, usted puede hacer una lista de todas las funciones recursivas primitivas. La idea es bastante similar al caso de las funciones recursivas parciales anteriores. No hay ningún procedimiento de decisión que, dado un programa fuente, se puede determinar si es el origen de una primitiva de la función recursiva (en general, no existe tal procedimiento de decisión para no trivial de la propiedad - este es el Arroz del teorema). Pero recordemos que cada función puede ser implementado en (infinitamente) de muchas maneras: es suficiente para enumerar una implementación de cada función. Por definición, cualquier primitiva recursiva de la función puede ser expresada con las proyecciones, constantes, la función sucesor, composición y primitivo de la recursividad. Si una expresión es de esta forma es fácilmente decidable (es una gramática independiente del contexto, además de una verificación de que los nombres de las variables se utilizan correctamente). Así que hay una manera de enumerar un conjunto que contiene el código fuente de cada primitiva recursiva de la función, y sólo contiene el código fuente de las funciones recursivas primitivas. Esto proporciona una enumeración del conjunto de todas las codificaciones de las funciones recursivas primitivas.
(La enumeración de las funciones recursivas primitivas por encima de las listas de cada función muchas veces, por ejemplo la identidad de la función aparece también como $x \mapsto x+0$, $x \mapsto S(S(S(x) \times 1)-3))$, etc. Curiosamente, es posible, pero es mucho más difícil, al enumerar las funciones recursivas primitivas, sin duplicación, incluso a pesar de que la igualdad de primitivas de funciones recursivas no es decidable. Ver Las Funciones Recursivas Primitivas son Recursivamente Enumerables por Stefan Kahrs).
P. S. "no Podemos decir que para algunos no primitivas no detener la función es en el conjunto de primitivos": true, pero que tienden a indicar que las funciones recursivas primitivas son no r.e.; como se ha visto anteriormente, son, porque es suficiente para encontrar una forma de expresar la función que podemos decir es primitiva recursiva. "Si el total de las funciones recursivas son no-r.e., eso significa que su complemento es en r.e.": no, eso está mal, el no-total-funciones recursivas no son recursivamente enumerables; la detención problema no es semi-decidable de cualquier manera.
Gilles, estoy de acuerdo en que el conjunto de todos los programas (es decir, el código fuente) que finitely expresar la clase del total de funciones recursivas no es recursivamente enumerable (o llamado computably enumerable). Pero la clase del total de funciones recursivas en sí es recursivamente enumerable. He aquí una prueba:
Dejar que una máquina de Turing M enumerar todas las funciones recursivas parciales. Para cada paso, se simula el programa de p en el i th entrada para j pasos. Si p se detiene con un resultado k, entonces se genera un registro <p, i, k, m> y aumenta el número de m por 1, aquí m sirve como índice del registro. Si p no se detiene, que no genera nada y pasa al siguiente paso para continuar con el proceso de enumeración.
Dado un tiempo en el futuro, M genera un conjunto finito de tales registros, cada uno de los cuales tiene un índice único m. Cuando nos ordenar todos los registros en el orden sintáctico (o números de Gödel) de los programas, se puede obtener un conjunto de registros que comparten el mismo programa p. Tal conjunto no constituyen la completa, pero un subconjunto de las propiedades de p.
Cuando dejamos que M se ejecuta para siempre, es decir, en countably infinitos pasos, se podría eventualmente generar la totalidad de los registros que constituyen la clase completa de el total de funciones recursivas. (En consecuencia, al final del tiempo infinito, por supuesto que nunca llega, todos los registros que comparten el mismo p , constituyen la totalidad de las propiedades de p.)
Este conjunto es muy especial. No resuelve el cese problema a menos que esperaron hasta el final del tiempo infinito. Representa estrictamente un subconjunto del total de funciones recursivas en cualquier momento dado en el futuro. Pero progresivamente se acumula más y más registros, y, finalmente, converge a la completa de propiedades de el total de funciones recursivas. Este conjunto es recursivamente enumerable.
Por el camino, y la diagonal de método que usa, sólo muestra que hemos innumerables total de funciones en el número teórico de la teoría, mientras que el total de las funciones recursivas son contables. Una multitud innumerable ciertamente no es recursivamente enumerable.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
