Maquina De Turing

I. INTRODUCCIÓN:

TEORÍA DE LOS LENGUAJES FORMALES:
Estudio de los Lenguajes con una fundamentación matemática. Esta representación adopta la forma de un mecanismo abstracto para generar o reconocer cualquier cadena del Lenguaje (llamada Gramática). Así, el conjunto de todos los programas válidos de Java o de C, puede considerarse como un Lenguaje Formal sobre el Alfabeto de símbolos de cadauno de esos mismos Lenguajes de programación.
LENGUAJE FORMAL:
Conjunto de palabras, producidas en base a las reglas que conforman una Gramática Formal.
Lenguaje con reglas explícitas y precisas para su sintaxis y semántica. Así, los Lenguajes Formales se distinguen de los naturales tales como el castellano, cuyas reglas a medida que evolucionan con el uso dejan de ser una definición completa oprecisa de la sintaxis del Lenguaje y mucho menos de su semántica.
GRAMÁTICA FORMAL:
Conjunto de reglas, empleadas para generar las palabras de un Lenguaje Formal. Todo Lenguaje Formal estará vinculado siempre a una Gramática Formal, que especificará el mecanismo de producción de las palabras que lo conforman.
Es un esquema generativo para la representación finita de los Lenguajes, es decir, unsolo modelo dinámico para generar palabras o cadenas de un Lenguaje. El deseo de formalizar los Lenguajes naturales fue lo que llevó a Noam Chomsky a la iniciación de este tema en 1956.

No existe un solo caso de un Lenguaje Formal que no sea producido por una Gramática Formal.

Noam Chomsky clasifica las gramáticas en 4 tipos:
TIPO 0: genera el lenguaje “RECURSIVAMENTE ENUMERABLE”
TIPO 1:genera el lenguaje “SENSIBLE AL CONTEXTO”
TIPO 2: genera el lenguaje “LIBRE DE CONTEXTO”
TIPO 3: genera el lenguaje “REGULAR”

COMPARACION DE LAS MAQUINAS SEGÚN SU GRAMÁTICA Y LENGUAJE ACEPTADOS

II. MODELO DE LA MAQUINA DE TURING:

Un modelo formal para un procedimiento efectivo deberá poseer ciertas propiedades. Primero, cada procedimiento deberá describir de manera finita. Segundo,el procedimiento deberá consistir en pasos discretos, cada uno de los cuales puede llevarse a cabo de manera mecánica. Este modelo fue introducido por Alan Turing en 1936. Aquí presentamos una variante del mismo.
El modelo básico ilustrado en la figura tiene un control finito, una cinta de entrada que está dividida en celdas y una cabeza de cinta que barre una celda de la cinta a la vez. La cintatiene una celda que está más a la izquierda, pero se extiende de manera infinita hacia la derecha. Cada celda de la cinta puede contener exactamente un símbolo de un número finito de símbolos de cinta. Inicialmente, las n celdas que están más a la izquierda, para alguna n > 0 finita, sujetan la entrada, que es una cadena de símbolos escogidos de un subconjunto de los símbolos de la cinta,llamados símbolos de entrada. Cada una del número infinito de celdas restantes sujetan el espacio en blanco, que es un tipo especial de símbolos que no es de entrada.

En un movimiento, dependiendo del símbolo del símbolo barrido por la cabeza de la cinta y del estado del control finito, la máquina de Turing
a. Cambia de estado.
b. Imprime un símbolo en la celda de la cinta que estásiendo barrida, sustituyendo lo que se encontraba ahí escrito.
c. Mueve su cabeza una celda hacia la izquierda o la derecha.
Ahora, una maquina de Turing será una 7-upla definida de la siguiente manera.

Por definición, al iniciar la operación de la MT, la cabeza lectora está posicionada en el carácter blanco a la izquierda de la palabra de entrada, el cual es el cuadro más a la izquierdade la cinta.
Decimos que la MT llegó al final de un cálculo cuando se alcanza un estado especial llamado HALT en el control finito, como resultado de una transición. Representaremos Halt por la letra ”H”. al llegar a H, se detiene la operación de la MT, y se acepta la palabra de entrada. Así, se dice que la MT posee un único estado de aceptación el cual es llamado Halt.
Cuando se desea que...