computer-science - machine - turing significado
¿Qué es una máquina de Turing? (10)
¿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?
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 problema de detención ), entonces es lógico pensar que es imposible para su PC IBM realizar ese mismo cálculo.
¿Por qué las personas que diseñan aviones se preocupan por los hermanos Wright, o la ciencia detrás de "levantar" 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.
La máquina de Turing es una máquina abstracta que puede operar en una secuencia de datos y puede cambiar su propio estado así como también 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 buenos conocimientos y abstracciones si se trata de algoritmos, estados, datos, etc.
Alimento para el pensamiento, para la mayoría.
La máquina de Turing es una máquina de computación teórica inventada por Alan Turing para servir como un 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, escriba un nuevo símbolo en su lugar, y luego muévalo hacia la izquierda o hacia la derecha.
Se dice que la máquina de Turing está 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 escribirse en la cinta, cuál sería el siguiente estado y dónde la cabeza debería moverse.
Aquí hay una Máquina de Turing básica , implementada en JavaScript ...
Y un boceto:
máquina de turing http://weblog.fortnow.com/media/turing-machine.jpg
La razón por la que las máquinas de Turing son una gran cosa tiene que ver con el estudio de las ciencias clásicas de la computación o 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 El problema de la detención . 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 produce porque son una gramática regular , y el estudio de estas gramáticas (parte de la Teoría de la Computación) le dirá más acerca de 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 le interesa un buen texto sobre este tipo de cosas, consulte Introducción a la teoría de la computación por Michael Sipser. Es bueno.
Una máquina de Turing es una máquina abstracta capaz de computación.
De la Wikipedia:
Las máquinas de Turing son dispositivos abstractos básicos de manipulación de símbolos 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".
¡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 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 por completo 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 "tesis Church-Turing" (generalmente aceptada) afirma que cada dispositivo o modelo de cálculo no es tan poderoso como una máquina de Turing. 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, también se pueden adaptar a otros modelos. (Por ejemplo, a veces puede ser conveniente pensar en computación 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).
Así que ya está: la gente habla de las máquinas de Turing porque es una manera 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.
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.
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:
- El ARN se compone de una cadena de nucleótidos ("bases") que definen las letras del alfabeto genético.
- Hay 4 bases en el alfabeto de ARN: A, C, G, U.
- Las bases son direccionales: por convención los extremos se llaman cinco primos y tres primos (5 '', 3'')
- Una base en una cadena de ARN puede atraer una base en otra cadena de ARN en "pares complementarios antiparalelos", donde A se adhiere a U y C a Stickman.
- Las bases se combinan en grupos de 3 para formar "codones" (palabras).
- Hay 64 combinaciones posibles para los codones (4 ^ 3).
- cada codón puede coincidir con un "anti-codón". por ejemplo AUG <-> UAC
- hay moléculas transportadoras especiales ("ARNt") que tienen anticodón particulares y están unidas a aminoácidos específicos (proteínas).
La operación del ribosoma es simple:
- la transcripción se inicia en un "codón de inicio", que define el "marco de lectura"
- la transcripción siempre procede en la dirección 5 ''-> 3''
- el codón bajo el marco de lectura se combina con un ARNt específico que contiene un aminoácido específico
- el codón de inicio siempre codifica el aminoácido metionina.
- el nuevo aminoácido está unido a la proteína en crecimiento
- el marco luego avanza 3 bases hacia el próximo codón, y la proteína se extiende continuamente
- al encontrar un codón "detener", la traducción se termina, 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!
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.
La cinta actúa como memoria, las reglas de transición actúan como condiciones ''if then else''