¿Qué es Turing completo?

¿Qué significa la expresión "Turing completo"?

¿Puedes dar una explicación simple, sin entrar en demasiados detalles teóricos?

Aquí está la explicación más breve:

Un sistema Turing Complete significa un sistema en el que se puede escribir un programa que encontrará una respuesta (aunque sin garantías con respecto al tiempo de ejecución o la memoria).

Entonces, si alguien dice "lo nuevo de Turing es completo", eso significa en principio (aunque a menudo no en la práctica) que podría usarse para resolver cualquier problema de cálculo.

A veces es una broma ... un tipo escribió un simulador de Turing Machine en vi, por lo que es posible decir que vi es el único motor computacional que se necesita en el mundo.

Aquí está la explicación más simple.

Alan Turing creó una máquina que puede tomar un programa, ejecutar ese programa y mostrar algún resultado. Pero luego tuvo que crear diferentes máquinas para diferentes programas. Entonces creó "Universal Turing Machine" que puede tomar CUALQUIER programa y ejecutarlo.

Los lenguajes de programación son similares a esas máquinas (aunque virtuales). Toman programas y los ejecutan. Ahora, un lenguaje de programación se llama "Turing completo", si es que puede ejecutar cualquier programa (independientemente del idioma) que una máquina de Turing puede ejecutar con suficiente tiempo y memoria.

Por ejemplo: Digamos que hay un programa que toma 10 números y los agrega. La máquina de Turing puede ejecutar fácilmente este programa. Pero ahora imagine que por alguna razón su lenguaje de programación no puede realizar la misma adición. Esto lo haría "Turing incompleto" (por así decirlo). Por otro lado, si puede ejecutar cualquier programa que pueda ejecutar la máquina universal de Turing, entonces es Turing completo.

La mayoría de los lenguajes de programación modernos (p. Ej., Java, JavaScript, Perl, etc.) están completos porque implementan todas las características necesarias para ejecutar programas como la suma, multiplicación, condición if-else, declaraciones de retorno, formas de almacenar / recuperar / borrar datos y así sucesivamente.

Actualización: puede obtener más información en mi blog: "JavaScript se está completando" - Explicado

De wikipedia :

La integridad de Turing, llamada así por Alan Turing, es importante porque cada diseño plausible para un dispositivo informático tan avanzado puede ser emulado por una máquina universal de Turing, una observación que se conoce como la tesis de Church-Turing. Por lo tanto, una máquina que puede actuar como una máquina universal de Turing puede, en principio, realizar cualquier cálculo que cualquier otra computadora programable sea capaz de hacer. Sin embargo, esto no tiene nada que ver con el esfuerzo requerido para escribir un programa para la máquina, el tiempo que puede tomar para que la máquina realice el cálculo, o cualquier habilidad que la máquina pueda poseer que no esté relacionada con el cálculo.

Si bien es probable que las máquinas verdaderamente completas de Turing sean físicamente imposibles, ya que requieren almacenamiento ilimitado, la integridad de Turing a menudo se atribuye libremente a máquinas físicas o lenguajes de programación que serían universales si tuvieran almacenamiento ilimitado. Todas las computadoras modernas son Turing-complete en este sentido.

No sé cómo puede ser más no técnico que eso, excepto diciendo "estar completo significa 'capaz de responder a un problema computable dado el tiempo y el espacio suficientes'".

Definición informal

Un lenguaje completo de Turing es aquel que puede realizar cualquier cálculo. La tesis de Church-Turing establece que cualquier cálculo ejecutable puede ser realizado por una máquina de Turing. Una máquina de Turing es una máquina con memoria de acceso aleatorio infinita y un 'programa' finito que dicta cuándo debe leer, escribir y moverse a través de esa memoria, cuándo debe terminar con un determinado resultado y qué debe hacer a continuación. La entrada a una máquina de Turing se guarda en su memoria antes de que comience.

Cosas que pueden hacer que un lenguaje NO se complete

Una máquina de Turing puede tomar decisiones basadas en lo que ve en la memoria - El 'lenguaje' que sólo los soportes +, -, *, y /en números enteros no es Turing completo porque no puede tomar una decisión basada en su entrada, pero una máquina de Turing puede.

Una máquina de Turing puede ejecutarse para siempre : si tomamos Java, Javascript o Python y eliminamos la capacidad de hacer cualquier tipo de bucle, GOTO o llamada a función, no sería Turing completo porque no puede realizar un cálculo arbitrario que nunca termina Coq es un probador de teoremas que no puede expresar programas que no terminan, por lo que no está completo.

Una máquina de Turing puede usar memoria infinita : un lenguaje que era exactamente como Java pero que terminaría una vez que usara más de 4 Gigabytes de memoria no estaría completo, porque una máquina de Turing puede usar memoria infinita. Es por eso que en realidad no podemos construir una máquina de Turing, pero Java sigue siendo un lenguaje completo de Turing porque el lenguaje Java no tiene restricciones que le impidan usar memoria infinita. Esta es una razón por la cual las expresiones regulares no están completas.

Una máquina Turing tiene memoria de acceso aleatorio : un lenguaje que solo le permite trabajar con memoria pushy popoperaciones en una pila no estaría completo. Si tengo un 'lenguaje' que lee una cadena una vez y solo puede usar la memoria presionando y haciendo estallar desde una pila, me puede decir si cada parte (de la cadena tiene la suya )más tarde presionando cuando ve (y haciendo estallar cuando ve ). Sin embargo, no puede decirme si cada uno (tiene el suyo )más adelante y si cada uno [tiene el suyo ]más tarde (tenga en cuenta que ([)]cumple con este criterio pero ([]]no lo hace). Una máquina de Turing puede utilizar su memoria de acceso aleatorio para realizar un seguimiento ()'s y[]está por separado, pero este lenguaje con solo una pila no puede.

Una máquina de Turing puede simular cualquier otra máquina de Turing : una máquina de Turing, cuando se le da un "programa" apropiado, puede tomar el "programa" de otra máquina de Turing y simularlo en una entrada arbitraria. Si tuviera un lenguaje que tuviera prohibido implementar un intérprete de Python, no sería Turing completo.

Ejemplos de idiomas completos de Turing

Si su idioma tiene memoria de acceso aleatorio infinito, ejecución condicional y alguna forma de ejecución repetida, probablemente Turing esté completo. Hay sistemas más exóticos que aún pueden lograr todo lo que una máquina Turing puede hacer, lo que los hace completos también:

• Cálculo lambda sin tipo
• El juego de la vida de Conway
• Plantillas C ++
• Prólogo

Básicamente, la integridad de Turing es un requisito conciso, una recursión ilimitada.

Ni siquiera limitado por la memoria.

Pensé en esto independientemente, pero aquí hay una discusión sobre la afirmación. Mi definición de LSP proporciona más contexto.

Las otras respuestas aquí no definen directamente la esencia fundamental de la integridad de Turing.

Turing completo significa que es al menos tan poderoso como una máquina de Turing . Esto significa que cualquier cosa que pueda ser calculada por una máquina de Turing puede ser calculada por un sistema Turing Complete.

Nadie ha encontrado aún un sistema más poderoso que una máquina de Turing. Entonces, por el momento, decir que un sistema es Turing Complete es lo mismo que decir que el sistema es tan poderoso como cualquier sistema informático conocido (ver Tesis de Church-Turing ).

En los términos más simples, un sistema completo de Turing puede resolver cualquier posible problema computacional.

Uno de los requisitos clave es que el tamaño del bloc de notas sea ilimitado y que sea posible rebobinar para acceder a escrituras anteriores en el bloc de notas.

Así, en la práctica, ningún sistema es completo de Turing.

Más bien, algunos sistemas se aproximan a la integridad de Turing al modelar la memoria ilimitada y realizar cualquier cálculo posible que pueda caber dentro de la memoria del sistema.

Creo que la importancia del concepto "Turing Complete" radica en la capacidad de identificar una máquina de computación (no necesariamente una "computadora" mecánica / eléctrica) que puede hacer que sus procesos se deconstruyan en instrucciones "simples", compuestas de más simples y más simples. instrucciones, que una máquina Universal podría interpretar y luego ejecutar.

Recomiendo encarecidamente el Turing anotado

@ Mark creo que lo que estás explicando es una mezcla entre la descripción de Universal Turing Machine y Turing Complete.

Algo que es Turing Complete, en un sentido práctico, sería una máquina / proceso / computación capaz de ser escrita y representada como un programa, para ser ejecutada por una Máquina Universal (una computadora de escritorio). Aunque no tiene en cuenta el tiempo o el almacenamiento, como lo han mencionado otros.

Lo que entiendo en palabras simples:

Turing completo: un lenguaje / programa de programación que puede hacer cómputo es Turing completo.

Por ejemplo :

1. ¿Puedes agregar dos números usando solo HTML ? (La respuesta es ' No ', debe usar javascript para realizar la suma). Por lo tanto, HTML no está completo.

2. Los lenguajes como Java, C ++, Python, Javascript, Solidity for Ethereum, etc. son Turing Complete porque puedes hacer cálculos como agregar dos números usando estos lenguajes.

Espero que esto ayude.

Está completo si puede probar y ramificarse (tiene un 'si')

Una máquina Turing requiere que cualquier programa pueda realizar pruebas de condición. Eso es fundamental.

Considere un reproductor de piano roll. El reproductor de piano puede tocar una pieza musical muy complicada, pero nunca hay una lógica condicional en la música. Está Turing completo.

La lógica condicional es tanto el poder como el peligro de una máquina que está Turing completa.

El piano roll está garantizado para detenerse siempre. No existe tal garantía para un TM. Esto se llama el "problema de detención".

Como dijo Waylon Flinn :

Turing completo significa que es al menos tan poderoso como una máquina de Turing.

Creo que esto es incorrecto, un sistema está completo de Turing si es exactamente tan poderoso como la Máquina de Turing, es decir, todos los cálculos realizados por la máquina pueden ser realizados por el sistema, pero también todos los cálculos realizados por el sistema pueden ser realizados por la máquina de Turing .

En términos prácticos de lenguaje familiares para la mayoría de los programadores, la forma habitual de detectar la integridad de Turing es si el lenguaje permite o permite la simulación de sentencias while sin límite anidadas (a diferencia del estilo Pascal para sentencias, con límites superiores fijos).

¿Puede una base de datos relacional ingresar latitudes y longitudes de lugares y caminos, y calcular el camino más corto entre ellos? Este es un problema que muestra que SQL no está completo.

Pero C ++ puede hacerlo y puede hacer cualquier problema. Así es.