¿Qué hace que un lenguaje sea completo?

79

¿Cuál es el conjunto mínimo de características / estructuras del lenguaje que lo hacen completo de Turing?

Gato curioso
fuente
21
¿No sería mejor simplemente googlearlo? en.wikipedia.org/wiki/Turing_completeness
aml90
2
Hola curioso gato, ¡bienvenido a Programadores! Las llamadas a listas no son sobre el tema aquí: he eliminado esa parte de tu pregunta. Dicho esto, esta búsqueda es extremadamente amplia: ¿hay algún problema específico en el que estés trabajando que te haga pensar en la integridad de Turing?
3
@amalantony: solo como una nota al pie .
Bobby
Para una perspectiva informática, ver aquí .
Raphael

Respuestas:

73

Un tarpit de Turing es un tipo de lenguaje de programación esotérico que se esfuerza por completar Turing 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 el 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 ramificar si es menor o igual que cero", o "restar y omitir inversamente si se toma prestado". El x86 MMU implementa la instrucción anterior y, por lo tanto, es Turing completo.

En general, para que un lenguaje imperativo sea completo en Turing, necesita:

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

  2. Una forma de leer y escribir alguna forma de almacenamiento (por ejemplo, variables, cinta)

Para que un lenguaje funcional basado en cálculo lambda sea ​​TC, necesita:

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

  2. La capacidad de aplicar funciones a argumentos (p. Ej., Reducción)

Por supuesto, hay otras formas de ver la computación, pero estos son modelos comunes para lonas de Turing. Tenga en cuenta que las computadoras reales no son máquinas 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 acotadas y las máquinas de estados finitos son útiles para el cálculo; simplemente no son universales .

Estrictamente hablando, no se requiere E / S para completar Turing; TC solo afirma que un lenguaje puede calcular la función que desea, no que puede mostrarle el resultado. En la práctica, cada lenguaje útil tiene una forma de interactuar con el mundo de alguna manera.

Jon Purdy
fuente
Para lenguajes imperativos, ¿son suficientes las variables simples? Tenía la impresión de que sería necesario algún tipo de colección (por ejemplo, matrices o listas vinculadas).
luiscubal
1
@luiscubal necesita poder especificar una cantidad arbitraria de datos. Con variables simples puede representar la cantidad de datos que tienen las variables mismas. ¿Qué sucede si necesita representar N + 1 datos diferentes? Se podría argumentar que con trucos como las jugadas de Fractran, podrías hacerlo incluso en variables simples ... pero eso no es exactamente lo que estás preguntando.
¿No es necesario que el idioma sea compatible con bucles SIN FIN ?
sergiol
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 las funciones de la biblioteca, y las funciones de la biblioteca podrían ser completamente diferentes en diferentes implementaciones. Pero, por la presente me abstengo de cualquier discusión sobre si Algol 60 fue o no "útil".
Solomon Slow
15

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

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

Anton Golov
fuente
11
Sí, definitivamente esa sería la forma más práctica de abordarlo. </sarcasm>
Robert Harvey
13
@RobertHarvey tiene un punto, pero la idea general es bastante vital. Se ha demostrado que Brainfuck es completo y muy simple a medida que avanzan 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 no estoy seguro de dónde comenzar con un formal prueba de que Python se está completando); y se sabe que docenas de lenguajes esotéricos inspirados en brainfuck están completos porque se sabe cómo se mapean en brainfuck.
77
@RobertHarvey: ¿Por qué no? Seguramente alguien que diseñe su propio idioma podría escribirle un compilador BF (si fuera imperativo, y de lo contrario encontraría un otro idioma adecuado).
Anton Golov
55
@delnan: Sin embargo, tendrá que demostrar que su intérprete de BF implementa correctamente la especificación de BF. Ahora, deberá demostrar que su intérprete de BF es, de hecho, un intérprete de BF y no un intérprete para un lenguaje similar a BF que podría o no ser Turing completo.
Jörg W Mittag
2
@ DarekNędza, eso es solo una consecuencia natural de cómo se define la integridad de Turing; cualquier extensión de un lenguaje Turing Complete seguirá siendo Turing Complete.
Anton Golov
8

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

Para verificar si algo está completo en Turing, 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 es suficiente para 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 equivalentes) 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 equivalentes).
  3. La capacidad de simular una máquina de estados finitos : aunque no se menciona con frecuencia, las máquinas de Turing son en realidad una variación de las máquinas de estados finitos que se usan a menudo en el desarrollo de IA. Alan Turing dijo que el propósito de los estados es simular los "diversos modos de resolución de problemas" de una persona.
  4. Un estado de "alto" : 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 qué algoritmo es algoritmo de estado siempre debe Finalmente concluir. Si no pueden concluir de alguna manera, o no está completo Turing, o dicho algoritmo no es una función computable. Los sistemas completos que técnicamente no pueden concluir debido a la forma en que funcionan (como las consolas de juegos, por ejemplo) evitan 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 lo demuestra "

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

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

usuario3067516
fuente
4

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 completen un lenguaje durante el tiempo, por lo que las respuestas que dicen que necesita bucles o que necesita variables son incorrectas, ya que hay idiomas que no tienen ninguno pero están completos.

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

La complejidad del tiempo, la complejidad del espacio, la facilidad de formato de entrada / salida y la facilidad de escribir cualquier programa no se incluyen en la ecuación, por lo que, en teoría, dicha máquina puede hacer todos los cálculos si los cálculos no se detienen por la pérdida de potencia o el sol se traga la Tierra.

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

Sin embargo, para crear un lenguaje exitoso se necesita algo más que la integridad completa, y esto es cierto incluso para las lonas impermeables. No creo que BrainFuck hubiera sido popular sin ,y ..

Sylwester
fuente
2
"Un lenguaje de programación se está completando si puedes hacer algún cálculo con él". Esa es la tesis de la Iglesia-Turing, no lo que hace que un lenguaje sea completo.
Rhymoid
@Rhymoid ¿Quiere decir que nada está completo a menos que pueda hacer un intérprete? Es decir. ¿el cálculo lambda no está completo incluso si es igual?
Sylwester
1
Todavía estoy buscando una definición autorizada de los términos Turing-equivalente y Turing-complete (y Turing-poderoso). Ya he visto demasiados casos, desde personas en tableros de mensajes hasta investigadores en sus propios periódicos, que interpretan estos términos de manera diferente.
Rhymoid
De todos modos, interpreto que 'Turing-complete' es una simulación equivalente a una Máquina Turing Universal (UTM; que, a su vez, es capaz de simular cualquier máquina Turing, por lo tanto, 'universal'). En el artículo de Turing de 1936, donde introdujo 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 al cálculo lambda de Church. Al hacerlo, demostró que tenían el mismo poder computacional. La tesis de Church-Turing afirma, en pocas palabras, que "ese es todo el poder computacional que jamás obtendrás".
Rhymoid
Tiene dos definiciones formales para la página de integridad de Turing de Wikipedia . Uno requiere E / S, el otro no. El que no dice que una máquina está completa si puede calcular todas las funciones computables de Turing. Eso hace que el cálculo lambda vuelva a estar completo, ya que puede hacer fácilmente un programa equivalente en cálculo lambda que calcule lo mismo que cualquier programa de máquina de turing.
Sylwester
4

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

-------------

Explicación: Dada alguna información, es imposible saber en todos los casos (usando otra máquina de Turing) si la cosa se repetirá infinitamente o finalmente se detendrá, excepto ejecutándola (lo que le da una respuesta si se detiene, pero no si se repite!).

Esto significa que tiene que ser capaz de almacenar una cantidad de datos potencialmente ilimitada de alguna manera: ¡debe haber un equivalente a la cinta infinita, sin importar cuán enrevesada sea! (De lo contrario, solo hay un número finito de estados y luego puede verificar si ya ha pasado por ese estado y, finalmente, detenerse). En general, las máquinas de Turing pueden aumentar o reducir el tamaño de su estado por algún medio controlable.

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

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 demuestra que su sistema también está completo.

Por ejemplo, suponga que desea demostrar que Snakes & Ladders está completa en Turing, dado un tablero con un patrón de cuadrícula infinitamente repetido (con una versión diferente en el lado superior e izquierdo). Sabiendo que la máquina Minsky de 2 contadores está Turing completa (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. ¡Explosión! Acabas de demostrar que Snakes & Ladders están completos.

Hubert Lamontagne
fuente
1
No compro ese argumento. El hecho de que el problema de detención sea indecidible para las máquinas de Turing no implica directamente que cada notación que le permite especificar un programa para el cual el problema de detención sea indecidible sea Turing completo. Obviamente, solo lo inverso es cierto: si la notación es Turing completa, entonces, por supuesto, es posible escribir programas para los cuales el problema de detención es indecidible.
5gon12eder
Es una condición necesaria. Si puede decidir para cada programa si se detiene, entonces el idioma no está completo.
gnasher729
4

Una condición necesaria es un bucle con un recuento de iteración máximo que no se determina antes de la iteración, o recursión donde la profundidad de recursión máxima no se determina adelante. Como ejemplo, para ... en ... los bucles, ya que los encuentra en muchos idiomas más nuevos, no son suficientes para completar el lenguaje (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 idioma sin estas características. Por otro lado, se puede escribir una gran cantidad de software altamente complejo y altamente útil sin requerir estas características.

Por otro lado, con cada recuento de iteraciones y cada profundidad de recursión calculada con anticipación, no solo se puede decidir si un programa se detendrá o no, sino que se detendrá.

gnasher729
fuente
-1

Sé que esta no es la respuesta formalmente correcta, pero una vez que elimine el 'mínimo' de 'Turing-complete' y vuelva a colocar 'práctico' donde pertenece, verá las características más importantes que distinguen un lenguaje de programación de un lenguaje de marcado son

  • variables
  • condicionales (si / entonces ...)
  • loopage (bucle / pausa, mientras ...)

luego viene

  • funciones anónimas y con nombre

Para probar estas afirmaciones, comience con un lenguaje de marcado, por ejemplo, HTML. podríamos inventar un HTML + con variables solamente, o solo condicionales (MS lo hizo con comentarios condicionales), o algún tipo de construcción de bucle (que en ausencia de condicionales probablemente terminaría como algo así <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 la minimidad en la lógica y la programación es importante e interesante, pero si tuviera que enseñar a los jóvenes o viejos 'qué es la programación' y 'cómo aprender a programar', difícilmente comenzaría con toda la amplitud y amplitud de los fundamentos teóricos de la integridad de Turing. toda la esencia de la cocina y la programación es hacer cosas, en el orden correcto, repitiendo hasta que esté listo, como lo hizo tu madre. Eso lo resume todo para mí.

Por otra parte, nunca terminé mi CS.

fluir
fuente
2
Si no está seguro, primero debe investigarlo. fractran se está completando , al igual que brainf * ck . Tenga en cuenta también que html 5 + CSS 3 está Turing completo porque puede implementar la regla 110 .
1
Sí, sí, lo sé. pero todos los ejemplos dados son más o menos esotéricos (aunque quizás sean interesantes o sorprendentes), mi respuesta fue pragmática, y muy probablemente no mínima. Creo que es importante señalarlo: esta página fue la número 1 en la búsqueda de la integridad de Turing en Google, las respuestas aquí son en mi humilde opinión de poca utilidad para, por ejemplo, un n00bie que quiere saber qué distingue HTML de PHP o Python. Quiero decir, brainf ck no se llama brainf ck sin ninguna razón.
fluye el