Page 103 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

103

Esta máquina recibe el nombre de universal (MTU) por ser capaz de simular el comportamiento
de cualquier otra máquina de Turing y fue propuesta por el propio Alan Turing en 1936. Es así
que la meta funciona como una plataforma para interpretar y ejecutar las MT que sean descritas
en su cinta. O sea, una MT interpreta y estudia el comportamiento de otra MT.

Para implementar una MTU, es necesario definir la forma en que la MT es codificada sobre la
cinta. Deben por ejemplo definirse la cantidad de estados, los elementos de la función de
transición y la cadena que debe ser procesada o aceptada. Para que la MTU funcione se usan
separadores que permiten identificar los diversos campos sobre la cinta. El concepto de las
MTU es muy potente pero muy laborioso.