¿Existe una definición clara de "computable" para los modelos de cómputo que no están completos?

9

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 F:norteknorte se llama turing computable si hay una máquina turing que computa utilizando una codificación adecuada de los números naturales como cadenas.fMETROF

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 }METROC{0 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:norteknorteMETROCfMETROF

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 fF:nortenorte,nortenorte+1METROCF METROCF


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.

Stefan Lutz
fuente

Respuestas:

6

Un hecho básico que falta aquí es que todas las codificaciones que menciona son equivalentes desde la perspectiva de la computabilidad: hay una función computable que asigna la codificación binaria de un número a su codificación unaria, o viceversa. Por lo tanto, para definir la computabilidad, no importa cuál de estas codificaciones elija para los números. Simplemente arregle su codificación favorita.

La computabilidad es, en esencia, una propiedad de las funciones de cadena . Cuando define la computabilidad en cualquier otro dominio, debe corregir una codificación. En la práctica, todas las codificaciones "razonables" son equivalentes en el sentido del párrafo anterior, por lo que la codificación exacta no importa.F:ΣΣ

Sin embargo, la codificación sí importa en modelos restringidos de cómputo. Para tomar un ejemplo extremo, suponga que considera máquinas de Turing con restricción de tiempo: digamos que desea que su máquina termine en el tiempo para alguna c , donde n es la longitud de la entrada (como una cadena). Ya no podemos cambiar entre codificación binaria y codificación unaria, porque la codificación binaria es mucho más compacta. Cuando hablamos de una función computable de tiempo polinomial de enteros , especificamos que los enteros están codificados en binario. Incluso esta es una elección algo arbitraria, ya que la codificación decimal conduciría a la misma noción de computabilidad del tiempo polinomial.O(norteC)Cnorte

Entonces, para responder a su pregunta, la codificación se especifica como parte de la definición del modelo restringido.

Yuval Filmus
fuente
"Un hecho básico que te falta aquí es que todas las codificaciones que mencionas son equivalentes desde la perspectiva de la computabilidad: hay una función computable que asigna la codificación binaria de un número a su codificación unaria, o viceversa" - sí, yo tenía eso en la versión original de mi pregunta, pero no puedo ver cómo es relevante para la pregunta sobre modelos más débiles. También está claro que la codificación debe especificarse como parte de la definición del modelo, pero la pregunta es cómo se puede llegar a una definición tan razonable.
Stefan Lutz
1
Uno saca esta definición del sombrero. Dado que las diferentes definiciones tienden a ser equivalentes, la definición exacta no importa. Cuando lo haga, habrá varias nociones diferentes de complejidad. Por ejemplo, para algunos algoritmos gráficos hace una diferencia si se le da una matriz de adyacencia o una lista de aristas.
Yuval Filmus
Para resumir: a) La definición de cada modelo de cómputo individual debe incluir sintaxis, semántica Y una codificación adecuada. b) La definición de "codificación adecuada" es completamente independiente de la sintaxis y la semántica del modelo. c) No hay forma de dar una definición de "codificación adecuada" que sea válida para todos los modelos de computación. ¿Es eso correcto?
Stefan Lutz
Estoy de acuerdo con a) yb), pero con c) solo parcialmente. Puede definir una codificación adecuada que sirva como la "codificación estándar", utilizada a menos que se haga una mención explícita del hecho. En el caso de los números, existe una codificación estándar de este tipo: codificación binaria.
Yuval Filmus
METRO
4

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.

Hoopje
fuente
¿Es posible que haya cambiado las cosas en el último párrafo? Escribe que la codificación se realiza mediante el modelo simple, no el modelo de referencia; en el párrafo anterior desea que la codificación se realice mediante el modelo de referencia, no el otro modelo (cálculo lambda).
Stefan Lutz
Si está estudiando modelos de computación más débiles, no desea usar máquinas Turing en ningún lado, ni siquiera en la fase de codificación / decodificación. Entonces podría realizar todos los cálculos en la fase de codificación y cualquier modelo de cálculo estaría completo. Por lo tanto, debe usar el modelo de referencia más simple para codificar / decodificar.
Hoopje
1
nortenorteChturCh:nortelunametrosireunatmirmetroChturCh(norte)tosiyonorteunary:lunametrosireunatmirmetrolunametrosireunatmirmetrowΣ