¿Cuáles son las pautas prácticas para evaluar el & # 8220; Turing Completeness & # 8221 ;?

https://stackoverflow.com/questions/449014

19-08-2019
|

Pregunta

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

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

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

(Supongo que la ramificación condicional y un almacén de memoria legible / grabable me llevarán la mayor parte del camino)

EDITAR:

Creo que he salido por la tangente diciendo "Turing completo". Estoy tratando de adivinar con una confianza razonable que un lenguaje recién inventado con un determinado conjunto de características (o alternativamente, una VM con un determinado conjunto de instrucciones) podría calcular cualquier cosa que valga la pena computar. Sé que demostrar que puedes construir una máquina Turing con él es de una manera, pero no la única.

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

Solución

Necesita alguna forma de construcción de asignación dinámica ( malloc o new o cons servirá) y funciones recursivas o alguna otra forma de escribiendo un bucle infinito. Si los tiene y puede hacer algo interesante, es casi seguro que está completando Turing.

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

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

Otros consejos

'Turing Completeness' describe la propiedad de poder expresar cualquier arbitrario computación algorítmica, que era el punto de La máquina de Turing en primer lugar. Un lenguaje o sistema lógico puede describirse como 'Turing completo' si tiene esta propiedad. Desde una perspectiva práctica, todos los lenguajes de programación de propósito general, y una cantidad sorprendentemente grande de propósitos especiales, pueden hacer esto para una definición adecuadamente flexible (ver más abajo).

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 Complete, pero esta restricción generalmente se relaja (al menos de manera informal) cuando se atribuye Turing Completeness a un lenguaje de programación. Una prueba trivial de la integridad de Turing para un idioma es si el idioma se puede utilizar para implementar un simulador de máquina de Turing.

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

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

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

Si puede escribir un Brainf $ & amp; # intérprete en su idioma, es Turing -completar. LOLCODE demostró ser Turing completo exactamente de esta manera.

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

for i=1 to N {...}

pero carece de bucles ilimitados que comprueban 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 está completo de Turing.

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

No estoy seguro de si hay un "conjunto mínimo de características", pero para demostrar que un idioma está completo en Turing, solo tiene que demostrar que puede emular otro sistema completo de Turing (no necesariamente una máquina de Turing), siempre y cuando se sepa que el otro sistema es Turing 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.

Quisiera 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 son solo bajo el supuesto de que la memoria también es infinita.

Brainfuck está Turing completo, y solo tiene estructuras de bucle e incremento / disminució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.

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

Una forma de escribir en una variable
Una forma de leer una variable
Una forma de goto condicional (sentencia if, while loop, etc.)

No recuerdo haber visto nada como características mínimas para Turing Completeness. Sin embargo, si su idioma admite bucles y ramas condicionales, las posibilidades de que se complete Turing son buenas. Sin embargo, la única forma de demostrarlo es simular una máquina de Turing u otro lenguaje completo de Turing.

Si puede implementar una máquina 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 Turing está completo.

Algunas indicaciones:

Puede verificar la memoria y manipularla en función del valor actual, así como usarla para controlar el flujo del programa.
A esa memoria se le puede asignar memoria, cadenas a las que puede agregar, una pila en 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.

Cualquier lenguaje capaz de no terminar es prácticamente Turing completo. Puede hacer que un lenguaje sea capaz de no terminar dándole estructuras de bucle ilimitadas (como bucles While o un Goto que puede alcanzarse de nuevo), o dándole una recursión general (dejando que una función se llame a sí misma sin restricción).

Una vez que esté turing completo, puede hacer cosas como interpretar otros idiomas de Turing Complete, incluido el suyo.

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

Siempre puede agregar integridad de Turing escribiendo '' Hacer esto, aquello o lo que sea; pero hazlo con el resultado proporcionado por X " en cualquier otro lenguaje completo de Turing, donde X es proporcionado por un lenguaje completo que no es de Turing.

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

Puede intentar emular un OISC (una computadora con conjunto de instrucciones). Si puede emular una de las instrucciones allí, entonces dado que esas instrucciones individuales pueden usarse para componer una máquina Turing Complete, entonces ha demostrado que su idioma también debe ser Turing Complete.

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

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

También debe poder expresar un salto a un punto anterior del programa, además del cual podría implementar un bucle. Por ejemplo, BPF, que prohíbe los saltos hacia atrás para garantizar que el programa termine, tampoco se completa con Turing.

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

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

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

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

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

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow