Máquina de Turing (MT)

Una máquina de Turing es el concepto teórico de una máquina capaz de resolver de manera formal problemas.
Es la base teórica de la computación.

La máquina de turing esta formada por dos partes.

1. Una cinta infinita (bien en una dirección o en ambas) .
2. Un cabezal que la recorre , lee, y escribe en ella .
   El cabezal lee borra el valor y escribe.
3. Tabla de estados.

Sea $\Gamma$ un conjunto finito de elementos, con uno de ellos $b$ carácter en blanco, un conjunto ordenado e infinito $L$ y un conjunto de estados finitos $Q$ , en estos estados finitos, hay que destacar $q_0$ estado de inicio y $\{ q_{f_1}, ..., q_{f_n} \}$ estados finales, y una ley de composición interna $ \lambda $ definida como: $$ \lambda : Q \times \Gamma \longrightarrow Q \times \Gamma \times L $$ con $L$ un desplazamiento a izquierda a derecha o de permanencia en este conjunto ordenado, Esto es una máquina de turing

Esta estructura representa toda la posibilidad de algoritmos existentes.