¿Qué es Turing Completo?

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

Alan Turing creó una máquina que puede tomar un programa y ejecutar ese programa y mostrar algún resultado. Pero luego tuvo que crear diferentes máquinas para diferentes programas. Así que creó la "Máquina Universal de Turing" 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 complete", si eso se puede ejecutar cualquier programa (independientemente del idioma) que una máquina de Turing pueda ejecutar con suficiente tiempo y memoria.

Por ejemplo: Digamos que hay un programa que toma 10 números y los agrega. Máquina de Turing puede ejecutar fácilmente este programa. Pero ahora imagine por alguna razón su lenguaje de programación no puede hacer la misma adición entonces es Turing máquina incompleta. Por otro lado, si puede ejecutar cualquier programa como la máquina universal de turing puede ejecutar, entonces es Turing completo.

La más moderna los lenguajes de programación como Java, JavaScript, Perl, etc. son turing completos porque todos implementan todas las características necesarias para ejecutar programas como suma, multiplicación, condición if-else, declaraciones de retorno, formas de almacenar/recuperar/borrar datos, etc.

Actualización: Puedes obtener más información en mi entrada de blog: "JavaScript Is Turing Complete" - Explained

De wikipedia:

Turing completity, el nombre de Alan Turing, es significativo en que cada diseño plausible para una computación dispositivo hasta ahora avanzado puede ser emulado por una máquina universal de Turing-an observación que se ha conocido como la tesis de Church-Turing. Así, un máquina que puede actuar como un universal La máquina de Turing puede, en principio, realizar cualquier cálculo que cualquier otro computadora programable es capaz de. 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 de la máquina puede poseer que no están relacionados a la computación.

Mientras verdaderamente Turing-máquinas completas es muy probable que físicamente imposible, ya que requieren almacenamiento ilimitado, Turing integridad es a menudo vagamente atribuidas a máquinas físicas o lenguajes de programación que serían universal si tuvieran ilimitado almacenamiento. Todos los ordenadores modernos son Turing-completo en este sentido.

No se como puedes ser más no técnico que eso excepto diciendo "turing completo significa 'capaz de responder problema computable dado suficiente tiempo y espacio'".

Definición informal

Un lenguaje Turing completo es aquel que puede realizar cualquier cálculo. La Tesis de Church-Turing establece que cualquier cálculo realizable puede ser realizado por una máquina de Turing. Una máquina de Turing es una máquina con una 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 es ponlo en su memoria antes de que empiece.

Cosas que pueden hacer que un lenguaje NO Turing SEA completo

Una máquina de Turing puede tomar decisiones basadas en lo que ve en la memoria - El 'lenguaje' que solo admite +, -, *, y / en enteros no es Turing completo porque no puede hacer una elecció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 la función, no sería Turing completa 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 es Turing completo.

Una máquina de Turing puede usar infinite memory - Un lenguaje que era exactamente igual a Java, pero que terminaría una vez que utilizara más de 4 Gigabytes de memoria, no sería Turing completo, porque una máquina de Turing puede usar memoria infinita. Esta es la razón por la que no podemos realmente construir una máquina de Turing, pero Java sigue siendo un lenguaje completo de Turing porque el lenguaje Java no tiene ninguna restricción que le impida usar memoria infinita. Esta es una razón por la que las expresiones regulares no están completas.

Una máquina de Turing tiene memoria de acceso aleatorio - Un lenguaje que solo le permite trabajar con memoria a través de push y pop operaciones a una pila no sería Turing completo. Si tengo un el 'lenguaje' que lee una cadena de caracteres una vez y sólo se puede utilizar la memoria empujando y surgiendo de una pila, me puede decir si cada una de las ( en la cadena tiene su propio ) más adelante empujando cuando ve ( y apareciendo cuando ve ). Sin embargo, no puede decirme si cada ( tiene su propio ) más adelante y cada [ tiene su propio ] más adelante (tenga en cuenta que ([)] cumple con este criterio, pero ([]] no lo hace). Una máquina de Turing puede usar su memoria de acceso aleatorio para rastrear ()'s y []'s 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 al que se le prohibiera implementar un intérprete de Python, no sería Turing completo.

Ejemplos de lenguajes completos de Turing

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

• Cálculo lambda no tipificado
• El juego de la vida de Conway{[64]]}
• Plantillas de C++
• Prolog

Fundamentalmente, Turing-completitud es un requisito conciso, recursión ilimitada.

Ni siquiera limitado por la memoria.

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

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

Turing Completo significa que es al menos tan potente como una Máquina de Turing. Esto significa que cualquier cosa que pueda ser computada por una Máquina de Turing puede ser computada por un sistema completo de Turing.

Nadie ha encontrado todavía un sistema más poderoso que una máquina de Turing. Por lo tanto, por el momento, decir que un sistema es Turing Completo es lo mismo que decir que el sistema es tan poderoso como cualquier sistema de computación conocido (ver Tesis de Church-Turing).

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

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

Por lo tanto, en la práctica ningún sistema es Turing completo.

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

Creo que la importancia del concepto "Turing Completo" está en la capacidad de identificar una máquina de computación (no necesariamente una "computadora" mecánica/eléctrica) que puede tener sus procesos deconstruidos en instrucciones "simples", compuestas de instrucciones más simples y más simples, 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 la Máquina de Turing y Turing Completa.

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

Como Waylon Flinn dijo :

Turing Completo significa que es al menos tan potente como una máquina de Turing.

Creo que esto es incorrecto, un sistema es Turing completo si es exactamente tan poderoso como la Máquina de Turing, es decir, cada computación hecha por la máquina puede ser hecha por el sistema, pero también cada computación hecha por el sistema puede ser hecha por la máquina de Turing.

En términos prácticos del lenguaje familiar 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 anidadas unbounded while (a diferencia del estilo Pascal para sentencias, con límites superiores fijos).

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

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