Un lenguaje total que solo un lenguaje completo de Turing puede interpretar

16

Cualquier lenguaje que no esté completo no puede escribir un intérprete para sí mismo. No tengo idea de dónde lo leí, pero lo he visto varias veces. Parece que esto da lugar a una especie de lenguaje completo "Turing" no Turing completo; la (s) que solo puedenser interpretado por una máquina de Turing. Estos lenguajes no serían necesariamente capaces de calcular todas las funciones totales de naturales a naturales ni serían necesariamente isomórficos (es decir, tal vez los lenguajes finales A y B existen de tal manera que existe una función F que A puede calcular pero B no puede). Agda puede interpretar el sistema T de Godel y Agda es total, por lo que un lenguaje tan avanzado debería ser estrictamente más poderoso que el sistema T de Godel. Me parece que tal lenguaje sería al menos tan poderoso como el agda también (aunque no tengo evidencia, solo una corazonada).

¿Se ha realizado alguna investigación en este sentido? ¿Qué resultados se conocen (es decir, se conoce un lenguaje tan "definitivo")?

Bonificación: me preocupa que exista un caso patológico que no puede calcular funciones que el Sistema T de Godel todavía puede ser interpretado solo por una máquina de Turing porque permite calcular algunas funciones realmente extrañas. ¿Es este el caso o podemos saber que ese lenguaje podría calcular cualquier cosa que el Sistema T de Godel pudiera calcular?

Jake
fuente
2
Sus declaraciones son confusas debido a la forma en que utiliza la terminología. En lugar de confiar en la terminología, intente formular su pregunta de manera matemáticamente rigurosa y clara para que podamos entender su pregunta. ¿Qué quiere decir con lenguaje de programación en el contexto de la teoría de la computabilidad? ¿Te refieres a una enumeración de funciones computables?
Kaveh
1
Mi suposición sobre lo que lees: si un lenguaje es lo suficientemente fuerte y contiene la función universal de otra clase de funciones, entonces puede definir la función diagonal para esa clase. Si es una clase de funciones totales, entonces la función diagonal no puede estar en la clase.
Kaveh
Fue declarado informalmente donde lo encontré. Algo literalmente similar a lo que di aquí. Tampoco sé cómo decir esto de manera matemática. Después de leer un poco, no estoy seguro de cuál es la "función diagonal de una clase de funciones". Creo que en sus términos lo que quiero decir es que "una clase de funciones totales no puede contener su propia función universal" y por eso creo que estoy preguntando "qué clase de funciones totales C es el caso de que ninguna clase de funciones totales contenga función universal para C ". Si entiendo qué es una "función universal", creo que es correcta.
Jake
1
Estrictamente hablando, esta no es una pregunta de nivel de investigación. Además, ¿por qué es una wiki comunitaria? ¿O es eso?
Andrej Bauer
"Parece que esto da lugar a un tipo de lenguaje completo" definitivo "que no tiene trucos; el que solo puede ser interpretado por una máquina de Turing". no sigas esa afirmación, parece un non sequitur, ¿qué quieres decir, por qué eso parece?
vzn

Respuestas:

42

Esta es una pregunta mal formulada, así que primero tengamos sentido. Voy a hacerlo al estilo de la teoría de la computabilidad. Por lo tanto, usaré números en lugar de cadenas: un fragmento de código fuente es un número, en lugar de una cadena de símbolos. Realmente no importa, puede reemplazar con s t r i n g a continuación.Nstring

Deje ser una función de emparejamiento .m,n

Digamos que un lenguaje de programación viene dado por los siguientes datos:L=(P,ev)

  1. un conjunto decidible de "programas válidos", yPN
  2. un computable y parcial función .ev:P×NN

El hecho de que sea ​​decidible significa que hay un mapa computable total v a l i d : N{ 0 , 1 } tal que v a l i d ( n ) = 1Pvalid:N{0,1} . Informalmente, estamos diciendo que es posible saber si una cadena dada es un código válido. La función e v es esencialmente un intérprete para nuestro lenguaje: e v ( m , n ) ejecuta el código m en la entrada n - el resultado puede ser indefinido.valid(n)=1nPevev(m,n)mn

Ahora podemos introducir alguna terminología:

  1. Una lengua es total de si es una función total para todo m P .nev(m,n)mP
  2. Un lenguaje interpreta el lenguaje L 2 = ( P 2 , e v 2 ) si existe u P 1 de tal manera que e v 1 ( u , n , m ) e v 2 ( n , m ) para todos n PL1=(P1,ev1) L2=(P2,ev2)uP1ev1(u,n,m)ev2(n,m)nPy . Aquí u es el simulador de L 2 implementado en L 1 . También se conoce como el programa universal para L 2 .mNuL2L1L2

Son posibles otras definiciones de " interpreta L 2 ", pero no me permitas entrar en esto ahora.L1L2

Decimos que y L 2 son equivalentes si se interpretan entre sí.L1L2

Existe el lenguaje "más poderoso" de las máquinas de Turing (al que se refiere como "una máquina de Turing") en el que n N es una codificación de una máquina de Turing y φ ( n , m ) es la función computable parcial que "ejecuta la máquina de Turing codificada por n en la entrada m ". Este lenguaje puede interactuar con todos los demás idiomas, obviamente ya que requerimos que e v sea ​​computable.T=(N,φ)nNφ(n,m)nmev

Nuestra definición de lenguajes de programación es muy relajada. Para que se cumpla lo siguiente, solicitemos tres condiciones más:

  • implementa la función sucesora: hay s u c c P tal que e v ( s u c c , m ) = m + 1 para todos m N ,LsuccPev(succ,m)=m+1mN
  • implementa la función diagonal: Hay d i un g P tal que e v ( d i un g , m ) = m , m para todos m N ,LdiagPev(diag,m)=m,mmN
  • está cerrado bajo la composición de funciones: si L implementa f y g, entonces también implementa f g ,LLfgfg

Un resultado clásico es este:

Teorema: si un lenguaje puede interpretarse a sí mismo, entonces no es total.

Prueba. Supongamos que es el programa universal para un total de langauge L implementado en L , es decir, para todos m P y n N , e v ( u , m , n ) e v ( m , n ) . Como sucesor, diagonal y e v ( u , - ) se implementan en L , también lo es su composición k uLLmPnN

ev(u,m,n)ev(m,n).
ev(u,)L . Existe n 0P tal que e v ( n 0 , k ) e v ( u , k , k ) + 1 , pero entonces e v ( u , n 0 , n 0) e v (kev(u,k,k)+1n0Pev(n0,k)ev(u,k,k)+1 Como no hay un número igual a su propio sucesor, se deduce que L no es total o que L no interprete a sí misma. QED
ev(u,n0,n0)ev(n0,n0)ev(u,n0,n0)+1
LL

Observe que podríamos reemplazar el mapa sucesor con cualquier otro mapa sin punto fijo.

Aquí hay un pequeño teorema que creo que aclarará un malentendido.

Teorema: todo lenguaje total puede ser interpretado por otro lenguaje total.

Prueba. Sea ) = { e v ( n , m ) si  b =L sea ​​un lenguaje total. Obtenemos un total que interpreta L al unirse a L su evaluador e v . Más precisamente, dejar que P ' = { 0 , n | n P } { 1 , 0 } y definir e v ' como e v ' ( b , n , mLLLevP={0,nnP}{1,0}ev Obviamente,L'es total porqueLes total. Para ver queL'puede simularLacaba de tomaru=1,0

ev(b,n,m)={ev(n,m)if b=0,ev(m0,m1)if b=1 and m=m0,m1
LLLL , Desde entonces e v ' ( u , m , n ) e v ( m , n ) , según se requiera. QEDu=1,0ev(u,m,n)ev(m,n)

Ejercicio: [agregado 2014-06-27] El lenguaje construido anteriormente no está cerrado bajo composición. Arregle la prueba del teorema para que L ' satisfaga los requisitos adicionales si L lo hace.LLL

LLLLLL

Andrej Bauer
fuente
Si marqué la casilla de verificación wiki no fue intencional.
Andrej Bauer
2
¿Hay algún poder adicional en los idiomas en los que no se puede saber si un programa determinado es válido o no?
Phylliida
3
@DaniPhye: si la sintaxis del lenguaje no es semidecidible, puede "ocultar" el poder computacional en la sintaxis. Por ejemplo, las reglas del lenguaje podrían requerir que cada función esté equipada con un bit que indique si la función es total. Entonces podríamos implementar is_total, lo que de otra manera no es imponible, pero no podríamos implementar la evaluación (porque también tendrías que calcular el bit de la función resultante). En general, diría que no es un lenguaje de programación si ni siquiera puede implementar un analizador para él.
Andrej Bauer
3
¿Cómo "si un idioma puede interpretarse a sí mismo, entonces no es total" con este resultado: un autointerpretador para F-omega ?
Cactus
18

Cualquier lenguaje que no esté completo no puede escribir un intérprete para sí mismo.

Esta afirmación es incorrecta. Considere el lenguaje de programación en el que la semántica de cada cadena es "Ignore su entrada y pare inmediatamente". Este lenguaje de programación no está completo, pero cada programa es un intérprete para el lenguaje.

David Richerby
fuente
Ah! Ese es un buen punto. Por lo tanto, debe haber ciertos requisitos sobre lo que computa el lenguaje. Parece que se debe hacer algún requisito mínimo sobre el poder del lenguaje para hacer que esa afirmación sea verdadera. Parece que si exigimos que sea capaz de resolver problemas aritméticos básicos, entonces podría funcionar.
Jake
@Jake Es posible que puedas salirte con la tuya con algo increíblemente débil como "el lenguaje define al menos una función no constante" o "el lenguaje define más de una función". Mi contraejemplo es claramente trivial para cualquier definición razonable de "trivial".
David Richerby
Parece un problema interesante para mí. Si encuentro algo, responderé.
Jake