6.1 Definición formal MT

Una máquina de Turing (MT) es un modelo computacional abstracto que formaliza la idea intuitiva de algoritmo. Fue introducida por Alan Turing en 1936, y es uno de los modelos más importantes en la teoría de la computación.

Una MT está constituida por los siguientes elementos:

• Conjunto de estados: Es un conjunto finito de estados posibles en los que puede encontrarse la máquina.
• Alfabeto de entrada: Es un conjunto finito de símbolos que pueden aparecer en la cinta de entrada.
• Alfabeto de salida: Es un conjunto finito de símbolos que pueden aparecer en la cinta de salida.
• Símbolo blanco: Es un símbolo especial que se utiliza para representar el espacio vacío en la cinta.
• Cinta: Es una banda de papel o material similar, dividida en celdas, sobre la que la máquina puede leer y escribir.
• Función de transición: Es una función que determina el siguiente estado de la máquina, el símbolo que debe escribir en la cinta y el movimiento de la cabeza de lectura/escritura, según el estado actual de la máquina, el símbolo leído en la cinta y el símbolo que se encuentra en la cinta debajo de la cabeza de lectura/escritura.

El funcionamiento de una MT se puede describir de la siguiente manera:

• La máquina comienza en un estado inicial.
• La máquina lee un símbolo de la cinta.
• La máquina consulta su función de transición para determinar el siguiente estado, el símbolo que debe escribir en la cinta y el movimiento de la cabeza de lectura/escritura.
• La máquina escribe el símbolo correspondiente en la cinta.
• La máquina mueve la cabeza de lectura/escritura según lo indicado.
• La máquina repite los pasos 2 a 5 hasta que se encuentre en un estado de parada.

6.2 Construcción modular de una MT

Una MT se puede construir de manera modular, es decir, a partir de MTs más simples. Para ello, se pueden utilizar los siguientes métodos:

• Secuenciación: Se conectan varias MTs en serie, de modo que la salida de una MT se convierte en la entrada de la siguiente.
• Paralelismo: Se ejecutan varias MTs al mismo tiempo, de modo que cada MT puede procesar una parte de la entrada.
• Recursión: Se utiliza una MT para construir una MT más compleja.

6.3 Lenguajes aceptados por la MT

Un lenguaje es aceptado por una MT si, para cada cadena de entrada del lenguaje, la MT se detiene en un estado de parada con la cinta vacía.

Los lenguajes aceptados por las MTs se denominan lenguajes recursivos enumerables. Estos lenguajes incluyen todos los lenguajes que pueden ser descritos por un algoritmo.

Ejemplos de lenguajes aceptados por MTs

• El lenguaje de las cadenas binarias que terminan en 01.
• El lenguaje de las cadenas de enteros positivos.
• El lenguaje de las cadenas de caracteres que son palíndromos.

Conclusiones

Las MTs son modelos computacionales poderosos que pueden utilizarse para representar una amplia gama de algoritmos. Su importancia radica en que proporcionan una base formal para el estudio de la computación.