En el presente documento se sintetizarán conceptos básicos a cerca de la Máquina de Turing: componentes de la máquina, funcionamiento y aplicaciones. El trabajo realizado es netamente de investigación y compilación de conceptos de diferentes bibliografías. Se hará énfasis sobre todo en el funcionamiento de la máquina y como esta puede comprenderse mejor con Teoría de Autómatas y Lenguajes Formales, finalmente se mencionarán algunas de sus aplicaciones más importantes en la actualidad.
Cabe destacar que el inventor de dicha máquina fue Alan Mathison Turing (Paddington, Londres; 23 de junio de 1912-Wilmslow, Cheshire; 7 de junio de 1954), fue un matemático, lógico, informático teórico, criptógrafo, filósofo, biólogo teórico, maratoniano y corredor de ultradistancia británico. Es por eso que se ha denominado la máquina como el apellido de su creador. También Alan Turing es considerado uno de los padres de la ciencia de la computación y precursor de la informática moderna. Proporcionó una influyente formalización de los conceptos de algoritmo y computación: la máquina de Turing. Formuló su propia versión que hoy es ampliamente aceptada como la tesis de Church-Turing (1936).
Durante la segunda guerra mundial, trabajó en descifrar los códigos nazis, particularmente los de la máquina Enigma, y durante un tiempo fue el director de la sección Naval Enigma de Bletchley Park. Se ha estimado que su trabajo acortó la duración de esa guerra entre dos y cuatro años. Tras la guerra, diseñó uno de los primeros computadores electrónicos programables digitales en el Laboratorio Nacional de Física del Reino Unido y poco tiempo después construyó otra de las primeras máquinas en la Universidad de Mánchester.
MAQUINA DE TURING
La llamada “Máquina de Turing” es en realidad un modelo matemático consistente en un autómata que es capaz de “implementar cualquier problema matemático expresado a través de un algoritmo”. A pesar de esta definición tan complicada, en realidad la máquina de Turing destaca por su simplicidad pues manipula símbolos sobre una tira de cinta siguiendo una serie de reglas. A pesar de esta simplicidad, una máquina de Turing puede adaptarse para que simule la lógica de cualquier algoritmo de computador, de ahí su enorme potencial y valor.
Como su propio nombre indica, la máquina de Turing fue creada por el matemático inglés Alan Turing, un genio en muchos campos, pero especialmente en la criptografía y la lógica. Originalmente la denominó “Máquina de Computación Lógica” siendo una de las mayores aportaciones pues despejó el camino de la ciencia de la Computación, de la Informática moderna.
Componentes de la máquina de Turing.
· Una
cinta de longitud infinita dividida en celdas (cada celda puede tener solamente
un símbolo tomado de un diccionario de símbolos predefinido).
Un control finito que tiene la capacidad de examinar el algún símbolo de alguna celda y tomar una decisión que depende del símbolo observado y del estado en que se encuentre el control finito. El control es finito porque puede estar solamente en alguno de los estados posibles, habiendo solamente un número finito de ellos.
Se supone un diccionario de símbolos finto.
Se puede observar la cinta de longitud infinita, que en este caso se encuentra en la primera celda de la cinta con el símbolo S 1.
·
Se
debe entender a la máquina como un ser vivo que reacciona de maneras
preestablecidas ante estímulos provenientes del exterior (en este caso la
cinta).
·
Un
estímulo lo será si ocurren dos sucesos: Que el control finito se encuentre en
cierto estado E 1. En la celda actual existe un símbolo S 1
Características de la Maquina de Turing
Las principales características de la
máquina de Turing eran las siguientes:
·
La
entrada que tiene la cinta antes de que comience el cálculo debe consistir en
un número finito de símbolos.
·
La
cinta de la máquina tiene una de longitud ilimitada.
·
El
cabezal de lectura y escritura puede ser programable.
·
La
máquina de Turing es capaz de hacer seis tipos de operaciones fundamentales:
leer, escribir, mover hacia la izquierda, mover hacia la derecha, cambiar de
estado y detenerse.
·
Tiene
la capacidad de computar cualquier cosa que cualquier computadora moderna pueda
calcular.
·
Está
formada por un alfabeto de entrada y uno de salida y por un símbolo especial
llamado blanco.
Funcionamiento de la
máquina de Turing.
La máquina de Turing consta de un
cabezal lector/escritor y una cinta infinita en la que el cabezal lee el
contenido, borra el contenido anterior y escribe un nuevo valor. Las
operaciones que se pueden realizar en esta máquina se limitan a:
·
Mover
el cabezal lector/escritor hacia la derecha.
·
Mover
el cabezal lector/escritor hacia la izquierda.
El cómputo se determina a partir de una tabla de estados de la forma:
(estado, valor) à (nuevo estado, nuevo valor, dirección)
Esta tabla toma como parámetros el
estado actual de la máquina y el carácter leído de la cinta, dando la dirección
para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en
la cinta.
La memoria es la cinta de la máquina que se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado "blanco". Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, "si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha".
Aplicaciones y usos de
la Máquina de Turing
· Teoría de la Computación
Es una rama de las matemáticas y de las
ciencias de la computación que centra su interés en las limitaciones y
capacidades fundamentales de las computadoras. Específicamente esta teoría
busca modelos matemáticos que formalizan el concepto de hacer un cómputo y la
clasificación de problemas de acuerdo a su grado de complejidad.
Alan Turing demostró con su Máquina que
existen problemas imposibles de ser resueltos algorítmicamente, siendo el
Problema de la Parada el más importante. Para estos problemas no existe ni
existirá ningún algoritmo que los pueda resolver, no importando la cantidad de
tiempo o memoria se disponga en una computadora. Asimismo, con la llegada de
las computadoras modernas se constató que algunos problemas resolubles en
teoría eran imposibles en la práctica, puesto que dichas soluciones necesitaban
cantidades irrealistas de tiempo o memoria para poderse encontrar.
· Problema De La Parada
El problema de la parada o problema de
la detención para máquinas de Turing consiste en: dada una MT M y una palabra
w, determinar si M terminará en un número finito de pasos cuando se ejecuta
usando w como entrada. Alan Turing demostró que este problema es indecidible,
ninguna máquina de Turing lo puede resolver.
· Maquinas Oráculo
La máquina con oráculo, es una Máquina
de Turing equipada con un oráculo que es capaz de contestar preguntas sobre la
pertenencia a un conjunto específico de números naturales. Una máquina oráculo
con el "conjunto parada" en su oráculo puede computar la función del
problema de la parada. Mientras este sería un ejemplo trivial del uso del
conjunto oráculo, muchas otras funciones de interés pueden ser computadas utilizando
el oráculo de la función de la parada. De hecho, esto permite que todas las
funciones recursivamente enumerables sean computables.
· Máquinas de Turing como generadoras de Lenguajes
Si pueden reconocer lenguajes, también
son capaces de generarlos.
· Entre muchos más.
Tipos de Máquina de
Turing.
Existen varios tipos de Máquinas de
Turing, todas caracterizadas por tener un comportamiento similar, entre ellas
están:
· Máquina de Turing con cinta infinita a ambos lados
Esta modificación de denota al igual que
una Máquina de Turing sencilla, lo que la hace diferente es que la cinta es
infinita tanto por la derecha como por la izquierda.
· Máquina de Turing con Cinta Multiplista
Es aquella mediante la cual cada celda
de la cinta de una maquina sencilla se divide en subceldas. Cada celda es capaz
de contener carios símbolos de la cinta. Se dice que la cinta tiene múltiples
pistas porque cada celda de esta Máquina de Turing contiene múltiples
caracteres, el contenido de las celdas de la cinta puede ser representado
mediante n-tuplas ordenadas. Los movimientos que realice esta máquina
dependerán de su estado actual y de la n-tupla que represente el contenido de
la celda actual. Debe mencionar que posee un solo cabezal al igual que una
Máquina de Turing sencilla.
· Máquina de Turing Multicinta
Las Máquinas de Turing con más de una
cinta consisten en un control finito con k cabezales lectores/escritores y k
cintas. Cada cinta es finita en ambos sentidos. La Máquina de Turing Multicinta
define su movimiento dependiendo del símbolo que está leyendo cada uno de sus
cabezales, las reglas de sustitución para cada uno de los símbolos y dirección
de movimiento para cada uno de los cabezales. Inicialmente empieza con la
entrada en la primera cinta y el resto de las cintas en blanco.
· Máquinas de Turing Multidimensional
Una Máquina de Turing multidimensional
es aquella cuya cinta se extiende infinitamente en más de una dirección,
ejemplo más básico sería el de una maquina bidimensional cuya cinta se
extendería infinitamente hacia arriba, abajo, izquierda o derecha.
· Máquinas de Turing No Deterministas
Es una Máquina de Turing en la que
pueden existir varias transiciones a partir del mismo estado y lectura del
cabezal. Esto significa que, dado un estado y un símbolo de entrada, es posible
elegir la transición a efectuar entre varias operaciones. Una Máquina de Turing
No Determinista se puede modelar como una Máquina de Turing con una entrada
adicional que permite seleccionar la transición a efectuar entre las varias
posibilidades a cada paso.
Se pueden reescribir las transiciones
añadiendo nuevos estados de manera que en cada caso la elección se efectué solo
entre dos opciones, con lo que el selector podría ser una señal de un bit. Todo
lenguaje aceptado por una Máquina de Turing No Determinista puede ser aceptado
por una Maquina de Turing Determinista.
· Máquina de Turing Universal
Es una Máquina de Turing capaz de simular
el comportamiento de cualquier Maquina de Turing sobre cualquier cadena de
entrada. Para poder construir una Máquina de Turing Universal es necesario
definir una codificación de las Máquinas de Turing, de manera que se pueda
controlar a la maquina por medio de su código.
Una Máquina de Turing, o MT, se
considera una cinta infinita dividida en casillas, cada una de las cuales
contiene un símbolo, y sobre la cual actúa un dispositivo que puede adoptar
diversos estados, y que lee un símbolo de la casilla sobre la que está situado.
En función de dicho símbolo y del estado actual, se pueden realizar tres
acciones siguientes: pasa a un nuevo estado, imprime un símbolo en lugar del
que acaba de leer y se desplaza a una posición hacia la izquierda, derecha, o
se detiene.
Existen diversas clasificaciones de las
Máquinas de Turing, atendiendo a los estados reconocidos, tipo de cinta,
cantidad o división de dichas cintas: MT con directiva de permanecer, MT con
cinta infinita en una dirección, MT en dos direcciones, MT multicinta, MT
Multidimensional, MT No determinista.
Las MT, de acuerdo a la clasificación de
los lenguajes formales de Chomsky, acepta los lenguajes tipo cero (0), llamados
lenguajes recursivamente enumerables.
La creación modular de una máquina de
Turing permite desarrollar máquinas complejas a partir de bloques elementales,
mediante diagramas de transiciones. La construcción de máquinas de Turing se
lleva a cabo mediante dichos diagramas de transición, y sus combinaciones.
Las MT han sido aplicadas en el
desarrollo de la teoría computacional y en las llamadas máquinas oráculo,
generadores de funciones, calculadoras de funciones, y generadores de lenguaje.
Cabe destacar que son muy importantes
para comprender de una manera más detallada los Autómatas y los Lenguajes
Formales al igual que es importante resaltar el genio del Sr. Turing al poder
haber desarrollado una Máquina tan compleja y con tantas aplicaciones prácticas
que perduran en la actualidad, con componentes sencillos y una lógica
sensacional logro convertirse un uno de los padres de la computación y la
informática.
https://es.wikipedia.org/wiki/Alan_Turing
https://formatalent.com/que-es-una-maquina-de-turing-y-como-funciona/
https://borrowbits.com/2013/03/maquinas-de-turing/
http://maquinasdeturing.blogspot.com/2010/08/3-que-es-una-maquina-de-turing-y-como.html
https://slidetodoc.com/el-concepto-de-computabilidad-y-la-mquina-de/
https://www.euston96.com/maquina-de-turing/
https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
http://www.revistasbolivianas.org.bo/pdf/riei/v8n1/v8n1_a04.pdf
https://prezi.com/z14aeukb7rf7/aplicaciones-de-maquinas-de-turing/
http://maquinasdeturing.blogspot.com/2010/08/5-clasificacion-de-las-maquinas-de.html
http://maquinasdeturing.blogspot.com/2010/08/9-ejemplos-de-aplicacion-de-las-mt.html