La Máquina
de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse
como un modelo abstracto que formaliza la idea Intuitiva de algoritmo.
(MT) Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.
Su
funcionamiento se basa en una función de transición, que recibe un estado
inicial y una cadena de caracteres (la cinta, la cual es finita por la
izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de
la cinta , borrando el símbolo , escribir el nuevo símbolo perteneciente al
alfabeto de salida y finalmente avanza a la izquierda o a la derecha (solo una
celda a la vez), repitiendo esto según se indique en la función de transición,
para finalmente detenerse en un estado final o de aceptación, representando así
la salida.
La caja es tan fina que solo el trozo de
cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tiene una serie
de estados internos finitos que también se pueden numerar en binario. Para
llevar a cabo algún algoritmo , la máquina se inicializa en algún estado
interno arbitrario. A continuación , se pone en marcha y la máquina lee el bit
que se encuentra en ese momento en su interior y ejecuta alguna operación con
ese bit (lo cambia o no, dependiendo de su estado interno). Después se mueve
hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de
la misma manera.
