¿Qué es una máquina de Turing?

Question

¿Qué es una máquina de Turing y por qué la gente sigue mencionándola? ¡Mi PC IBM es todo lo que necesito para hacer mi cálculo! ¿Por qué a alguien le importan estas máquinas?

Answer 1

La razón por la cual las máquinas de Turing son un gran problema tiene que ver con el estudio de la ciencia de la computación clásica o la teoría de la computación. Básicamente se trata de analizar las propiedades generales de una computadora, como las capacidades teóricas y las limitaciones que tiene una computadora, así como lo que queremos decir cuando hablamos de & "; Computación &"; algo.

Un ejemplo de algo que uno podría estudiar usando Turing Machines es El problema de detención . Si bien este problema es algo así como un ejercicio académico, tiene implicaciones fácilmente tangibles en el mundo real. ¿Por qué no escribir un depurador que simplemente le dirá si su programa contiene o no bucles infinitos? El problema de detención establece que resolver este problema para el caso general es imposible.

El estudio de las máquinas de Turing también se presta para estudiar las gramáticas del lenguaje y sus clases, lo que conduce al desarrollo del lenguaje de programación. El término & Quot; expresiones regulares & Quot; surge porque son una gramática regular , y el estudio de estas gramáticas (parte de Theory of Computation ) le informará más sobre exactamente qué tipo de problemas pueden resolver las expresiones regulares y qué no pueden resolver. Por ejemplo, una sintaxis de expresión regular tradicional no podrá resolver el siguiente problema: analizar algún número N de caracteres 'a' en la entrada y luego analizar el mismo número N de char 'b'.

Si está interesado en un buen texto sobre este tipo de cosas, consulte Introducción a la teoría de la computación por Michael Sipser. Está bien.

Answer 2

La máquina de Turing es una máquina de computación teórica inventada por Alan Turing para servir como modelo idealizado para el cálculo matemático, básicamente es una forma simple de computadora, está compuesta por una cinta (una cinta de papel ), tiene una cabeza que puede leer los símbolos, escribir un nuevo símbolo en su lugar y luego moverse hacia la izquierda o hacia la derecha.

Se dice que la máquina Turing se encuentra en un cierto estado , y luego un programa es una lista de transiciones , que tiene un estado actual y un símbolo debajo de la cabeza, qué debería estar escrito en la cinta, cuál sería el siguiente estado y hacia dónde debería moverse la cabeza.

Aquí hay una Máquina básica de Turing , implementada en JavaScript ...

Y un boceto:

Answer 3

  

¡Mi PC IBM es todo lo que necesito para hacer mi cálculo!

Algo que otros no han señalado: su PC IBM es una máquina Turing. Más precisamente, es equivalente a esto, en el sentido de que cualquier cosa que su PC pueda hacer, una máquina de Turing puede hacer, y cualquier cosa que una máquina de Turing pueda hacer, su PC puede.

Específicamente, una máquina Turing es un modelo de computación que captura por completo la noción de computabilidad, sin dejar de razonar, sin todos los detalles específicos de la arquitectura de su PC.

La (generalmente aceptada) " Tesis de Church-Turing " afirma que cada dispositivo o modelo de computación no es más poderoso que una máquina de Turing. Entonces, muchos problemas teóricos (por ejemplo, clases como P y NP, la noción de & "; Algoritmo de tiempo polinómico &"; Y así sucesivamente) se expresan formalmente en términos de una máquina de Turing, aunque, por supuesto, También se pueden adaptar a otros modelos. (Por ejemplo, a veces puede ser conveniente pensar en el cálculo en términos del cálculo lambda, o la lógica combinatoria, o lo que sea ... todos son equivalentes en potencia entre sí, y también para su PC IBM).

Así que ahí lo tienes: la gente habla de las máquinas de Turing porque es una forma precisa y completa de decir qué & "; computadora &"; es decir, sin tener que describir cada detalle de la arquitectura de la CPU, sus restricciones, etc.

Answer 4

En realidad, hay ejemplos de máquinas de Turing en la naturaleza. Específicamente, el ribosoma , que traduce ARN en proteínas, implementa una máquina de Turing.

Primero, algunos antecedentes:

1. ARN se compone de una cadena de nucleótidos (& "; bases &";) que definen las letras del alfabeto genético.
2. Hay 4 bases en el ARN alfabeto - A, C, G, U.
3. Las bases son direccionales: por convención los extremos se llaman cinco primos y tres primos (5 ', 3')
4. Una base en una cadena de ARN puede atraer una base en otra cadena de ARN en & "; complementario antiparalelo pares " ;, donde A se adhiere a U y C se adhiere a G.
5. Las bases se combinan en grupos de 3 para formar & Quot; codones & Quot; (palabras).
6. Hay 64 combinaciones posibles para los codones (4 ^ 3).
7. cada codón puede coincidir con un " anti-codon " ;. por ejemplo AUG < - > UAC
8. hay moléculas transportadoras especiales (" tRNA ") que tienen particular anticodones y están unidos a aminoácidos específicos (proteínas).

El funcionamiento del ribosoma es simple:

La transcripción
1. se inicia en un " inicio codón " ;, que define la lectura " marco "
2. la transcripción siempre procede en la dirección 5 '- > 3'
3. el codón debajo del marco de lectura es emparejado con un ARNt específico que contiene un aminoácido específico
4. el codón de inicio siempre codifica el aminoácido metionina.
5. el nuevo aminoácido está unido a la proteína en crecimiento
6. el marco avanza 3 bases hasta el siguiente codón, y la proteína se extiende continuamente
7. al encontrar un " stop " codón, termina la traducción, no se une ningún aminoácido y el ribosoma se disocia del ARNm.

Como puede ver, esta es una máquina de Turing muy simple que realiza la operación más compleja: ¡la naturaleza misma!

Answer 5

Una máquina de Turing es una máquina teórica que puede usarse para razonar sobre los límites de las computadoras. En pocas palabras, es una computadora imaginaria con memoria infinita.

Nos preocupamos por las máquinas Turing porque nos ayudan a descubrir lo que es imposible de lograr con computadoras reales (como su PC IBM). Si es imposible que una máquina de Turing realice un cálculo particular (como decidir el Problema de detención ), entonces es lógico pensar que es imposible que su PC IBM realice el mismo cálculo.

Answer 6

¿Por qué las personas que diseñan aviones se preocupan por los hermanos Wright, o la ciencia detrás de " lift " que permite volar aviones de ala fija?

Alan Turing es alabado como el padre de la informática moderna. La máquina de Turing es la precursora de todas las computadoras modernas.

La teoría de la computabilidad fue mi clase más difícil en la universidad, pero me alegro de haberla tomado. Me hizo pensar en cosas que nunca tendría, o pensar en cosas que nunca hubiera tenido, y esas son cosas buenas.

Answer 7

Una máquina de Turing es una máquina abstracta capaz de computar.

De Wikipedia:

  

Las máquinas de Turing son dispositivos básicos de manipulación de símbolos abstractos que, a pesar de su simplicidad, pueden adaptarse para simular la lógica de cualquier algoritmo informático. Fueron descritos en 1936 por Alan Turing. Las máquinas de Turing no pretenden ser una tecnología informática práctica, sino un experimento mental sobre los límites de la computación mecánica. Por lo tanto, no se construyeron realmente. Estudiar sus propiedades abstractas proporciona muchas ideas sobre ciencias de la computación y teoría de la complejidad.

     

Una máquina de Turing que puede simular cualquier otra máquina de Turing se llama máquina universal de Turing (UTM, o simplemente una máquina universal). Una definición más orientada matemáticamente con una & Quot; universal & Quot; La naturaleza fue introducida por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelazó con el de Turing en una teoría formal de la computación conocida como la tesis de Church-Turing. La tesis establece que las máquinas de Turing capturan la noción informal de método efectivo en lógica y matemáticas, y proporcionan una definición precisa de un algoritmo o 'procedimiento mecánico'.

Answer 8

La máquina de Turing es una máquina abstracta que puede operar en una secuencia de datos y puede cambiar su propio estado y los datos mientras opera, de acuerdo con alguna lógica.

Este es un concepto que forma la base de algoritmos, programas almacenados y computación en general. Proporciona buenas ideas y abstracciones si se trata de algoritmos, estados, datos, etc.

Alimento para el pensamiento, para la mayoría.

Answer 9

Además de la entrada de Wikipedia, es posible que desee recoger el libro The Annotated Turing por Charles Petzold. Subtitulado & "; Un recorrido guiado por el artículo histórico de Alan Turing sobre computabilidad y la máquina de Turing &"; Incluye el documento completo, dividido en fragmentos con mucho discurso sobre el tema, incluida una perspectiva histórica.

Answer 10

La máquina de Turing es equivalente a un algoritmo. Se detiene cuando acepta una cadena, rechaza o entra en un bucle infinito cuando no acepta la cadena.

La cinta actúa como memoria, las reglas de transición actúan como condiciones 'si entonces más'