¿Qué es Turing Completo?

Question

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

Puede usted dar una explicación sencilla, sin entrar en demasiados teóricos detalles?

Answer 1

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

Una Turing Completo sistema de medios de un sistema en el que se puede escribir un programa que encuentre la respuesta (aunque sin garantías en cuanto a tiempo de ejecución o de la memoria).

Por lo tanto, si alguien dice: "mi nueva cosa es Turing Completo" que significa en principio (aunque a menudo no en la práctica) que podría ser utilizado para resolver cualquier problema de cálculo.

En algún momento es un chiste...un hombre escribió una Máquina de Turing simulador en el vi, por lo que es posible decir que vi es el único motor de cálculo nunca falta en el mundo.

Answer 2

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

Alan Turing creó una máquina que puede tomar un programa y ejecutar ese programa, y muestra el resultado.Pero luego tuvo que crear máquinas diferentes para los diferentes programas.Así que él creó "Máquina de Turing Universal" que puede tomar CUALQUIER programa y ejecutarlo.

Los lenguajes de programación son similares a las máquinas (aunque virtual).Ellos toman los programas y su ejecución.Ahora, un lenguaje de programación se denomina "Turing completo", si que se puede ejecutar cualquier programa(independientemente del idioma) que una máquina de Turing puede ejecutar dado el tiempo suficiente y la memoria.

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

La mayoría de los modernos lenguajes de programación como Java, JavaScript, Perl, etc son todos turing completo porque todos tienen que implementar todas las características necesarias para ejecutar los programas, como la suma, la multiplicación, la condición if-else, instrucciones return, formas de almacenar/recuperar/borrar datos, y así sucesivamente.

Actualización:Usted puede aprender más en mi blog: "JavaScript Es Turing Completo", — Explicó

Answer 3

De wikipedia:

Turing integridad, nombrado después de que Alan Turing, es importante que cada diseño posible para una computación dispositivo tan avanzado puede ser emulado por una máquina de Turing universal — un la observación que se ha conocido como la tesis de Church-Turing.Por lo tanto, un máquina que puede actuar como un universal Máquina de Turing puede, en principio, realizar cualquier cálculo que cualquier otro computadora programable es capaz de hacer.Sin embargo, esto no tiene nada que ver con el esfuerzo necesario para escribir un programa para la máquina, el tiempo que puede tardar para que la máquina realice el cálculo, o cualquier capacidades de la la máquina puede poseer que no están relacionados para el cálculo.

Mientras que en verdad Turing-completo de máquinas es muy probable que físicamente imposible, ya que requieren de un espacio de almacenamiento ilimitado, Turing integridad es a menudo vagamente se atribuye a las máquinas físicas o los lenguajes de programación que sería universal si tenían ilimitado de almacenamiento.Todas las computadoras modernas son Turing-completo en este sentido.

No sé cómo puede ser más de no-técnica que, excepto por decir "turing completo significa" capaz de responder a computable problema dado suficiente tiempo y espacio".

Answer 4

Informal Definición

Una Turing completo idioma es uno de los que puede realizar cualquier cálculo.El Tesis De Church-Turing los estados que cualquier ejecutables de cálculo puede ser realizado por una máquina de Turing.Un Máquina de Turing es una máquina con infinita memoria de acceso aleatorio y de un número finito de 'programa' que indica cuando se debe leer, escribir, y se mueven a través de la memoria, cuando debería terminar con un resultado determinado, y lo que debe hacer a continuación.La entrada a una máquina de Turing es poner en su memoria antes de que comience.

Cosas que pueden hacer que un idioma NO es Turing completo

Una máquina de Turing puede tomar decisiones basándose en lo que ve en la memoria - El "lenguaje" que sólo 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 correr para siempre - Si tomamos Java, Javascript o Python y eliminado la posibilidad de hacer cualquier tipo de bucle GOTO, o la llamada a la función, no es Turing completo porque no se puede realizar un cálculo arbitrario que no termina nunca. Coq es un teorema de armario que no puede expresar programas que no terminan, así que no es Turing completo.

Una máquina de Turing puede utilizar infinito de la memoria - Un lenguaje que era exactamente igual que Java, pero iba a terminar de una vez se usa más de 4 Gigabytes de memoria no se Turing completo, debido a que una máquina de Turing puede utilizar infinito de la memoria.Esta es la razón por la que no podemos realmente construir una máquina de Turing, pero Java es todavía una Turing completo idioma porque el Java idioma no tiene ninguna restricción impide el uso infinito de la memoria.Esta es una razón de expresiones regulares no son Turing completo.

Una máquina de Turing tiene memoria de acceso aleatorio - Un lenguaje que sólo permite trabajar con la memoria a través de push y pop las operaciones de una pila no se Turing completo.Si tengo un "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 propia ) más adelante empujando cuando ve ( y apareciendo cuando se ve ).Sin embargo, no me pueden decir si cada ( tiene su propio ) más tarde y cada [ tiene su propio ] más tarde (tenga en cuenta que ([)] esta cumple con los criterios, pero ([]] no lo hace).Una máquina de Turing puede utilizar su memoria de acceso aleatorio a la pista ()'s y []'s por separado, pero este lenguaje con sólo 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 concedió un 'programa', puede tomar otra máquina de Turing del 'programa' y simular arbitrarias de entrada.Si usted tenía un idioma que fue prohibida a partir de la implementación de un intérprete de Python, no es Turing completo.

Ejemplos de Turing completo idiomas

Si el lenguaje tiene una infinidad de memoria de acceso aleatorio, de ejecución condicional, y alguna forma de ejecución repetida, probablemente es Turing completo.Hay otros sistemas más exóticos que aún pueden lograr todo lo que una máquina de Turing se puede, lo que los hace Turing completo también:

• Sin cálculo lambda
• Conway juego de la vida
• Las Plantillas De C++
• Prólogo

Answer 5

Fundamentalmente, Turing-integridad es una concisa requisito, sin límites de recursividad.

Ni siquiera delimitada por la memoria.

Pensé que de esta forma independiente, pero he aquí algunos de discusión de la afirmación. Mi definición de LSP proporciona más contexto.

Las otras respuestas aquí no directamente de definir la esencia fundamental de Turing-completo.

Answer 6

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

Nadie ha encontrado aún un sistema más potente que una Máquina de Turing.Así que, por el momento, diciendo que un sistema es Turing Completo es lo mismo que decir que el sistema es tan poderoso como cualquier sistema de computación (ver Tesis De Church-Turing).

Answer 7

En términos más simples, una de Turing-completo sistema capaz de resolver cualquier posible problema computacional.

Uno de los requisitos clave es el bloc de notas tamaño ilimitado y que es posible rebobinar previo de acceso se escribe en el bloc de notas.

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

Más bien, algunos sistemas aproximado de Turing-integridad por el modelado de memoria ilimitado y la realización de cualquier posible computación que puede caber dentro de la memoria del sistema.

Answer 8

Creo que la importancia del concepto de "Turing Completo" está en la capacidad de identificar una máquina de computación (no necesariamente un mecánico/eléctrico "equipo") que puede tener sus procesos de ser deconstruido en "simple" instrucciones", compuesto de más y más simple de instrucciones, que una máquina Universal puede interpretar y ejecutar.

Recomiendo altamente El Anotado de Turing

@Marcos creo que lo que usted está explicando es una mezcla entre la descripción de la Máquina de Turing Universal y Turing Completo.

Algo que es Turing Completo, en un sentido práctico, sería una máquina/proceso/computación capaz de ser escrita y representada como un programa, que será ejecutado por una Máquina Universal (una computadora de escritorio).A pesar de que no toman en consideración por el tiempo de almacenamiento o, como se ha mencionado por otros.

Answer 9

Lo que yo entiendo en palabras simples:

Turing Completo : Un lenguaje de programación / programa que puede hacer el cálculo, es Turing completo.

Por ejemplo :

1. Se pueden añadir dos números usando Sólo HTML.(Ans es 'No'usted tiene que usar javascript para realizar la suma.), Por lo tanto HTML no es Turing Completo.

2. En lenguajes como Java , C++, Python, Javascript, Solidez de Etereum etc son Turing Completo porque se puede hacer el cálculo como suma de dos números usando esta idiomas.

Espero que esto ayude.

Answer 10

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 poderosa como la Máquina de Turing, es decir,cada cálculo realizado por la máquina se puede hacer por el sistema, sino también de todos los cálculos realizado por el sistema puede ser realizado por la máquina de Turing.

Answer 11

En la práctica, los términos del idioma familiar para la mayoría de los programadores, de la forma habitual para detectar Turing integridad es si el lenguaje permite o permite la simulación de las ilimitado mientras que las instrucciones (en contraposición a la de Pascal, al estilo de las declaraciones, con la fija límites superior).

Answer 12

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

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