MAQUINA TURING

Indice

1. Definición formal e las M. T.
2. Construcción de las M. T.
3. Lenguajes de aceptación por las M.T.
4. M.T. como e numeradores
5. M.T. restringidas

1. Definición formal e las M. T.

Una MT es una forma de simular una máquina computacional compuesta por estados y transiciones que seguir. La MT está formada por una cinta, un conjunto de estados, un alfabeto de entrada, un alfabeto para la cinta, una función de transición, un estado inicial y unos estados finales. La cinta es leida con un único cabezal, y en la misma se puede leer o escribir simbolos de los dados en el alfabeto para la cinta. Los movimientos permitidos en la cinta son; izquierda, derecha o mantenerse en el sitio.

     2. Construcción de las M. T.

Mediante esta técnica se puedan desarrollarse máquinas de Turing complejas a partir de  bloques de elementales a partir de máquinas mas 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

a)    Elimine las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.

b)    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.

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

3. Lenguajes de aceptación por las M.T.

Aceptan lenguajes formales que pueden ser generados por una gramática de tipo 0: recursivamente innumerable (r.e) Las maquinas de turing son los reconocedores de lenguaje más poderosos que existen.

Lenguajes regulares: las gramáticas (de tipo 3) formales definen un lenguaje describiendo como se pueden generar las cadenas del lenguaje… Las gramáticas regulares (aquellos reconocidos por un autómata finito). Son las gramáticas más restrictivas. El lado derecho de una producción debe contener un símbolo Terminal y como máximo un símbolo no Terminal.

Lenguajes Libres de contexto: Estas gramáticas conocidas también como gramáticas de tipo 2 o gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes del contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determinista o no determinista. Como toda gramática se definen mediante una cuádrupla G=N, T, S, P), siendo N un conjunto finito de símbolos no terminales; T un conjunto de símbolos terminales: P un conjunto finito de producciones; S es el símbolo distinguido o axioma

4.. M.T. como e numeradores

Hay varias definiciones alternativas para las máquinas de Turing simples. Se denominan variantes del modelo de máquina de Turing y son equivalentes en poder con el modelo original, es decir, reconocen la misma clase de lenguajes.

Un tipo de variante de máquina de Turing se llama  enumerador es, en términos simples, una máquina de Turing con una impresora adjunta. La máquina utiliza esta impresora como un dispositivo de salida para imprimir cadenas. Cada vez que la máquina de Turing desea agregar una cadena a la lista, envía la cadena a la impresora.

5. M.T. restringidas

Presentaremos algunas variantes de las máquinas de Turing y veremos que son equivalentes. Mostraremos las equivalencias entre las diversas modificaciones de las máquinas de Turing de manera más bien coloquial. Anque se puede presentar demostraciones rigurosas en base a descripciones instantáneas, aquí las omitiremos con la certeza de que el lector podrá construirlas a partir de las indicaciones que presentamos.  denotará a la clase de máquinas de Turing tal como las hemos definido. Diremos que dos clases de máquinas  y  son equivalentes si toda máquina en una clase es simulada por una máquina en la otra, es decir,donde c y d son funciones apropiadas de conversión de palabras de un alfabeto a otro, considerando los alfabetos de ambas máquinas, que cumplen además . Máquinas con cintas semi-infinitas, : Estas son máquinas de Turing donde las casillas de la cinta se ponen en correspondencia con  mas no con , es decir, la cinta de cada máquina de esta clase tiene una casilla inicial a la izquierda, digamos c₀, y se prolonga indefinidamente a la derecha