¿Qué es un ejemplo de subconjunto enumerable de forma recursiva de los números naturales, que no es recursivo?
Respuestas
¿Demasiados anuncios?
El conjunto de fórmulas universalmente válidas de la lógica de primer orden se convierte en un ejemplo, si el índice de fórmulas de números naturales en una computable. Esto se llama Iglesia del teorema, después de Alonzo Church. Él lo demostró en la década de 1930. Esto significa que, si bien no es un equipo rápido de la prueba de comprobación de algoritmo, no hay ayuno de prueba para encontrar el algoritmo.
El conjunto de ecuaciones polinómicas en varias variables con coeficientes enteros que han entero de soluciones es otro ejemplo. Eso se llama Matiyasevich del teorema. Se probó en 1970 por Uri Matiyasevich, que se basan en trabajos anteriores de Julia Robinson, Hillary Putnam, y Martin Davis. Desecha de Hilbert del décimo problema.
Justin Bennett
Puntos
2513
Establecer un esquema de codificación para Máquinas de Turing que trabajan en la entrada binaria con un vacío al principio de la entrada de la cinta utilizando un alfabeto con k símbolos-como {'(', ')', '0', '1', 'B', ',', ...}.
Podemos entonces programación (que es, computably) convertir cada codificado máquina de Turing a un número entero por el tratamiento de la codificación de la cuerda sobre el k símbolos como un k-ary entero. Por ejemplo, la cadena "(B)01" convierte el entero 15234 (podemos saltar 0 para evitar el cero complicaciones, por lo que es realmente un (k+1)-ary entero). Que cadena de caracteres en particular, probablemente no es la sintaxis correcta de la Máquina de Turing de codificación, pero muestra cómo hacer la conversión: '(' se convierte en 1, ')' se convierte en 2, '0' se convierte en 3, etc.
Los números enteros se obtiene que corresponden a sintácticamente correcto de la Máquina de Turing codificaciones será recursivo conjunto de números enteros, decir T (que puede ser revisado por un TM "compilador"). Pero el subconjunto H de T correspondiente a la TMs que detener cuando en realidad no será recursivo, pero va a ser recursivamente enumerable.
