¿Qué hace que un idioma sea Turing completo?

A Tarpit de Turing es una especie de lenguaje de programación esotérico que se esfuerza por ser Turing completo mientras usa la menor cantidad de elementos posible. Brainfuck es quizás el tarpit más conocido, pero hay muchos.

• Iota y Jot son lenguajes funcionales con dos y tres símbolos, respectivamente, basados en Cálculo del combinador SK (I) .

• OISC ( One Instruction Set Computer ) denota un tipo de cálculo imperativo que requiere solo una instrucción de uno o más argumentos, generalmente “restar y bifurcar si es menor o igual a cero”, o “Restar en reversa y saltar si se pide prestado”. La MMU x86 implementa la instrucción anterior y por lo tanto es Turing-completa.

En general, para un lenguaje imperativo para ser Turing-completo, necesita:

1. Una forma de repetición condicional o salto condicional (por ejemplo, while, if + goto)

2. Una forma de leer y escribir alguna forma de almacenamiento (p. ej. , variables, cinta)

Para que un lenguaje funcional basado en lambda-calculus sea TC, necesidades:

1. La capacidad de abstraer funciones sobre argumentos (por ejemplo, abstracción lambda, cita)

2. La capacidad de aplicar funciones a argumentos (por ejemplo, reducción)

Por supuesto, hay otras formas de ver la computación, pero estos son modelos comunes para los tarpits de Turing. Tenga en cuenta que las computadoras reales no máquinas de Turing universales porque no tienen almacenamiento ilimitado. Estrictamente hablando, son “máquinas de almacenamiento acotadas”. Si siguiera agregando memoria a ellos, se acercarían asintóticamente a las máquinas de Turing en el poder. Sin embargo, incluso las máquinas de almacenamiento limitadas y las máquinas de estado finito son útiles para la computación; simplemente no son universales .

Estrictamente hablando, la E / S no es necesaria para la completitud de Turing; TC solo afirma que un idioma puede calcular la función que desea, no que pueda mostrar el resultado. En la práctica, todo lenguaje útil tiene una forma de interactuar con el mundo de alguna manera.

Comentarios

• Para los lenguajes imperativos, ¿son suficientes las variables simples? Tenía la impresión de que sería necesario algún tipo de recopilación (por ejemplo, matrices o listas vinculadas).
• @luiscubal, debe poder especificar una cantidad arbitraria de datos. Con variables simples puedes representar la cantidad de datos que tienen las propias variables. ¿Qué sucede si necesita representar N + 1 piezas de datos diferentes? Se podría argumentar que con trucos como los que juega Fractran, podrías hacerlo incluso en variables simples … pero que ‘ no es exactamente lo que ‘ estás preguntando.
• No es ‘ t se requiere, el idioma debe admitir ¿Bucles SIN FIN ?
• Re, » cada lenguaje útil tiene una forma de interactuar con el mundo. » Algol 60 no tenía ninguna forma definida de interactuar con el mundo. Todas sus E / S en un programa Algol 60 se realizaron llamando a funciones de biblioteca, y las funciones de biblioteca podrían ser completamente diferentes en diferentes implementaciones. Pero, por la presente me excluyo de cualquier discusión sobre si Algol 60 fue » útil. »

Desde un punto de vista más práctico: si puedes traducir todos los programas en un lenguaje Turing completo a tu idioma, entonces (en la medida en que Lo sé), su idioma debe ser Turing completo.Por lo tanto, si desea verificar si un lenguaje que diseñó es Turing-completo, simplemente podría escribir un Brainf *** en el compilador YourLanguage y probar / demostrar que puede compilar todos los programas BF legales.

Para aclarar, quiero decir que además de un intérprete para YourLanguage, escribes un compilador (en cualquier idioma) que puede compilar cualquier programa BF en YourLanguage (manteniendo la misma semántica, por supuesto).

Comentarios

• Sí, definitivamente sería la forma más práctica de abordarlo. </sarcasm>
• @RobertHarvey tiene razón, pero la idea general es muy importante. Brainfuck ha demostrado ser turing-completo y muy simple como lo son los lenguajes de programación. Para los lenguajes de programación no esotéricos, implementar un intérprete de brainfuck puede ser mucho más fácil y rápido que dar una prueba rigurosa de la nada (puedo implementar BF en un par de líneas de Python, pero ‘ m no estoy seguro de por dónde empezar con una prueba formal de que Python se está completando); y se sabe que docenas de lenguajes esotéricos inspirados en la cogida cerebral son completos porque ‘ s sabe cómo se asignan a la cogida cerebral.
• @RobertHarvey: ¿Por qué no? Seguramente alguien que diseñe su propio lenguaje podría escribirle un compilador BF (si fuera imperativo, y encontrar otro lenguaje adecuado en caso contrario).
• @delnan: Usted lo hará tiene que demostrar, sin embargo, que su intérprete BF implementa correctamente la especificación BF, IOW tendrá que demostrar que su intérprete BF es, de hecho, un intérprete BF y no un intérprete para un lenguaje similar a BF que podría o no ser Turing-complete.
• @ DarekNędza, que ‘ es solo una consecuencia natural de cómo se define Turing Completeness; cualquier extensión de un idioma de Turing Complete seguirá siendo Turing Complete.

Un sistema solo puede considerarse ser Turing completo si puede hacer algo que pueda hacer una máquina universal de Turing. Dado que se dice que la máquina universal de Turing es capaz de resolver cualquier función computable en un momento dado, los sistemas completos de Turing también pueden hacerlo, por extensión.

Para verificar si algo es Turing completo, vea si puede implementar una máquina de Turing en su interior. En otras palabras, verifique si puede simular lo siguiente:

1. La capacidad de leer y escribir «variables» (o datos arbitrarios) : se explica por sí mismo.
2. La capacidad de simular el movimiento del cabezal de lectura / escritura : No basta con poder recuperar y almacenar variables. También debe ser posible simular la capacidad de mover la cabeza de la cinta para hacer referencia a otras variables. Esto a menudo se puede simular dentro de los lenguajes de programación con el uso de estructuras de datos de matriz (o equivalente) o, en el caso de ciertos lenguajes como el código de máquina, la capacidad de hacer referencia a otras variables mediante el uso de «punteros» (o equivalente).
3. La capacidad de simular una máquina de estados finitos : aunque no se menciona a menudo, las máquinas de Turing son en realidad un variación de las máquinas de estados finitos que se utilizan a menudo en el desarrollo de la IA. Alan Turing dijo que el propósito de los estados es simular los distintos modos de resolución de problemas de una persona.
4. Un estado «detenido» : Aunque a menudo se menciona que un conjunto de reglas debe poder repetirse para contar como Turing completo, ese no es realmente un buen criterio, ya que la definición formal de lo que es El algoritmo es estado, los algoritmos siempre deben eventualmente concluir. Si no pueden concluir de alguna manera, o no es Turing completo, o dicho algoritmo no es una función computable. Los sistemas completos de Turing que técnicamente no pueden concluir debido a la forma en que funcionan (como las consolas de juegos, por ejemplo) superan esta limitación al poder «simular» un estado de detención de alguna manera. No debe confundirse con el «problema de detención «, una función indecidible que demuestra que es imposible construir un sistema que pueda detectar con un 100% de confiabilidad si una entrada dada hará que otro sistema no concluya.

Estos son los verdaderos mínimos requisitos para que un sistema se considere Turing completo. Nada más y nada menos. Si no puede simular ninguno de estos de alguna manera, no es Turing completo. Los métodos propuestos por otras personas son solo medios para el fin, ya que hay varios sistemas completos de Turing que no tienen esas características.

Tenga en cuenta que no existe una forma conocida de construir un verdadero sistema completo de Turing. . Esto se debe a que no existe una forma conocida de simular genuinamente la ilimitación de la cinta de la máquina de Turing dentro del espacio físico.

Un lenguaje de programación se está completando si puede hacer algún cálculo con él.No hay un solo conjunto de características que haga que la formación de un idioma sea completa, por lo que las respuestas que dicen que necesita bucles o que necesita variables son incorrectas, ya que hay idiomas que no tienen ni pero están turing completo.

Alan Turing hizo la máquina turing universal y si puedes traducir cualquier programa diseñado para funcionar en la máquina universal para que se ejecute en tu idioma, también es Turing completo. Esto también funciona indirectamente, por lo que puede decir que el idioma X se está completando si todos los programas para el idioma completo Y se pueden traducir para X, ya que todos los programas de la máquina universal de turing se pueden traducir a un programa Y.

La complejidad del tiempo , complejidad espacial, formato de entrada / salida fácil y fácil de escribir, cualquier programa no está incluido en la ecuación, por lo que dicha máquina teóricamente puede hacer todos los cálculos si los cálculos no se detienen por una pérdida de energía o la Tierra es tragada por el sol.

Por lo general, para demostrar la completitud de turing, hacen un intérprete para cualquier lenguaje turing completo probado, pero para que funcione se necesitan medios de entrada y salida, dos cosas que realmente no son necesarias para que un idioma sea turing completo. Es suficiente que su programa pueda alterar su estado al inicio y que pueda inspeccionar la memoria después de que el programa se detenga.

Sin embargo, para hacer un lenguaje exitoso se necesita algo más que completar el proceso y esto es cierto incluso para las lonas de turing. No creo que BrainFuck hubiera sido popular sin , y ..

Comentarios

• » Un lenguaje de programación se está completando si puede hacer algún cálculo » Eso ‘ es la tesis de Church-Turing, no lo que hace que un lenguaje sea Turing-completo.
• @Rhymoid Entonces, ¿quieres decir que nada está completo a menos que puedas hacer un intérprete? Es decir, el cálculo lambda no está completo incluso si ‘ está en equilibrio?
• Yo ‘ sigo buscando una definición autorizada de los términos Turing-equivalente y Turing-completo (y Turing-poderoso). I ‘ Ya he visto demasiados casos, desde personas en foros de mensajes hasta investigadores en sus propios trabajos ‘, que interpretan estos términos de manera diferente.
• De todos modos, Interpreto ‘ Turing-complete ‘ como una simulación equivalente a una Universal Turing Machine (UTM; que, a su vez, es capaz de simular cualquier máquina de Turing, por lo tanto, ‘ universal ‘). En el artículo de Turing ‘ de 1936, donde presentó sus máquinas, definió la noción de un UTM y dio un bosquejo de una prueba de que los UTM son una simulación equivalente a Church ‘ s cálculo lambda. Al hacerlo, demostró que tenían el mismo poder computacional. La tesis de Church-Turing afirma, en pocas palabras, que » que ‘ es todo el poder computacional que ‘ alguna vez obtendremos «.
• Tiene dos definiciones formales para página de Turing de Wikipedia . Uno requiere E / S y el otro no ‘ t. El que no ‘ no dice que una máquina se está completando si puede calcular todas las funciones computables de Turing. Eso hace que el cálculo lambda vuelva a ser turing completo, ya que puede crear fácilmente un programa equivalente en cálculo lambda que calcule lo mismo que cualquier programa de máquina turing.

No puede «saber si» se repetirá infinitamente o se detendrá.

————-

Explicación: Dada alguna entrada, es imposible decir en todos los casos (usando otra máquina de Turing) si la cosa va a hacer un bucle infinito o eventualmente se detendrá, excepto ejecutándola (lo que le da una respuesta si lo hace detener, ¡pero no si se repite!).

Esto significa que debe poder almacenar una cantidad potencialmente ilimitada de datos de alguna manera; tiene que haber un equivalente a la cinta infinita, no importa cómo ¡Enrevesado! (De lo contrario, solo hay un número finito de estados y luego puede verificar si ha pasado por ese estado anteriormente y eventualmente detenerse). Generalmente, las máquinas de Turing pueden aumentar o reducir el tamaño de su estado mediante algunos medios controlables.

Dado que la máquina de Turing universal original de Turing tiene un problema de detención insoluble, su propia máquina completa de Turing también debe tener una detención insoluble problema.

Los sistemas completos de Turing pueden emular cualquier otro sistema completo de Turing, por lo que si puede construir un emulador para algún sistema completo de Turing conocido en su sistema, eso prueba que su sistema también es Turing completo.

Por ejemplo, suponga que quiere demostrar que Snakes & Ladders es Turing completo, dado un tablero con un patrón de cuadrícula repetido infinitamente (con una versión diferente en la parte superior y lado izquierdo). Sabiendo que la máquina Minsky de 2 contadores es Turing completo (que tiene 2 contadores ilimitados y 1 estado de un número finito), puede construir un tablero equivalente donde la posición X e Y en la cuadrícula es el valor actual de los 2 contadores y la ruta actual es el estado actual. ¡Estallido! Acabas de demostrar que Snakes & Las escaleras están Turing completas.

Comentarios

• Yo no ‘ No compre ese argumento. El hecho de que el problema de la detención sea indecidible para las máquinas de Turing no implica directamente que toda notación que le permita especificar un programa para el que el problema de la detención sea indecidible sea Turing completo. Solo lo inverso es obviamente cierto: si la notación es Turing completa, entonces, por supuesto, es posible escribir programas para los que el problema de detención es indecidible.
• It ‘ una condición necesaria. Si puede decidir para cada programa si se detiene, entonces el idioma no es ‘ t Turing completo.

Una condición necesaria es un bucle con un recuento máximo de iteraciones que no se determina antes de la iteración, o recursividad donde la profundidad máxima de recursión no se determina por delante. Como ejemplo, los bucles for … in … tal como los encuentra en muchos idiomas más nuevos no son suficientes para completar el turing del idioma (pero tendrán otros medios). Tenga en cuenta que esto no significa un número limitado de iteraciones o una profundidad de recursión limitada, sino que las iteraciones máximas y la profundidad de recursión deben calcularse con anticipación.

Por ejemplo, la función de Ackermann no se puede calcular en un lenguaje sin estas características. Por otro lado, se puede escribir una gran cantidad de software altamente complejo y muy útil sin requerir estas características.

Por otro lado, con cada recuento de iteraciones y cada profundidad de recursividad calculada de antemano, no solo ¿Se puede decidir si un programa se detendrá o no, pero se detendrá .

Sé que esta no es la respuesta formalmente correcta, pero una vez que elimine el «mínimo» de «Turing-completo» y vuelva a poner «práctico» en su lugar, verá las características más importantes que distinguen a un lenguaje de programación de un lenguaje de marcado son

• variables
• condicionales (si / entonces …)
• loopage (bucle / descanso, mientras …)

siguiente com e

• funciones anónimas y con nombre

para probar estas afirmaciones, comience con un lenguaje de marcado, digamos, HTML. podríamos inventar un HTML + solo con variables, o solo condicionales (MS hizo eso con comentarios condicionales), o algún tipo de construcción de bucle (que en ausencia de condicionales probablemente terminaría como <repeat n="4">...</repeat>). hacer cualquiera de estos hará que HTML + sea significativamente (?) más poderoso que HTML simple, pero aún sería más un marcado que un lenguaje de programación; con cada nueva característica, lo convierte en un lenguaje menos declarativo y más imperativo.

La búsqueda de lo mínimo en lógica y programación es sin duda importante e interesante, pero si tuviera que enseñar a n00bies jóvenes o mayores «qué es programar» y «cómo aprender a programar», difícilmente empezaría con toda la amplitud y amplitud de los fundamentos teóricos de la completitud de Turing. toda la esencia de la cocina y la programación es hacer las cosas, en el orden correcto, repitiendo hasta que estén listas, como lo hizo tu madre. Eso lo resume todo para mí.

de nuevo, nunca terminé mi CS.

Comentarios

• Si no está seguro, primero debe investigarlo. fractran está completando , al igual que brainf * ck . Tenga en cuenta también que html 5 + CSS 3 es Turing completo porque puede implementar regla 110 .
• sí sí sí lo sé. pero todos los ejemplos dados son más o menos esotéricos (aunque quizás interesantes o sorprendentes), m Mi respuesta fue pragmática, y muy probablemente no mínima en absoluto. Creo que ‘ es importante señalar eso: esta página fue la número 1 cuando se buscó Turing-completeness en Google, las respuestas aquí son en mi humilde opinión de poca utilidad para, digamos, un n00bie que quiere saber qué distingue a HTML de PHP o Python. quiero decir, brainf ck no se llama brainf ck sin ninguna razón.