¿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 que las máquinas Turing son un gran problema tiene que ver con el estudio de la informática clásica o de la teoría de la computación. Básicamente se trata de analizar las propiedades generales de una computadora, como las habilidades teóricas y las limitaciones que tiene una computadora, así como a qué nos referimos cuando hablamos de "computar" algo.

Un ejemplo de algo que uno podría estudiar usando Máquinas Turing es The Halting Problem.Si bien este problema es algo así como un ejercicio académico, tiene implicaciones 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 Turing Machines 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 "expresiones regulares" se debe a que son regular grammar, y el estudio de estas gramáticas (parte de la Teoría de la Computación) le proporcionará más información sobre qué tipos de problemas pueden resolver las expresiones regulares y cuáles no. Por ejemplo, una sintaxis tradicional de expresiones regulares no podrá resolver el siguiente problema: analizar un número N de caracteres 'a' en la entrada, y luego analizar el mismo número N de caracteres 'b'.

Si está interesado en un buen texto sobre este tipo de cosas, consulte Introduction to the Theory of Computation por Michael Sipser. Es bueno.

Answer 2

Una máquina de Turing es una máquina abstracta capaz de computación.

De Wikipedia:

máquinas de Turing son dispositivos de manipulación de símbolos abstractos básicos que, a pesar de su simplicidad, se pueden adaptar para simular la lógica de cualquier algoritmo informático. Fueron descritos en 1936 por Alan Turing. Las máquinas de Turing no están pensadas como una tecnología informática práctica, sino como un experimento mental sobre los límites de la computación mecánica. Por lo tanto, en realidad no fueron construidos. El estudio de sus propiedades abstractas arroja muchas ideas sobre la ciencia de la computación y la 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 matemáticamente orientada con una naturaleza "universal" similar fue presentada 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 Church-Turing. La tesis afirma 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 3

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

máquina

El Turing se dice que es en cierto estado, y luego un programa es una lista de transiciones, que tiene un estado actual y un símbolo debajo de la cabeza, lo que debe ser escrito en la cinta, lo sería el próximo estado, y donde la cabeza debería moverse.

Aquí es una Basic Turing Machine, implementado en JavaScript ...

Y un boceto:

Answer 4

máquina de Turing es una máquina abstracta que puede operar en una secuencia de datos y pueden cambiar su propio estado, así como los datos durante el funcionamiento, de acuerdo con alguna lógica.

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

Alimento para el pensamiento, para la mayoría.

Answer 5

¿Por qué las personas que diseñan aviones se preocupan por los hermanos Wright, o la ciencia detrás del "levantamiento" 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 el precursor de todas las computadoras modernas.

La teoría de la computación 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 las cosas de una manera que nunca hubiera tenido, y esas son cosas buenas.

Answer 6

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 importan las máquinas Turing porque nos ayudan a descubrir qué es imposible de lograr con computadoras reales (como su PC IBM). Si es imposible para una máquina de Turing realizar un cálculo en particular (como decidir el Halting Problem), entonces es lógico pensar que es imposible que su PC IBM realice ese mismo cálculo.

Answer 7

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

En primer lugar, 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. Bases son direccionales: por convención los extremos se llaman cinco prima y tres -El primer (5' , 3')
4. una base en una cadena de ARN puede atraer una base en otra cadena de ARN en "anti-paralelas complementarias pares", donde a se pega a U y C se pega a G.
5. Las bases se combinan en grupos de 3 para formar "codones" (palabras).
6. Hay 64 combinaciones posibles para los codones (4^3).
7. cada codón puede coincidir con un "anticodón".por ejemplo AUG < -> UAC
8. hay moléculas especiales portadoras ("tRNA") que tienen particulares anticodones y están unidos a aminoácidos específicos (proteínas).

El funcionamiento del ribosoma es simple:

1. la transcripción se inicia en un "comienzo codón", que define la "lectura marco"
2. transcripción procede siempre en el 5' -> 3 'dirección
3. el codón bajo el marco de lectura es emparejado con un tRNA 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 bastidor avanza entonces 3 bases en el siguiente codón, y la proteína se extiende continuamente
7. al encontrar una "parada" codón, la traducción se termina, no amino el ácido se une 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 8

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

Algo que otros no lo han señalado: Su IBM PC es una máquina de Turing. Más precisamente, es equivalente a él, 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 hacerlo.

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

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

Aquí está: la gente habla de las máquinas de Turing porque es una forma precisa y precisa de decir qué es una "computadora", sin tener que describir todos los detalles de la arquitectura de la CPU, sus limitaciones, etc.

Answer 9

Además de la entrada de Wikipedia, es posible que desee recoger el libro The Annotated Turing de Charles Petzold.Subtitulado "Una visita guiada a través del histórico documento de Alan Turing sobre computabilidad y la máquina de Turing", incluye el documento completo, dividido en fragmentos con muchos discursos 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 ingresa un bucle infinito cuando no acepta la cadena.

cinta actúa como una memoria, reglas de transición actúa como 'si entonces si' condiciones