computer-science language-design turing-complete

computer science - ¿Cuáles son las pautas prácticas para evaluar el "Turing Completeness" de un idioma?



computer-science language-design (13)

He leído "what-is-turing-complete" y la página de wikipedia, pero estoy menos interesado en una prueba formal que en las implicaciones prácticas de ser Turing Complete.

Lo que estoy tratando de decidir es si el lenguaje de juguetes que acabo de diseñar podría usarse como lenguaje de propósito general. Sé que puedo demostrar que es así si puedo escribir una máquina de Turing con él. Pero no quiero pasar por ese ejercicio hasta que esté bastante seguro de éxito.

¿Existe un conjunto mínimo de características sin las cuales la integridad de Turing es imposible? ¿Existe un conjunto de características que prácticamente garantiza la integridad?

(Mi suposición es que la bifurcación condicional y una memoria legible / escribible me llevarán la mayor parte del camino)

EDITAR:

Creo que me he ido en una tangente diciendo "Turing Complete". Intento adivinar con razonable confianza que un lenguaje recientemente inventado con un determinado conjunto de características (o alternativamente, una máquina virtual con cierto conjunto de instrucciones) podría calcular cualquier cosa que valga la pena calcular. Sé que probar que puedes construir una máquina de Turing es una forma, pero no la única.

Lo que esperaba era un conjunto de pautas como: "si puede hacer X, Y y Z, probablemente pueda hacer cualquier cosa".

No estoy seguro de si hay un "conjunto mínimo de características", pero para demostrar que un idioma está completo, solo debe probar que puede emular otro sistema completo de Turing (no necesariamente una máquina de Turing), siempre que el se sabe que otro sistema está completo. http://en.wikipedia.org/wiki/Turing_complete#Examples tiene una lista completa de los sistemas completos de Turing. Algunos de ellos son más simples que las máquinas de Turing.

... que en las implicaciones prácticas de ser Turing completo.

Dudo que haya implicaciones prácticas de ser Turing completo.

Si nos fijamos en algunos de los ejemplos de máquinas completas de Turing, por ejemplo, la máquina original de Turing , verá que están lejos de ser útiles para los cálculos reales de que el concepto solo debe ser de interés teórico.

Los ejemplos de lenguajes que no son Turing-completos frecuentemente tienen bucles delimitados , como:

for i=1 to N {...}

pero carecen de bucles ilimitados que controlan una condición más general, como:

while bool_expr {...}

Si todas las construcciones de bucle posibles están limitadas, se garantiza que su programa terminará. Y, aunque una garantía de terminación incondicional es potencialmente útil, también es una indicación de que el lenguaje no es Turing-completo.

Tenga en cuenta también que clavar todas las posibles construcciones de bucle puede ser difícil; por ejemplo, estoy bastante seguro de que las plantillas C ++ no estaban destinadas a ser Turing-completas ...

Me gustaría agregar una advertencia a lo que dijo Norman Ramsey: una máquina de Turing tiene memoria infinita y, por lo tanto, los lenguajes de programación que se consideran completos de Turing solo lo son bajo la suposición de que la memoria también es infinita.

No recuerdo haber visto nada como características mínimas para Turing Completeness. Sin embargo, si su idioma admite bucles y bifurcaciones condicionales, las posibilidades de que sea Turing completo son buenas. Sin embargo, la única manera de probarlo es simulando una Máquina de Turing u otro lenguaje de Turing completo.

Si puede implementar una máquina de Turing (en la medida en que puedan implementarse, ya que son construcciones matemáticas con memoria ilimitada [el tamaño de la cinta es infinito]), entonces puede estar seguro de que está completo.

Algunas indicaciones:

  • Puede verificar la memoria y manipularla según el valor actual, así como también usarla para controlar el flujo del programa.
  • A esa memoria se le puede asignar memoria, cadenas a las que puede agregar, una pila a la que puede asignar memoria mediante recursividad, etc.
  • El flujo del programa puede ser a través de la iteración o mediante la recursión basada en la selección.

Brainfuck está completo y solo tiene estructuras de bucle e incremento / decrementación de memoria, así que esto es suficiente.

Por otro lado, no hay forma de modificar ningún valor en el cálculo lambda, pero es Turing completo, por lo que es claramente posible hacerlo sin memoria mutable.

Sin embargo, lo más probable es que tu programa no tenga nada que ver con el cálculo lambda, por lo que para una respuesta práctica el mínimo debe ser

  1. Una forma de escribir en una variable
  2. Una forma de leer a una variable
  3. Una forma de goto condicional (instrucción if, while loop, etc.)

Cualquier lenguaje capaz de no terminación es más o menos Turing completo. Puede hacer que un lenguaje que no termine sea capaz dándole estructuras de bucle ilimitadas (como bucles While While o un Goto que pueda alcanzarse de nuevo) o dándole una recursión general (permitiendo que una función se llame sin restricción).

Una vez que esté completa, puede hacer cosas como interpretar otros lenguajes de Turing Complete, incluido el suyo.

La verdadera pregunta es "¿de qué sirve?" Si su lenguaje va a ser utilizado en un dominio específico para resolver problemas específicos, puede ser mejor encontrar una manera de expresar las soluciones en un idioma que no sea Turing Complete, y por lo tanto se garantiza que dará una respuesta.

Siempre puede agregar Exhaustividad de Turing escribiendo "Haga esto, aquello o lo que sea, pero hágalo con el resultado proporcionado por X" en cualquier otro lenguaje de Turing Complete, donde X sea provisto por un lenguaje completo que no sea de Turing.

Por supuesto, si solo quieres usar un idioma, probablemente sea mejor Turing Complete ...

Puede intentar emular un OISC (One Instruction-Set Computer). Si puede emular una de las instrucciones allí, entonces dado que esas instrucciones individuales se pueden usar para componer una máquina Turing completa, entonces ha demostrado que su lenguaje debe ser Turing Complete también.

''Turing Completeness'' describe la propiedad de poder expresar cualquier cálculo algorítmico arbitrario , que fue el punto de la Máquina de Turing en primer lugar. Un lenguaje o sistema lógico se puede describir como ''Turing Complete'' si tiene esta propiedad. Desde una perspectiva práctica, todos los lenguajes de programación de propósito general, y un número sorprendentemente grande de propósitos especiales, pueden hacer esto para una definición adecuada y libre (ver a continuación).

Sin embargo, una definición estricta de integridad de Turing implica una capacidad de almacenamiento infinita, que por supuesto no es físicamente posible. Dado esto, ninguna máquina física puede ser Turing completa, pero esta restricción generalmente se relaja (al menos de manera informal) al atribuir la integridad de Turing a un lenguaje de programación. Una prueba trivial de Turing Completeness para un idioma es si el lenguaje se puede usar para implementar un simulador de máquina Turing.

Un ejemplo de un sistema generalizado que no es Turing Complete es el álgebra relacional, la base teórica detrás de SQL como se describe en el documento de Codd Un modelo relacional para grandes bancos de datos compartidos. Relational Algebra tiene la propiedad de Godel Completeness , lo que significa que puede expresar cualquier cálculo que pueda definirse en términos de cálculo de predicados de primer orden (es decir, expresiones lógicas ordinarias). Sin embargo, no es Turing-Completo ya que no puede expresar un cálculo algorítmico arbitrario.

Tenga en cuenta que la mayoría, si no todos, todos los dialectos SQL prácticos amplían el modelo relacional puro con construcciones de procedimiento en la medida en que están completos por la definición que se aplica normalmente a los lenguajes de programación. Sin embargo, una consulta SQL individual en general no lo es.

Algunos ejemplos más atroces de los lenguajes específicos de dominio de Turing son TeX y sendmail.cf,. En este último caso, hay un ejemplo famoso de alguien que usa sendmail.cf para implementar un simulador universal de máquina de Turing.

Se necesita alguna forma de construcción de asignación dinámica ( malloc o new o cons ) y funciones recursivas o alguna otra forma de escribir un ciclo infinito. Si tienes esos y puedes hacer algo interesante, casi seguro que eres completo.

El cálculo lambda es equivalente en potencia a una máquina de Turing, y si implementa el cálculo lambda, en realidad es muy divertido escribir programas de cálculo lambda. ¡Es mucho más divertido que escribir un programa para una máquina de Turing!

La única implicación práctica de Turing-completitud que conozco es que puedes escribir programas que no terminan. He usado un par de idiomas especiales que garantizan la terminación y, por lo tanto, no son completos. Algunas veces es útil renunciar al poder expresivo adicional a cambio de la terminación garantizada.

¿Existe un conjunto mínimo de características sin las cuales la integridad de Turing es imposible? ¿Existe un conjunto de características que prácticamente garantiza la integridad?

Sí, necesita tener un flujo de control condicionado a los datos: lo que a menudo se expresa como if . Por ejemplo, una calculadora de bolsillo +-*/ no es Turing completa, ya que no hay forma de expresar condicionales.

También debe ser capaz de expresar un salto a un punto anterior en el programa, además de lo cual podría implementar un bucle. Por ejemplo, BPF, que prohíbe los saltos hacia atrás para garantizar que el programa termine, tampoco está completo.

Necesita un almacenamiento que sea legible y modificable y arbitrariamente grande. Por ejemplo, un idioma que tiene solo dos variables de 32 bits está limitado en lo que puede calcular. Tiene muchas opciones sobre cómo se estructura el almacenamiento: memoria dirigida por punteros, matrices, pilas, celdas de cons, estructuras de datos puras, etc.

Además de esto, puedes construir cualquier otro lenguaje de programación: puede que no sea fácil o rápido, pero es suficiente.