Instituto tecnológico superior de ciudad constitución

Ingeniería en sistemas computacionales

LENGUAJES Y AUTOMATAS I

Máquinas de Turing

Raul Zarate Ledezma

5SV

Ciudad Constitución Baja California Sur. A miércoles 03 de diciembre de 2014

Instituto Tecnológico Superior de Ciudad Constitución

Ingeniería en Sistemas Computacionales

LENGUAJES Y AUTOMATAS I

Máquinas de Turing

M.S.C. AMÉRICO ANTONIO LEÓN BARRÓN

Raul Zarate Ledezma

5SV

Ciudad Constitución Baja California Sur. A miércoles 03 de diciembre de 2014

1

La presente investigación se refiere al tema de las Maquinas Turing que se puede

definir como un modelo computacional que realiza una lectura/escritura de manera

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

Hablaremos de cómo construir una base de módulos de una máquina de Turing a

través de diagramas de transición. Finalmente mostraremos los tipos de lenguajes

que se puede aceptar por la MT.

2

Definición formal de una Máquina de Turing

Una máquina de Turing 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á formado por un alfabeto de entrada y uno de salida, un símbolo

especial llamado blanco (normalmente 𝑏, ∆ 𝑜 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 puede ser infinita) pertenecientes al alfabeto de entrada.

Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

𝑀 = (𝑄, 𝛴, 𝛤, 𝛿, 𝑞0, 𝐵, 𝐹)

Cuyos componentes tienen el siguiente significado:

𝑄: Conjunto finito de estados.

𝛴: El conjunto finito de símbolos de entrada.

𝛤: El conjunto completo de símbolos de cinta; 𝛴 siempre es un subconjunto de 𝛤.

𝛿: La función de transición. Los argumentos de 𝛿 (𝑞, 𝑋) son un estado q y un símbolo

de cinta 𝑋. El valor de 𝛿 (𝑞, 𝑋), si está definido, es (𝑝, 𝑌, 𝐷), donde:

1. 𝑝 es el siguiente estado de 𝑄.

2. 𝑌 es el símbolo de 𝛤, que se escribe en la casilla que señala la cabeza y que sustituye a cualquier símbolo que se encontrara en ella.

3

3. 𝐷 es una dirección y puede ser 𝐿 o 𝑅, lo que nos indica la dirección en que la cabeza se mueve, “izquierda” (𝐿) o “derecha” (𝑅), respectivamente.

𝑞0: El estado inicial, un elemento de 𝑄, en el que inicialmente se encuentra la unidad de control.

𝐵: El símbolo espacio en blanco. Este símbolo pertenece a 𝛤 pero no a 𝛴; es decir, no es un símbolo de entrada. El espacio en blanco aparece inicialmente en todas las casillas excepto en aquéllas que se almacenan los símbolos de la entrada.

𝐹: El conjunto de los estados finales o de aceptación, un subconjunto de 𝑄.

Construcción modular de una MT.

El objetivo de la creación modular de una máquina de Turing es poder desarrollar

máquinas complejas a partir de bloques elementales, a partir de máquinas más

pequeñas, mediante 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:

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

excepto la de aquel donde iniciara la maquina compuesta.

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 combinan.

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

Lenguajes aceptados por la MT

De acuerdo a la clasificación de los lenguajes formales realizada por el norteamericano

Avram Chomsky, la Máquina de Turing acepta los lenguajes más generales, o tipo cero

4

(0), también llamados lenguajes recursivamente numerables. Las máquinas de turing

son los reconocedores de lenguaje más poderosos que existen.

Un lenguaje recursivamente numerables es un lenguaje formal para el cual existe una

máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje, pero

que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no

pertenece al lenguaje. Todos los lenguajes, regulares, independientes de contexto,

dependientes de contexto y recursivos son recursivamente numerables. . El término

“recursivamente enumerable” viene de los formalismos de computación que

precedieron a la máquina de Turing pero que definen la misma clase de lenguajes o

funciones aritméticas.

Una cadena ω∈A^*, es aceptada por una MT, si comienza en el estado e0, con la cabeza de lectura/escritura en el símbolo más a la izquierda, luego de leer toda la

cadena ω, llega a un estado e_f∈F. El lenguaje aceptado por MT, es el conjunto de todas las cadenas que son aceptadas por MT: L(MT)={ω / e_0 ω ⊢*α_1 e_f α_2 y e_f∈F y α_1,α_1 ∈C^* y ω∈A^* } Tenemos por ejemplo una MT que reconoce el lenguaje {0^n 1^n:n≥1}. Las transiciones de la máquina se representan como sigue:

Se evalúa la cadena w = 1100, arrojando el siguiente resultado:

Otras cadenas también aceptadas por esta MT son 11110000, 10, 11111110000000.

5

Podemos concluir que una Máquina de Turing es una máquina mediante la cual es

posible la categorización de problemas computacionales mediante el análisis de

complejidad de algoritmos, de acuerdo a su comportamiento.

6

Bibliografía

John E. Hopcroft, Teoria de autómatas, lenguajes y computación, PEARSON

EDUCACION S.A., Madrid, 2007.

http://10380054.galeon.com/u4.htm

http://maquinadeturingunad.blogspot.mx/2010/11/los-lenguajes-aceptados-para-

una.html

http://10380054.galeon.com/u4.htm

http://maquinasdeturing.blogspot.mx/2010/08/6-lenguajes-aceptados-por-una-mt.html