Máquinas de Turing

Introducción
Una máquina de Turing es una máquina de computación teórica que fue inventada por Alan Turing que sirve como un modelo para el cálculo matemático. Estos dispositivos son solo teóricos que ayudan al estudio de algoritmos.

Una máquina de Turing consiste en una línea llamada cinta, la cual contiene una serie de celdas, Una cabeza lee estos símbolos y realiza diferentes acciones deacuerdo a su conjunto de instrucciones, esta puede moverse hacia atrás y hacia adelante. La máquina de Turing cuenta con un programa de ejecución, y se puede decir que cada máquina Turing se crea para realizar una aplicación, pues no existen formas para cargar o alterar un programa.

El ejemplo más usado de máquinas de Turing es aquel que solo cuenta con una cabeza y una cinta, pero existen mástipos de máquinas de Turing, por ejemplo se pueden tener múltiples cintas o una cinta con múltiples cabezas.


Máquinas de Turing
Una máquina de Turing es aquella que a partir de una maquina representada por m simula el comportamiento de esta sobre una cadena de entrada representada por w. Una máquina de Turing es una especie de máquina de estados. En cualquier momento la máquina se encuentra en unacualquiera de un número finito de estados. Las instrucciones para una máquina de Turing consisten en condiciones específicas bajo las cuales se podrá realizar la transición entre un estado y otro.

Algunas de las características de las máquinas de Turing son las siguientes:
Las celdas solo almacenas un símbolo
La capacidad de almacenamiento es ilimitado
Se puede acceder al contenido de la celdadesde cualquier sentido (izquierda o derecha)

m se compone por una tupla de 7 elementos (Q,∑, Γ,q0,b,F, δ) donde:
Q es un conjunto finito de estados
∑ es el alfabeto de entrada
Γ es el alfabeto de la cinta
q0 es el estado inicial
b es el símbolo de vacío, este no se encuentra en ∑
F es el conjunto de estados finales
δ es la función de transición

Las máquinas de Turing no son físicas, más bien sonelementos matemáticos o algoritmos. Las acciones que pueden ser llevadas a cabo por la máquina son simples.

Las máquinas de Turing más simples se componen de una cinta de papel de longitud indefinida; normalmente se representa la cinta como horizontal con las células de izquierda a derecha. La cinta tiene un extremo, en la palabra izquierda, y se extiende infinitamente más a la derecha. Cadacélula es capaz de contener un símbolo.

Hay una cabeza que se escanea una sola célula en la cinta, decidir si se escribir un nuevo símbolo en su lugar, y luego mover hacia la izquierda o la derecha para para escanear las siguientes células.

La acción de una máquina de Turing se determina por el estado actual en que se encuentra la máquina y por el símbolo que se está escaneado por la cabezauna tabla de reglas de transición, que sirven como el programa o guía para la máquina. Como acciones, una máquina de Turing, como ya se había mencionado, puede escribir un símbolo en la celda actual de la cinta o se puede mover la cabeza de una celda a la izquierda o a la derecha a estos movimientos se les denomina reglas de transición.

Si la máquina termina en un estado en el que no hay ningunaregla de transición que puede ser realizada se detiene la máquina.

Una cadena w es aceptada por una máquina de Turing m si al realizar todas las acciones correspondientes según los estados, llega a un estado final.

Existen algunas variantes de las máquinas de Turing como lo son:
Máquina de Turing multicintas: es como una máquina ordinaria con muchas cintas. Cada cinta tiene su propia cabeza dela cinta. Inicialmente la cadena de entrada se encuentra en la cinta 1 y las otras cintas están en blanco. La función de transición se modifica para permitir la lectura, escritura y movimiento de todas las cintas simultáneamente.
Máquina de Turing Multidimensional: Un ejemplo de esta variación sería una cinta de dos dimensiones que se extienda hacia abajo y hacia arriba, al igual que hacia la...