Mathematica Eterna
Acceso abierto

abstracto

Métodos para comprender los cálculos de la máquina de Turing

Juan Nixon

Este artículo es una investigación ab initio sobre las formas de describir el comportamiento de la máquina de Turing (TM). Se muestra cómo los resultados de una TM restringida a una longitud finita de cinta se pueden utilizar para acelerar cualquier cálculo de TM. El conjunto no redundante de tales reglas se conoce como reglas (de computación) regulares irreducibles (IRR) y se describe un algoritmo para generarlas para cualquier TM para una longitud de cinta arbitraria. Este algoritmo se ha implementado en C++ y está disponible gratuitamente. Los ejemplos estudiados muestran que la TIR puede ser finita o infinita en número. Para varios TM cuando son infinitos, se encontraron fórmulas recursivas para ellos y se espera que esto siempre sea posible. Estas fórmulas se encontraron examinando la TIR en cada ejemplo por separado y adivinándola correctamente y probándola por inducción. Para los ejemplos estudiados, se encontró una tabla que muestra qué TIR sigue a otros dependiendo del siguiente símbolo leído y brinda mucha información sobre el comportamiento de TM. Se prevé que de esta manera será posible analizar una MT universal para descubrir cómo funciona el ciclo de interpretación.