Maquina De Turing

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de un computador.

Una máquina de Turing que es capaz de simular cualquier otra máquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina universal). Una definición más matemáticamente orientada, con una similar naturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una formal teoría de la computación conocida como la tesis de Church-Turing. La tesis señala que las máquinas de Turing de hecho capturan la noción informal de un método eficaz en la lógica y las matemáticas y proporcionan una precisa definición de un algoritmo o 'procedimiento mecánico'.

Las máquinas de Turing pueden representarse mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:

Esta máquina de Turing está definida sobre el alfabeto , posee el conjunto de estados , con las transiciones que se pueden ver. Su estado inicial es y el estado final es , el lenguaje de salida

siendo el símbolo denominado "blanco". Esta máquina reconoce la expresión regular de la forma con .

• Los estados se representan como vértices, etiquetados con su nombre en el interior.

• Una transición desde un estado a otro, se representa mediante una arista dirigida que une a estos vértices, y esta rotulada por símbolo que lee el cabezal/símbolo que escribirá el cabezal, movimiento del cabezal.

• El estado inicial se caracteriza por tener una arista que llega a él y que no proviene de ningún otro vértice.

• El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.

...