maquinas 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 parasimular 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.
La máquina de Turing fue descrita por AlanTuring como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society, La máquina de Turing no está diseñada como una tecnología de computación práctica, sino comoun dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.
Importancia
Lo que le da laimportancia a este dispositivo es el hecho de que es capaz de resolver cualquier problema matemático con la condición de que haya sido reducido a un algoritmo.


De hecho Turing demostró con estoque hay problemas matemáticos que incluso no pueden tener solución.


Por consiguiente, a como lo comprendo, puedo decir que la máquina de turing es una ayuda para los problemas matemáticos,en los cuales podemos ver si hay o no una solución real para estos.
Representación como diagrama de estados
Las máquinas de Turing pueden representarse mediante grafos particulares, tambiénllamados diagramas de estados finitos, de la siguiente manera:
Los estados se representan como vértices, etiquetados con su nombre en el interior.
Una transición desde un estado a otro, se representamediante una arista dirigida que une a estos vértices, y está rotulada por símbolo que lee el cabezal/símbolo que escribirá el cabezal, movimiento del cabezal.
El estado inicial se caracterizapor 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....