Máquina de Turing o Características

Máquina de Turing

o Características

La máquina de Turing es de tipo teórico y trabaja con el concepto de algoritmo, entendido como la descripción de un proceso finito, sin ambigüedades y con pasos definidos. Un proceso sólo será computable (con solución algorítmica) si la máquina partiendo de un estado inicial, encuentra la solución o estado final. Cuando el proceso no puede representarse con la máquina de Turing en un tiempo finito, se dice que no es computable y este tipo de problemas se conocen como “problemas indecibles”. La máquina de Turing utiliza:

* Un alfabeto finito con símbolos específicos que permitirán representar un proceso dado

* Una cinta infinita dividida en celdas donde algunas de las celdas contendrán los símbolos que en su conjunto representarán el proceso

o Funcionamiento

Inicia con un control finito que sólo puede adoptar un estado exclusivo. Normalmente el control apunta a la primera celda de la cinta infinita, adoptando un estado inicial y, al recibir un estímulo externo, se analiza el estado y símbolo de la celda, entonces, se recibe como respuesta otro símbolo, tomando además la decisión de avanzar, retroceder o quedarse estacionado en la celda a la que apunta. Este tipo de codificación genera parejas de datos que pueden considerarse como estímulo- reacción.

Al final del proceso, las celdas de la cinta que estuvieron involucradas en los estímulos y reacciones, contienen en su conjunto una serie de símbolos que describen la solución encontrada. Durante todo el proceso pueden surgir uno o varios finales que indican al control finito que de detenga, dada por terminada la computación del proceso. Cada máquina de Turing que se programa, únicamente puede resolver el problema particular que se plantea y nada más.

...