Este es un seguimiento de otra pregunta aquí , y espero que no sea demasiado filosófico. Como señaló Raphael en un comentario sobre mi pregunta anterior, realmente no entiendo la definición de "computable", pero de acuerdo con algunos documentos que leí, la definición tampoco está muy clara cuando se trata de modelos de computación más débiles que turing máquinas debido a la codificación de la entrada y salida.
La definición típica de turing computable es la siguiente:
Definición 1: Una función se llama turing computable si hay una máquina turing que computa utilizando una codificación adecuada de los números naturales como cadenas.f
Las definiciones difieren en qué es exactamente una codificación adecuada , pero la mayoría se refiere a la codificación binaria , codificación unaria o codificación decimal como la codificación fija y adecuada. También es posible mostrar que se requiere la fijación de una codificación para la definición de computabilidad de turing. Pero, ¿qué hace que la codificación binaria de números naturales sea especial para que podamos axiomatizarla como la codificación adecuada? Probablemente porque se ajusta a la noción intuitiva de lo que significa computabilidad por coincidencia .
¿Y si observamos modelos de computación más débiles que las máquinas de Turing? Por ejemplo, consideremos el conjunto de máquinas de turing "paralizadas" con el alfabeto que solo puede moverse hacia la derecha, y una definición de turing paralizado computable que es consistente con la de computabilidad de turing: { 0 , 1 }
Definición 2: Una función se llama tullida turing computable o computable en si hay una máquina turing tullida que computa usando una codificación adecuada de los números naturales como una cuerda.f
Si definimos "codificación adecuada" como "codificación binaria", entonces la función no es computable en . Si axiomatizamos "codificación adecuada" como "codificación unaria", entonces es computable en . Esto parece extraño dado el hecho de que todos pueden arreglar una de las infinitas codificaciones intuitivas a voluntad. Debe quedar claro si un modelo de computación puede computar o no sin referirse a alguna codificación específica; al menos, nunca he visto a nadie mencionar qué codificación se usa al afirmar que "los programas de bucle son más débiles que las máquinas de turing".M c f M c f
Después de esta introducción, finalmente puedo formular mi pregunta: ¿Cómo definiría "codificaciones adecuadas" y "computabilidad" para modelos arbitrarios de computación que no coinciden con la noción intuitiva de computabilidad? ¿Es esto posible en el marco de la computabilidad de turing?
Editar: acorté la introducción, no se agregó a la pregunta.
fuente
En primer lugar, no puede corregir la "codificación adecuada" para que sean cadenas binarias o cualquier otra codificación. Esto se debe a que perdería demasiados modelos de computación, porque diferentes modelos de computación pueden tener modelos muy diferentes de entrada y salida. En otras palabras, no pueden "hablar" cadenas.
Por ejemplo, los términos del cálculo lambda sin tipo son variables, o la aplicación de un término a otro, o una abstracción de un término lambda. Entrada y salida son términos, cadenas arbitrarias. Aún así, el cálculo lambda sin tipo es completo de Turing porque existe una "codificación adecuada" que codifica los números naturales como términos lambda de una determinada forma, y bajo esta codificación para cada función computable existe un término lambda que lo computa.
Puede formalizar la "codificación adecuada" si fija las máquinas de Turing como su modelo de cálculo de referencia, y luego requiere que la codificación y decodificación desde y hacia cadenas binarias sea realizada por una máquina de Turing que siempre se detiene. Por ejemplo, una máquina de Turing podría traducir un número natural como una cadena binaria a un término Lambda que exprese este número, simular la reducción en el cálculo lambda y traducir el resultado nuevamente a una cadena binaria.
Para modelos de computación más simples, esperaría el mismo enfoque: tome un modelo de computación de referencia y arregle una codificación de los números naturales, y luego asegúrese de que la codificación y decodificación se realice por instancias de ese modelo simple. Como notó, para las máquinas Turing paralizadas, el uso de números codificados unarios y binarios no produciría un modelo equivalente de cálculo.
fuente