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?
Respuestas:
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.N string
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)
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 ) = 1P valid: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)=1⟺n∈P ev ev(m,n) m n
Ahora podemos introducir alguna terminología:
Son posibles otras definiciones de " interpreta L 2 ", pero no me permitas entrar en esto ahora.L1 L2
Decimos que y L 2 son equivalentes si se interpretan entre sí.L1 L2
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,φ) n∈N φ(n,m) n m ev
Nuestra definición de lenguajes de programación es muy relajada. Para que se cumpla lo siguiente, solicitemos tres condiciones más:
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 ↦u L L m∈P n∈N
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 ⟩ , mL′ L L ev P′={⟨0,n⟩∣n∈P}∪{⟨1,0⟩} ev′
Obviamente,L'es total porqueLes total. Para ver queL'puede simularLacaba de tomaru=⟨1,0
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.L′ L′ L
fuente
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.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.
fuente