2025
Construcción modular de una MT
Lenguajes y Autómatas I
Introducción
Una máquina de Turing trabaja con una cinta infinita, pero en cada configuración solo interesa la parte usada: desde el símbolo más a la izquierda hasta el más a la derecha que no sean blancos. Si la cabeza apunta fuera de esa zona, se incluyen espacios en blanco adicionales. Además de la cinta, también debe representarse el estado de control y la posición de la cabeza, insertando el estado justo antes del símbolo señalado.
Notación de Configuración
Para evitar ambigüedad, los nombres de estados se diferencian de los símbolos de cinta. La configuración se representa como x₁x₂...xᵢ₋₁ q xᵢ xᵢ₊₁...xₙ, donde q es el estado, la cabeza apunta al símbolo xᵢ, y la cadena refleja la parte activa de la cinta. Con esta notación, los movimientos de la máquina de Turing se describen mediante la flecha →M.
Ejemplo
La siguiente máquina de Turing acepta el lenguaje {0n1n|n ≥ 1}. Inicialmente, sobre la cinta se escribe una secuencia finita de ceros y unos, precedida y seguida por un número finito de espacios en blanco. Alternativamente, la máquina de Turing cambiará primero un 0 por una x y luego un 1 por una y, hasta que se hayan cambiado todos los ceros y unos. La máquina de Turing repite los pasos que se describen a continuación más detalladamente, y comenzando por el extremo izquierdo de la entrada.
Cambia un 0 por una x y se mueve hacia la derecha, pasando por encima de todos los ceros e y que encuentre, hasta llegar a un 1. Cambia el 1 por una y y se mueve hacia la izquierda, pasando por encima de todas las y y de todos los ceros que vaya encontrando, hasta llegar a una x.
Entonces, busca el primer 0 que se encuentre inmediatamente a su derecha y, si lo encuentra, lo sustituye por una x y repite el proceso igual que antes, cambiando un 1 por una y.Ejemplo: La cadena 0011 se acepta porque la máquina logra transformarla en XXYY, confirmando que el número de ceros y unos es igual.
Si la entrada no es de la forma 0∗1∗, la máquina de Turing no conseguirá finalmente realizar ningún movimiento, y dejará de operar sin aceptar. Sin embargo, si termina cambiando todos los ceros por x en la misma pasada en la que cambia el ultimo 1 por una y, entonces determina que la cadena de entrada era de la forma 0n1n y acepta. La máquina de Turing que realiza la serie de movimientos es la siguiente:
M = ({q0,q1q2,q3,q4},{0,1},{0,1,X,Y,B},δ,q0,B,{q4})
Donde δ (delta) está representada mediante la siguiente tabla:
Mientras M realiza los pasos anteriores, la porción de la cinta que ya ha sido recorrida por la cabeza de la cinta corresponderá siempre a una secuencia de símbolos descrita mediante la expresión regular X∗0∗Y ∗1∗. Es decir, habrá algunos ceros que ya han sido sustituidos por X, seguidos de algunos ceros que todavía no han sido sustituidos. Luego, se encontraran algunos unos ya reemplazados por Y, seguidos de unos que aun no han sido reemplazados.
A continuación, puede que haya algunos ceros o unos. El estado q0 es el estado inicial, y M entra de nuevo en q0 cada vez que vuelve a señalar al 0 que quede más a la izquierda. Si M se encuentra en el estado q0 y la cabeza señala a un 0, la regla del extremo superior izquierdo de la figura anterior indica que M debe pasar por el estado q1, reemplazar el 0 por una X, y moverse hacia la derecha. Una vez en el estado q1, M sigue moviéndose hacia la derecha, pasando por encima de todos los ceros y todas las Y que encuentre, mientras permanece en el estado q1. Si M encuentra una X o una B, deja de operar. Sin embargo, si M encuentra un 1 cuando está en el estado q1, sustituye dicho 1 por una Y , pasa al estado q2, y comienza a moverse hacia la izquierda.
En el estado q2, la máquina se mueve hacia la izquierda hasta encontrar la última X, luego vuelve a q0 y avanza.
- Si encuentra un 0, repite el ciclo de sustitución (0 → X y 1 → Y).
- Si encuentra una Y, significa que todos los ceros ya fueron cambiados:
- Si después solo hay Y y luego un blanco, la entrada es válida (0ⁿ1ⁿ) y pasa a q4 para aceptar.
- Si aparece un 1 extra, hay más unos que ceros y rechaza.
- Si aparece un 0, la cadena no es correcta y también rechaza.
A continuación emplearemos la máquina M anterior para comprobar si la cadena 0011 es aceptada por la máquina de Turing. Comenzamos con M en el estado q0, y señalando al primer 0, con lo cual la configuración inicial es q00011, presntamos a continuación la secuencia completa de movimientos de M es:
Ejemplo 2
Aqui se presenta otro ejemplo, en el que se examina qué hace M con la entrada 0010, la cual es una cadena que no pertence al lenguaje aceptado por la máquina El comportamiento de M con 0010 recuerda su comportamiento con 0011, hasta que alcanza la configuración XXY 0q1B. Sin embargo, en el estado q1, M no puede realizar ningún movimiento si el símbolo de la entrada al que señala es B. Por tanto, M deja de operar sin aceptar esta entrada.
Ejemplo 3
Diseñar una Máquina de Turing que calcule el complemento a 1 de un número binario. (Es decir, que sustituya los 0’s por 1’s y los 1’s por 0’s).
Solución:
- Algoritmo: Recorrer la cinta de izquierda a derecha, sustituyendo 1’s por 0’s y viceversa.
- Definición de la MT
- Necesitamos implementar una Máquina de Turing que se comporte como transductor, porque genera una salida en la cinta.
- Tendremos un solo estado, que será el inicial, q0, sobre el que se realizan todas las transiciones
Lenguajes aceptados por la MT
Aceptación de cadenas en Máquinas de Turing
La aceptación de una cadena en una máquina de Turing ocurre cuando, tras colocar la entrada en la cinta y comenzar desde el símbolo más a la izquierda, el proceso llega a un estado de aceptación. En ese caso, se dice que la cadena fue reconocida; si no se alcanza dicho estado, la cadena no es aceptada. Formalmente, el lenguaje aceptado por una máquina de Turing M se define como el conjunto de cadenas de Σ∗ que permiten llegar a un estado final. Estos lenguajes reciben el nombre de lenguajes recursivamente enumerables (RE).
Aceptación por parada y lenguajes recursivos
Además del método anterior, existe la aceptación por parada, que ocurre cuando la máquina no puede continuar porque su función de transición no está definida. Se suele suponer que una máquina de Turing siempre se detiene en los estados de aceptación, aunque no siempre es así. Los lenguajes reconocidos por máquinas que siempre se paran, acepten o no, se denominan lenguajes recursivos. Estas máquinas representan un buen modelo de algoritmo, ya que si siempre se detienen, reflejan la noción de problema decidible dentro de la teoría de la decidibilidad.
¡GRACIAS!
2025
Copia - 6.2 Construcción modular de una mt
TECNOLOGICO NACIONAL DE MÉXICO
Created on September 10, 2025
Start designing with a free template
Discover more than 1500 professional designs like these:
View
SWOT Challenge: Classify Key Factors
View
Vision Board
View
Explainer Video: Keys to Effective Communication
View
Explainer Video: AI for Companies
View
Corporate CV
View
Flow Presentation
View
Discover Your AI Assistant
Explore all templates
Transcript
2025
Construcción modular de una MT
Lenguajes y Autómatas I
Introducción
Una máquina de Turing trabaja con una cinta infinita, pero en cada configuración solo interesa la parte usada: desde el símbolo más a la izquierda hasta el más a la derecha que no sean blancos. Si la cabeza apunta fuera de esa zona, se incluyen espacios en blanco adicionales. Además de la cinta, también debe representarse el estado de control y la posición de la cabeza, insertando el estado justo antes del símbolo señalado.
Notación de Configuración
Para evitar ambigüedad, los nombres de estados se diferencian de los símbolos de cinta. La configuración se representa como x₁x₂...xᵢ₋₁ q xᵢ xᵢ₊₁...xₙ, donde q es el estado, la cabeza apunta al símbolo xᵢ, y la cadena refleja la parte activa de la cinta. Con esta notación, los movimientos de la máquina de Turing se describen mediante la flecha →M.
Ejemplo
La siguiente máquina de Turing acepta el lenguaje {0n1n|n ≥ 1}. Inicialmente, sobre la cinta se escribe una secuencia finita de ceros y unos, precedida y seguida por un número finito de espacios en blanco. Alternativamente, la máquina de Turing cambiará primero un 0 por una x y luego un 1 por una y, hasta que se hayan cambiado todos los ceros y unos. La máquina de Turing repite los pasos que se describen a continuación más detalladamente, y comenzando por el extremo izquierdo de la entrada.
Cambia un 0 por una x y se mueve hacia la derecha, pasando por encima de todos los ceros e y que encuentre, hasta llegar a un 1. Cambia el 1 por una y y se mueve hacia la izquierda, pasando por encima de todas las y y de todos los ceros que vaya encontrando, hasta llegar a una x. Entonces, busca el primer 0 que se encuentre inmediatamente a su derecha y, si lo encuentra, lo sustituye por una x y repite el proceso igual que antes, cambiando un 1 por una y.Ejemplo: La cadena 0011 se acepta porque la máquina logra transformarla en XXYY, confirmando que el número de ceros y unos es igual.
Si la entrada no es de la forma 0∗1∗, la máquina de Turing no conseguirá finalmente realizar ningún movimiento, y dejará de operar sin aceptar. Sin embargo, si termina cambiando todos los ceros por x en la misma pasada en la que cambia el ultimo 1 por una y, entonces determina que la cadena de entrada era de la forma 0n1n y acepta. La máquina de Turing que realiza la serie de movimientos es la siguiente: M = ({q0,q1q2,q3,q4},{0,1},{0,1,X,Y,B},δ,q0,B,{q4})
Donde δ (delta) está representada mediante la siguiente tabla:
Mientras M realiza los pasos anteriores, la porción de la cinta que ya ha sido recorrida por la cabeza de la cinta corresponderá siempre a una secuencia de símbolos descrita mediante la expresión regular X∗0∗Y ∗1∗. Es decir, habrá algunos ceros que ya han sido sustituidos por X, seguidos de algunos ceros que todavía no han sido sustituidos. Luego, se encontraran algunos unos ya reemplazados por Y, seguidos de unos que aun no han sido reemplazados.
A continuación, puede que haya algunos ceros o unos. El estado q0 es el estado inicial, y M entra de nuevo en q0 cada vez que vuelve a señalar al 0 que quede más a la izquierda. Si M se encuentra en el estado q0 y la cabeza señala a un 0, la regla del extremo superior izquierdo de la figura anterior indica que M debe pasar por el estado q1, reemplazar el 0 por una X, y moverse hacia la derecha. Una vez en el estado q1, M sigue moviéndose hacia la derecha, pasando por encima de todos los ceros y todas las Y que encuentre, mientras permanece en el estado q1. Si M encuentra una X o una B, deja de operar. Sin embargo, si M encuentra un 1 cuando está en el estado q1, sustituye dicho 1 por una Y , pasa al estado q2, y comienza a moverse hacia la izquierda.
En el estado q2, la máquina se mueve hacia la izquierda hasta encontrar la última X, luego vuelve a q0 y avanza.
A continuación emplearemos la máquina M anterior para comprobar si la cadena 0011 es aceptada por la máquina de Turing. Comenzamos con M en el estado q0, y señalando al primer 0, con lo cual la configuración inicial es q00011, presntamos a continuación la secuencia completa de movimientos de M es:
Ejemplo 2
Aqui se presenta otro ejemplo, en el que se examina qué hace M con la entrada 0010, la cual es una cadena que no pertence al lenguaje aceptado por la máquina El comportamiento de M con 0010 recuerda su comportamiento con 0011, hasta que alcanza la configuración XXY 0q1B. Sin embargo, en el estado q1, M no puede realizar ningún movimiento si el símbolo de la entrada al que señala es B. Por tanto, M deja de operar sin aceptar esta entrada.
Ejemplo 3
Diseñar una Máquina de Turing que calcule el complemento a 1 de un número binario. (Es decir, que sustituya los 0’s por 1’s y los 1’s por 0’s). Solución:
Lenguajes aceptados por la MT
Aceptación de cadenas en Máquinas de Turing
La aceptación de una cadena en una máquina de Turing ocurre cuando, tras colocar la entrada en la cinta y comenzar desde el símbolo más a la izquierda, el proceso llega a un estado de aceptación. En ese caso, se dice que la cadena fue reconocida; si no se alcanza dicho estado, la cadena no es aceptada. Formalmente, el lenguaje aceptado por una máquina de Turing M se define como el conjunto de cadenas de Σ∗ que permiten llegar a un estado final. Estos lenguajes reciben el nombre de lenguajes recursivamente enumerables (RE).
Aceptación por parada y lenguajes recursivos
Además del método anterior, existe la aceptación por parada, que ocurre cuando la máquina no puede continuar porque su función de transición no está definida. Se suele suponer que una máquina de Turing siempre se detiene en los estados de aceptación, aunque no siempre es así. Los lenguajes reconocidos por máquinas que siempre se paran, acepten o no, se denominan lenguajes recursivos. Estas máquinas representan un buen modelo de algoritmo, ya que si siempre se detienen, reflejan la noción de problema decidible dentro de la teoría de la decidibilidad.
¡GRACIAS!
2025