Tecnm Campus Acapulco

Carrera: Ingeniería en Sistemas

Computacionales.

Materia: Lenguajes y Autómatas I

Tema: 6 Máquinas de Turing.

Equipo 3:
Alumno Control
José Ignacio Diaz Rodriguez 20320996
Brandon Isrrael Oyorsabal Rabiela 20321153
Juan Carlos Suastegui Gomez 20321233
Fernando Isrrael Torres Carmona 20321239

Hora: 01:00-02:00pm.

24 de mayo del 2023.

Índice
Introducción ........................................................................................................................................ 3

6.1 definición formal de Turing ........................................................................................................... 5

¿QUE SON Y COMO FUNCIONAN? .................................................................................................. 7

6.2 construcción modular de una máquina de Turing ...................................................................... 10

Objetivo de creación modular de una máquina de Turing ........................................................... 10

Pasos para la construcción de una máquina de Turing ................................................................. 10

ejemplo de cómo se puede crear una máquina de Turing de manera modular en C#: ............... 13

6.3 lenguajes aceptados por la MT ................................................................................................... 16

Lenguajes regulares....................................................................................................................... 16

Lenguajes libres de contexto......................................................................................................... 17

Lenguajes sensibles al contexto .................................................................................................... 18

Lenguajes recursivamente enumerables ...................................................................................... 20

Actividad a) Identificar la anotación formal de una MT.................................................................... 21

Actividad b) construir una MT a partir de un caso de estudio .......................................................... 22

Conclusiones ..................................................................................................................................... 24

Bibliografía ........................................................................................................................................ 25
 3

Introducción

Para introducir al tema a continuación se tienen que descubrir los inicios de la

máquina de Turing

Alan Turing fue un polifacético hombre de ciencias nacido en Londres en 1912. Fue

matemático lógico, criptógrafo, filósofo y científico de la computación, haciendo importantes

y brillantes aportaciones al mundo de la computación que le convirtieron en pionero de la

informática moderna.

En 1936 crea la máquina de Turing, capaz de resolver

cualquier problema matemático que pudiera representarse mediante

un algoritmo. En 1938 se inventó el término hipercomputación para,

a través de las máquinas Oracle, resolver también

problemas para los que no existía representación

algorítmica.

Su aportación a la II Guerra Mundial

Esta máquina, parecida a una máquina de escribir convencional

de la época y de nombre Enigma, estaba compuesta de varios rotores

(con 26 posicione s cada uno en base a las 26 letras del alfabeto) que iban girando a medida

que se introducía el mensaje de entrada. Estos giros hacían que a cada letra de entrada

del mensaje original le correspondiera una letra de salida de manera que, al ir rotando a

cada pulsación, la misma letra de entrada no tenía siempre la misma letra de salida. Es

decir, posibilitaban un código variable.

Tras la guerra, su trabajo continuó en el marco de la computación. Diseñó uno de

los primeros computadores electrónicos programables digitales, así como otra de las
 4

primeras máquinas en la Universidad de Mánchester. También destacó en el campo de la

inteligencia artificial, principalmente por la concepción del test de Turing en 1950, según el

cual puede juzgarse la inteligencia de una máquina si sus respuestas en la prueba son

indistinguibles de las de un ser humano.

Su pareja, otro hombre, ayudo a un ladrón a entrar en la casa de Turing. En la

investigación Turing reconoció ser homosexual, lo cual era delito en esa época en Reino

Unido. Se le dio a escoger entre la cárcel y la castración química. Eligió lo segundo,

provocándole importantes alteraciones físicas. Alan Turing se suicidó por consumo de

cianuro en 1954, dos años después de ser condenado.

 5

6.1 definición formal de Turing

Puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de

algoritmo.

(MT) Es un modelo computacional que realiza una lectura/escritura de manera

automática sobre una entrada llamada cinta, generando una salida en esta misma. Este

modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial

llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de

transiciones entre dichos estados.

Su funcionamiento se basa en una función de transición, que recibe un estado inicial

y una cadena de caracteres (la cinta, la cual es finita por la izquierda) pertenecientes al

alfabeto de entrada. Luego va leyendo una celda de la cinta, borrando el símbolo, escribir

el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a

la derecha (solo una celda a la vez), repitiendo esto según se indique en la función de

transición, para finalmente detenerse en un estado final o de aceptación, representando así

la salida.

Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla ;

M = (𝑄, Σ, Γ, 𝑠, 𝑏, 𝐹, 𝛿) donde:

Q es un conjunto finito de estados.

 6

Σ es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto

de máquina o, de entrada.

Γ es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta. Σ ⊆ Γ

𝑠 ∈𝑄 es el estado inicial.

𝑏 ∈Γ es un símbolo denominado blanco, y es el único símbolo que se puede repetir un

número infinito de veces.

𝐹 ⊆ 𝑄 es el conjunto de estados finales de aceptación.

𝛿 ∶ 𝑄 𝑥 Γ ⟶ P(𝑄 𝑥 Γ 𝑥 {𝐿, 𝑅} )

Es una función parcial denominada función de transición, donde L s un movimiento

a la izquierda y R es el movimiento a la derecha.
La máquina de Turing puede considerarse como un autómata capaz de reconocer
lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente
enumerables, de acuerdo a la jerarquía de Chomsky.

Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata

finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.

Las máquinas de Turing se pueden representar mediante grafos particulares, también

llamados diagramas de estados finitos, de la siguiente manera:

Esta Máquina de Turing está definido sobre el alfabeto Σ={a,b,c}, posee el conjunto

de estados
 7

Q={qo,q1,q2,q3,q4,q5,q6}, con las transiciones que se pueden ver. Su estado inicial

es q1 y el estado final es q0, el lenguaje de salida δ={X,Y,Z,B} siendo B el símbolo

denominado Blanco.

Esta Máquina reconoce la expresión regular de la forma {a^n b^n c^n,n>=0} .

*Los estados se representan como vértices, etiquetados con su nombre en el

interior.

*Una transición desde un estado a otro, se representa mediante una arista dirigida

que une a estos vértices, y esta rotulada por símbolo que lee el cabezal/símbolo que

escribirá el cabezal, movimiento del cabezal.

*El estado inicial se caracteriza por tener una arista que llega a él, proveniente de

ningún otro vértice.

*El o los estados finales se representan mediante vértices que están encerrados a

su vez por otra circunferencia.

¿QUE SON Y COMO FUNCIONAN?

Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en

casillas. Sobre esta cinta hay un dispositivo capaz de desplazarse a lo largo de ella a razón

de una casilla cada vez. Este dispositivo cuenta con un cabezal capaz de leer un símbolo
 8

escrito en la cinta, o de borrar el existente e imprimir uno nuevo en su lugar. Por último,

contiene además un registro capaz de almacenar un estado cualquiera, el cual viene

definido por un símbolo.

Los símbolos que definen el estado del dispositivo no tienen por qué coincidir con

los símbolos que se pueden leer o escribir en la cinta. En los programas presentados en el

artículo, los posibles símbolos a leer o escribir en la cinta son el 0 y el 1, y los posibles

estados se representan con letras mayúsculas. En el emulador, existe un cambio en la

representación del estado, usando para ello los números del 0 al 99, para permitir un mayor

número de ellos. La máquina tiene un funcionamiento totalmente mecánico y secuencial.

Lo que hace es leer el símbolo que hay en la casilla que tiene debajo. Después toma el

símbolo del estado en que se encuentra. Con estos dos datos accede a una tabla, en la

cual lee el símbolo que debe escribir en la cinta, el nuevo estado al que debe pasar y si

debe desplazarse a la casilla izquierda o derecha.

Ejemplo Definimos una máquina de Turing sobre el alfabeto {0,1}, donde 0

representa el símbolo blanco. La máquina comenzará su proceso situado sobre un símbolo

“1″ de una serie.

La máquina de Turing copiará el número de símbolos “1″ que encuentre hasta el

primer blanco detrás de dicho símbolo blanco. Es decir, situada sobre el 1 situado en el

extremo izquierdo, doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la

entrada “111″ devolverá “1110111″, con “1111″ devolverá “111101111″, y sucesivamente.

El conjunto de estados es {s1, s2, s3, s4, s5} y el estado inicial es s1.
 9

La tabla que describe la función de transición es la siguiente:

El funcionamiento de una computación de esta máquina se puede mostrar con el

siguiente ejemplo (en negrita se resalta la posición de la cabeza lectora/escritora):

Vemos que esta máquina no hace gran cosa. Sin embargo, una máquina de Turing

puede hacer cosas útiles, tales como suma r dos números, multiplicarlos, copiarlos, etc.

Disponiendo de una máquina con el suficiente número de estados, podríamos hacer con

ella cualquier operación que un ordenador normal pudiese realizar.

 10

Las máquinas de Turing plantean una deducción bastante curiosa: dado que en

ellas se puede realizar cualquier trabajo computable, es posible programarlas para que

simulen el comportamiento de un potente ordenador. Y como una máquina de Turing

puede ser codificada en cualquier ordenador, por pequeño que sea, sería posible (si

disponemos de memoria suficiente, claro) emular en nuestro ordenador de casa una

máquina de Turing que simule un superordenador. Esto significa que todos los

ordenadores pueden realizar exactamente el mismo tipo de tareas, y que los cálculos que

pueda realizar el más grande los puede llevar a cabo también el más pequeño. La única

diferencia sería, obviamente, la velocidad.

6.2 construcción modular de una máquina de Turing

Objetivo de creación modular de una máquina de Turing

Mediante esta técnica se puedan desarrollarse máquinas de Turing complejas a

partir de bloques de elementales a partir de máquinas más pequeñas mediaste diagramas

de transiciones.

La construcción de máquinas de Turing se lleva a cabo mediante los diagramas de

transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión

y concatenación de los autómatas finitos.

Pasos para la construcción de una máquina de Turing

1.-Elimine las características de inicio de los estados iniciales de las maquinas,

excepto la de aquel donde iniciara la maquina compuesta.

 11

2.-Elimine las características de detención de los estados de parada de todas la

maquinas e introduzca un nuevo estado de parada que no se encuentre en ninguno de los

diagramas que se encuentren.

3.-Para cada uno de los antiguos estados de parada p y cada x en y.

Ejemplificación de dicha construcción.

Los diagramas compuestos para la construcción modular de una máquina de Turing

Son aquellos en los que cada uno de los bloques de construcción se representa

como un nodo, con flechas entre dichos nodos para indicar las transiciones entre bloques.

Se puede combinar dos máquinas de Turing permitiendo que compartan la misma

cinta y, que cuando una termine su ejecución, el otro empiece. El contenido de la cinta

cuando comienza la ejecución de la segunda máquina de Turing, está formado por todo lo

que dejó la primera máquina de Turing, y la cabeza del /e de la segunda se situará, al

comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primera.

 12

Un sistema Turing completo es aquel que puede simular el comportamiento de

una máquina de Turing. Es evidente que, salvando los problemas de memoria, los

ordenadores modernos y los lenguajes de programación de uso general, son sistemas de

Turing completos. También es evidente, que, con independencia de su forma concreta,

cualquier dispositivo que se comporte como un sistema de Turing completo, puede en

principio ejecutar cualquier cálculo que realice cualquier computador.

Nota: Observe que la anterior afirmación no menciona para nada la posible dificultad

de escribir el programa o del tiempo que pueda emplear en realizar el cálculo (cualquier

cálculo que pueda hacer un ordenador puede teóricamente efectuarse con papel y lápiz).

Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal

de datos. En cada instante la máquina puede leer un solo dato de la secuencia

(generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en

cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la
 13

posibilidad de escribir nuevos datos en la secuencia; recorrer la secuencia en ambos

sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.

Maquina s de Turing Compuesta.

La creación modular de una máquina de Turing implica dividir la implementación en

componentes individuales que se combinan para construir la máquina completa.

ejemplo de cómo se puede crear una máquina de Turing de manera

modular en C#:

Definir una clase Tape (cinta) que represente la cinta de la máquina de Turing. Esta clase

puede contener un arreglo de símbolos y un puntero que indica la posición actual en la cinta.

Además, debe proporcionar métodos para mover el puntero a la izquierda o a la derecha, leer el

símbolo actual y escribir un nuevo símbolo.

class Tape
{
private char[] symbols;
private int position;

public Tape(string input)

 14

{
symbols = input.ToCharArray();
position = 0;
}

public char ReadSymbol()

{
return symbols[position];
}

public void WriteSymbol(char symbol)

{
symbols[position] = symbol;
}

public void MoveLeft()

{
position--;
}

public void MoveRight()

{
position++;
}
}
Definir una clase Transition (transición) que represente una transición de estado en

la máquina de Turing. Esta clase puede contener el estado actual, el símbolo actual, el

estado siguiente, el símbolo siguiente y la dirección en la que se debe mover el puntero.

class Transition
{
public string CurrentState { get; set; }
public char CurrentSymbol { get; set; }
public string NextState { get; set; }
public char NextSymbol { get; set; }
public int MoveDirection { get; set; } // -1 para mover a la
izquierda, 1 para mover a la derecha
}
 15

Definir una clase TuringMachine (máquina de Turing) que represente la máquina

completa. Esta clase puede contener una lista de transiciones, un diccionario de estados

finales y un método Run() para ejecutar la máquina de Turing.

class TuringMachine
{
private List<Transition> transitions;
private HashSet<string> finalStates;

public TuringMachine(List<Transition> transitions, HashSet<string>

finalStates)
{
this.transitions = transitions;
this.finalStates = finalStates;
}

public void Run(string initialState, string input)

{
string currentState = initialState;
Tape tape = new Tape(input);

while (!finalStates.Contains(currentState))
{
char currentSymbol = tape.ReadSymbol();

Transition transition = transitions.FirstOrDefault(t =>

t.CurrentState == currentState && t.CurrentSymbol ==
currentSymbol);

if (transition == null)
{
Console.WriteLine("No se encontró una transición válida
para el estado y símbolo actual.");
return;
}

tape.WriteSymbol(transition.NextSymbol);

if (transition.MoveDirection == -1)
tape.MoveLeft();
else if (transition.MoveDirection == 1)
tape.MoveRight();

currentState = transition.NextState;
 16

Console.WriteLine("La máquina de Turing ha alcanzado un estado

final.");
}
}

6.3 lenguajes aceptados por la MT

Las máquinas de Turing, así como los AF y los AP se utilizan para aceptar cadenas

de un lenguaje definidas sobre un alfabeto A. El modelo básico de máquina de Turing, tiene

un mecanismo de control, una cinta de entrada que se divide en celdas, y una cabeza de

lectura/escritura que lee un solo símbolo de la cinta por vez. La cinta tiene una celda de

inicio de más a la izquierda, pero es infinita a derecha. Cada celda de la cinta puede

contener exactamente un símbolo del alfabeto de la cinta C. Inicialmente, las n celdas de

más a la izquierda (n ≥ 0) contienen una cadena ω, siendo |ω|=n. ω está definida sobre un

subconjunto de C, llamado alfabeto de entrada A. Las infinitas celdas restantes contienen

un símbolo blanco B, el cual es un símbolo especial del alfabeto C. La diferencia

fundamental con el autómata de pila y el autómata finito, es que se puede leer un símbolo

y reescribirlo por otro símbolo, y además la cabeza de lectura/escritura puede desplazarse

a la izquierda, a la derecha o quedarse en el mismo lugar. El modelo general de MT permite

aceptar los lenguajes recursivos enumerables o estructurados por frases que incluyen todo

el conjunto de lenguajes que describen procedimientos computacionales. Todo

procedimiento computacional puede ser modelado con una Máquina de Turing.

Lenguajes regulares

Una máquina de Turing puede aceptar lenguajes regulares, que son aquellos que

pueden ser descritos por una expresión regular. Estos lenguajes incluyen patrones simples

como cadenas de caracteres con una estructura regular.

 17

En términos de la máquina de Turing, un lenguaje regular es un lenguaje que puede

ser reconocido y aceptado por una máquina de Turing determinista (MTD) o una máquina

de Turing no determinista (MTND) específica.

Una MTD es una máquina de Turing que opera de manera determinista, lo que

significa que, para cada estado y símbolo de entrada, existe exactamente una transición

definida. Una MTND, por otro lado, puede tener múltiples transiciones posibles para un

estado y símbolo de entrada dado.

La definición de un lenguaje regular en términos de una máquina de Turing se basa

en la capacidad de la máquina para reconocer patrones simples y regularidades en las

cadenas de entrada. Un lenguaje regular puede ser descrito por una expresión regular, que

es una secuencia de símbolos que define un patrón de búsqueda en un texto.

La máquina de Turing puede tener un conjunto de estados, una cinta de entrada,

una cabeza de lectura/escritura, y transiciones que especifican cómo cambiar de estado y

mover la cabeza de acuerdo con el símbolo leído. En el caso de los lenguajes regulares,

las transiciones de la máquina de Turing serían relativamente simples y predecibles, ya que

se enfocarían en reconocer y repetir patrones específicos en las cadenas de entrada.

Lenguajes libres de contexto

Las máquinas de Turing también pueden aceptar lenguajes libres de contexto, que

son más poderosos que los lenguajes regulares. Estos lenguajes incluyen estructuras más

complejas, como los lenguajes de programación.

los lenguajes libres de contexto son un tipo de lenguaje formal que se puede

describir mediante una gramática libre de contexto. Estos lenguajes son más expresivos y

poderosos que los lenguajes regulares.

 18

Una gramática libre de contexto consta de un conjunto de reglas de producción que

definen cómo se pueden construir las cadenas dentro del lenguaje. Cada regla de

producción consiste en un símbolo no terminal (representado por una variable) y una

secuencia de símbolos que pueden ser terminales (símbolos que forman parte del lenguaje)

o no terminales (símbolos que pueden ser reemplazados por una secuencia de símbolos).

En un lenguaje libre de contexto, las reglas de producción son aplicadas de manera

independiente del contexto en el que aparecen los símbolos. Esto significa que la elección

de las reglas de producción a aplicar no depende del contexto en el que se encuentre el

símbolo dentro de la cadena.

Un ejemplo común de lenguaje libre de contexto es el lenguaje de programación C,

en el cual la estructura de los programas está definida por una gramática libre de contexto.

Los lenguajes libres de contexto son utilizados en la descripción de muchos lenguajes de

programación, compiladores, analizadores sintácticos y procesadores de lenguaje natural.

Algunos ejemplos de lenguajes libres de contexto son el lenguaje de balanceo de

paréntesis, el lenguaje de expresiones aritméticas y el lenguaje de expresiones regulares

extendidas.

Lenguajes sensibles al contexto

Las máquinas de Turing más avanzadas pueden aceptar lenguajes sensibles al

contexto. Estos lenguajes son aún más poderosos y pueden representar estructuras y

gramáticas más complejas que los lenguajes libres de contexto.

Los lenguajes sensibles al contexto son un tipo de lenguaje formal que se encuentra

en un nivel de complejidad mayor que los lenguajes libres de contexto. Estos lenguajes son

descritos mediante gramáticas sensibles al contexto, también conocidas como gramáticas

tipo 1, que son más generales que las gramáticas libres de contexto.
 19

En una gramática sensible al contexto, las reglas de producción tienen la capacidad

de modificar el contexto o contexto de las cadenas a medida que se aplican. Esto significa

que las reglas de producción pueden tomar en cuenta información adicional, más allá de la

estructura local de los símbolos en la cadena.

Las gramáticas sensibles al contexto tienen una forma generalizada para sus reglas

de producción. Una regla de producción típica en una gramática sensible al contexto se

representa de la siguiente manera:

αAβ→αγβ

Donde:

α y β representan secuencias de símbolos que pueden ser terminales o no

terminales.

A es un símbolo no terminal.

γ es una secuencia de símbolos que pueden ser terminales o no terminales.

En un lenguaje sensible al contexto, las reglas de producción se aplican teniendo en

cuenta el contexto o contexto de los símbolos involucrados. Esto significa que el lado

izquierdo y derecho de una regla de producción pueden contener diferentes secuencias de

símbolos, y la elección de la regla a aplicar depende del contexto en el que se encuentren

los símbolos dentro de la cadena.

Un ejemplo común de lenguaje sensible al contexto es el lenguaje de programación

Python, en el cual la sintaxis y la estructura del código están definidas por una gramática

sensible al contexto.
 20

Lenguajes recursivamente enumerables

Las máquinas de Turing universales pueden aceptar lenguajes recursivamente enumerables.

Estos lenguajes son los más generales y pueden representar cualquier lenguaje decidible, es decir,

aquellos lenguajes para los que existe un algoritmo que puede determinar si una cadena pertenece

al lenguaje o no.

Los lenguajes recursivamente enumerables, también conocidos como lenguajes

recursivamente enumerables o lenguajes semidecidibles, son un tipo de lenguaje formal que

pertenece a la clase más alta de complejidad en la jerarquía de Chomsky, llamada lenguajes

recursivamente enumerables.

Un lenguaje recursivamente enumerable es un lenguaje que puede ser generado o

reconocido por una máquina de Turing en su modo de "enumeración" o "generación". Esto significa

que una máquina de Turing puede producir todas las cadenas que pertenecen al lenguaje, pero no

necesariamente puede determinar si una cadena dada no pertenece al lenguaje.

Formalmente, un lenguaje L es recursivamente enumerable si existe una máquina de Turing

que, al ejecutarse, eventualmente enumerará todas las cadenas que pertenecen a L. Si una cadena

no pertenece a L, la máquina de Turing puede continuar ejecutándose indefinidamente sin generarla

o reconocerla.

Esta característica distingue a los lenguajes recursivamente enumerables de los lenguajes

recursivos, donde una máquina de Turing puede determinar en tiempo finito si una cadena

pertenece o no al lenguaje.
 21

Un ejemplo clásico de lenguaje recursivamente enumerable es el lenguaje de aceptación de

una máquina de Turing universal. Este lenguaje contiene todas las descripciones de máquinas de

Turing y sus respectivas entradas para las cuales la máquina de Turing universal aceptará.

Actividad a) Identificar la anotación formal de una MT

La anotación formal de una Máquina de Turing (MT) se puede realizar utilizando

una notación específica que describe sus componentes y transiciones. A continuación, se

muestra una representación formal comúnmente utilizada para describir una MT:

Una MT se denota por una tupla de la forma:

MT = (Q, Σ, Γ, δ, q0, qaccept, qreject)

Donde:

Q es un conjunto finito de estados.

Σ es el alfabeto de entrada.

Γ es el alfabeto de la cinta (que incluye el símbolo blanco y los símbolos de la

entrada).

δ es la función de transición.

q0 es el estado inicial.

qaccept es el estado de aceptación.

qreject es el estado de rechazo.

 22

La función de transición δ especifica cómo la máquina de Turing se mueve entre

estados y cómo modifica el contenido de la cinta. Puede estar definida de diferentes

maneras según el tipo de máquina de Turing (determinista o no determinista).

En el caso de una máquina de Turing determinista (MTD), la función de transición

se define de la siguiente manera:

δ: Q × Γ → Q × Γ × {L, R}

Donde δ(q, a) = (p, b, D) indica que si la máquina de Turing se encuentra en el

estado q y lee el símbolo a en la cinta, entonces se transita al estado p, se escribe el

símbolo b en la cinta y se mueve hacia la dirección D (izquierda o derecha).

En el caso de una máquina de Turing no determinista (MTND), la función de

transición se define de manera similar, pero permite múltiples transiciones para un estado

y símbolo de entrada determinados.

Actividad b) construir una MT a partir de un caso de

estudio

Para construir una Máquina de Turing (MT) basada en el caso de estudio de

lenguajes y gramáticas, podemos considerar un ejemplo específico, como el

reconocimiento de un lenguaje dado. A continuación, proporcionaré un ejemplo de cómo

construir una MT para verificar si una cadena pertenece a un lenguaje regular específico.

Supongamos que queremos construir una MT para verificar si una cadena de

entrada está compuesta solo por símbolos '0' y '1' y tiene una longitud par. En otras

palabras, queremos reconocer el lenguaje regular L = {'0', '1’} * con una longitud par.
 23

Diseño básico de la MT:

Estados:

q0: Estado inicial.

q1: Estado de aceptación.

qr: Estado de rechazo.

Alfabeto:

Σ: {'0', '1', blanco} (símbolos de entrada).

Γ: {'0', '1', blanco} (símbolos de la cinta).

Transiciones:

δ(q0, '0') = (q1, '0', R): Si la máquina de Turing lee '0' en el estado q0, transita al

estado q1, escribe '0' en la cinta y se mueve hacia la derecha.

δ(q0, '1') = (q1, '1', R): Si la máquina de Turing lee '1' en el estado q0, transita al

estado q1, escribe '1' en la cinta y se mueve hacia la derecha.

δ(q0, blanco) = (qr, blanco, S): Si la máquina de Turing lee el símbolo blanco

(espacio en blanco) en el estado q0, transita al estado de rechazo qr y se detiene

(movimiento estacionario).

δ(q1, '0') = (q0, '0', R): Si la máquina de Turing lee '0' en el estado q1, transita al

estado q0, escribe '0' en la cinta y se mueve hacia la derecha.

δ(q1, '1') = (q0, '1', R): Si la máquina de Turing lee '1' en el estado q1, transita al

estado q0, escribe '1' en la cinta y se mueve hacia la derecha.

 24

δ(q1, blanco) = (qr, blanco, S): Si la máquina de Turing lee el símbolo blanco en el

estado q1, transita al estado de rechazo qr y se detiene (movimiento estacionario).

Estado inicial y estados de aceptación/rechazo:

Estado inicial: q0.

Estado de aceptación: q1.

Estado de rechazo: qr.

Con esta descripción, hemos construido una MT que reconoce si una cadena de entrada
está compuesta solo por símbolos '0' y '1' y tiene una longitud par.

Conclusiones

La anotación formal de una MT incluye la especificación de sus componentes (estados,

alfabetos, función de transición) y su representación mediante una tupla. Esta notación proporciona

una descripción precisa y formal de una máquina de Turing.

la Máquina de Turing es un modelo teórico de computación que ha sido fundamental en el

estudio de la computabilidad y la complejidad de los problemas. Aunque no se construyen Máquinas

de Turing físicas, su concepto ha sido aplicado de diversas formas en la teoría de la computación y

en la práctica de la informática.

Algunas de las aplicaciones y contribuciones de la Máquina de Turing:

Análisis de algoritmos: La Máquina de Turing ha sido utilizada para analizar la complejidad

de los algoritmos y para demostrar resultados teóricos sobre qué problemas son computables y

cuáles no.
 25

Diseño y evaluación de lenguajes de programación: El modelo de la Máquina de Turing ha

servido como base teórica para el diseño y evaluación de lenguajes de programación, así como para

el estudio de la semántica de los mismos.

Teoría de la computabilidad: La Máquina de Turing es un modelo de computación que

captura la noción intuitiva de un algoritmo efectivo, lo que ha permitido establecer límites teóricos

sobre qué problemas pueden ser resueltos por una computadora.

Desarrollo de compiladores y lenguajes formales: Los principios de la Máquina de Turing se

aplican en el diseño y desarrollo de compiladores y analizadores léxicos y sintácticos, que se

encargan de traducir programas escritos en lenguajes de alto nivel a instrucciones ejecutables por

una máquina real.

Inteligencia artificial: La teoría de la computación, incluyendo la Máquina de Turing, ha sido

relevante en el desarrollo y estudio de la inteligencia artificial y el aprendizaje automático,

proporcionando fundamentos teóricos y límites en términos de lo que puede ser computado y

automatizado.

Bibliografía

ALONSO CORTÉS, Á. El fantasma de la máquina de lenguaje: por qué el

lenguaje no es un autómata. ed. Madrid: Biblioteca Nueva, 2013. 188 p.

Disponible en: https://elibro.net/es/ereader/itacapulco/117468?page=1.

Consultado en: 25 May 2023

 26

González, E. (2014). Programación de autómatas SIMATIC S7-300: lenguaje

AWL.. Cano Pina. https://elibro.net/es/lc/itacapulco/titulos/43097

GONZÁLEZ RUEDA, E. Ejercicios resueltos para autómatas SIMATIC S7-300

(Lenguaje AWL). ed. Barcelona: Cano Pina, 2012. 102 p. Disponible en:

https://elibro.net/es/ereader/itacapulco/43096?page=1. Consultado en: 25 May

2023

Bastarrica, M. C. (2006). Input/ output autómatas como lenguaje de definición de

arquitecturas.. Red Revista de Facultad de Ingeniería.

https://elibro.net/es/lc/itacapulco/titulos/12249

Constable, L., Meloni, B., Vázquez, J., Giró, J. (2015). Lenguajes formales y teoría

de autómatas. Colombia: Alpha Editorial.