Máquina de Turing como función
Si queremos definir la Máquina de Turing en términos de función, podríamos decir que es:
una función cuyo dominio se encuentra en la cinta infinita y es en esta misma donde se plasma su codominio, esto es, todos los posibles valores de entrada se encuentran en la cinta y todos los resultados de su operación se plasman también en ella.
La Máquina de Turing es el antecedente más remoto de un autómata y, al igual que éste, puede definirse con varias herramientas: diagrama de estado, tabla de estado y función.
Hay problemas que pueden resolverse mediante una Máquina de Turing y otros no, a los primeros se les denomina problemas computables y a los segundos problemas no computables o problemas indecidibles, de ello derivan respectivamente, los procesos computables y los procesos no computables, a saber:
– Proceso computable: es aquel que puede implementarse en un algoritmo o Máquina de Turing y definirse en un lenguaje decidible. Un proceso computable puede implementarse como el programa de la Máquina de Turing.
– Proceso no computable: es aquel que no puede implementarse con una Máquina de Turing por no tener solución para todas sus posibles entradas.
El lenguaje en que se especifica es un lenguaje indecidible que no puede ser interpretado por una Máquina de Turing.
Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM
