viernes, 27 de mayo de 2011

INTRODUCCIÓN

En las Unidades precedentes se han estudiado lo que se puede considerar las máquinas abstractas que permiten solucionar ciertos tipos de algoritmos, los algoritmos en los que no puede recordarse más que una cantidad fija de información y otros en los que la información desarrollada durante la ejecución del algoritmo puede recuperarse solo en concordancia con la regla “lifo” últimos en entrar primeros en salir, en esta unidad se describe una maquina abstracta, llamada Máquina de Turing , que es aceptada de manera amplia como modelo general de computación, aunque las operaciones básicas de esta máquina son comparables en su sencillez a las de las máquinas estudiadas en las unidades anteriores, las nuevas maquinas pueden realizar una amplia variedad de operaciones de cómputo.

Además de aceptar lenguajes les es posible computar funciones y de conformidad con la tesis de Church-Turing, ejecutar casi cualquier procedimiento algorítmico concebible.

¿Por qué creemos que las máquinas de Turing son una buena formalización del concepto de algoritmo?
  • Porque cada programa de una máquina de Turing puede ser implementado.
  • Porque todos los algoritmos conocidos han podido ser implementados en máquinas de Turing.
  • Porque todos los otros intentos por formalizar este concepto fueron reducidos a las máquinas de Turing.
  • Los mejores intentos resultaron ser equivalentes a las máquinas de Turing.
  • Todos los intentos “razonables” fueron reducidos eficientemente.
  • Tesis de Church: Algoritmo = Máquina de Turing.

OBJETIVOS

OBJETIVO GENERAL
Reconocer la importancia y el poder computacional de las Máquinas de Turing en el contexto de la solución de problemas computacionales de reconocimiento de Lenguajes.

OBJETIVOS ESPECIFICOS
Estudiar las Máquinas de Turing y sus propiedades básicas.

miércoles, 25 de mayo de 2011

1. Realiza una breve síntesis del invento patentado por Alan Turing en 1931.


El matemático inglés Alan Turing fue uno de los pioneros más importantes en la creación de lo que se convertiría en La Teoría de la Computación.

En 1931, decidió reformular ciertos resultados de la lógica matemática expresando las formulaciones de teoremas en términos de algoritmos que podían ser interpretados por una máquina teórica.

Lo que pretendía Turing era estudiar los límites de las máquinas que realizaban cálculos automáticos. Era un tiempo en que se estaban sentando las bases de cómo serían los computadores. Ya era posible contar con los elementos para construir estas máquinas y Turing quería ver cuál era el poder de éstas y hasta qué punto serían capaces de ayudarnos a resolver problemas complejos.

Turing describió una máquina teórica que manipula los símbolos escritos en una larga cinta de acuerdo a una tabla de reglas. La máquina de Turing consta de un cabezal que puede leer y/o escribir en una cinta infinita de papel. La máquina puede realizar sólo las siguientes operaciones: avanzar el cabezal hacia la derecha, avanzar el cabezal hacia la izquierda, leer el contenido de una celda de la cinta, borrar el contenido de una celda y escribir en la cinta.

En 1937, publica un famoso artículo que desarrolla el teorema de Gödel, y que puede considerarse como el origen oficial de la Informática Teórica.

Las máquinas de Turing fueron propuestas por Alan en un intento para dar una definición matemática precisa de algoritmo o procedimiento mecánico. Los primeros trabajos de Turing y Alonzo Church abrieron la rama de la lógica matemática, que eventualmente se convertiría en la Teoría de Funciones Recursivas.

La máquina de Turing, mecanismo que formaliza el concepto de algoritmo, que pretende ser lo suficientemente general como para resolver cualquier problema posible (siempre que sea computacionalmente abordable), se introduce para demostrar la validez de los postulados de Gödel. Es decir, Turing demuestra que existen problemas irresolubles, inasequibles para cualquier máquina de Turing, y por ende, actualmente, para cualquier ordenador. Al ser la máquina de Turing un modelo ideal de máquina capaz de adoptar una infinidad de estados posibles, resulta obvio pensar que su realización está fuera del alcance práctico. Sin embargo, debido a la gran capacidad de los ordenadores actuales, la máquina de Turing resulta ser un modelo adecuado de su funcionamiento.

2. Describa en qué consiste la prueba de Turing (maquina y persona)


Prueba o test de Turing es un procedimiento desarrollado por Alan Turing para identificar la existencia de inteligencia en una máquina y comprobar que una máquina puede llegar a pensar al igual que una persona.

Este test fue expuesto en 1950 en un artículo (Computing machinery and intelligence) para la revista Mind que sigue siendo hoy día una de las cabezas de lanza de los defensores de la Inteligencia Artificial.

Está fundamentado en la hipótesis positivista de que, si una máquina se comporta en todos los aspectos de forma inteligente, entonces debe ser inteligente.

Básicamente la prueba consiste en un desafío en el cual la máquina debe hacerse pasar por humana en una conversación con un hombre a través de una comunicación de texto en modo chat. Al sujeto no se le avisa si está hablando con una máquina o una persona de modo que si el sujeto es incapaz de determinar si la otra parte de la comunicación es humana o máquina, entonces se considera que la máquina ha alcanzado un determinado nivel de madurez: es inteligente.

Tal procedimiento tiene la ventaja de no tener que definir lo que es la inteligencia. Turing creía firmemente que máquinas que piensen llegarían a existir y predijo que hacia el año 2000 una máquina jugaría al ‘juego de imitación’, como él llamó al test, de manera que un interrogador medio no tendría más del 70 por 100 de posibilidades de efectuar la identificación correcta tras cinco minutos de preguntas." (Enric Trillas55)

3. ¿Qué es una maquina de Turíng y cómo funciona?

Es un dispositivo de reconocimientos de lenguaje, es más general que cualquier autómata finito y cualquier autómata de pila, debido a que ellas pueden reconocer tanto los lenguajes regulares, como los lenguajes independientes de contexto y además muchos otros tipos de lenguajes.
Una máquina de Turing (abreviado MT), 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 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.
La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el carácter blanco (que representaremos con “t”). La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el extremo izquierdo, la MT la cabeza lectora es de lectura y escritura, por lo que la cinta puede ser modificada en curso de ejecución. Además, en la MT la cabeza se mueve bidireccionalmente (izquierda y derecha), por lo que puede pasar repetidas veces sobre un mismo segmento de la cinta.
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.

4. Mediante un ejemplo de máquina de Turing ilustre su representación gráfica, elementos correspondientes y reconocimiento de cadena.







5. Describa la clasificación de las Máquinas de Turing y defina cada una de ellas.


Máquina de Turing con Directiva de Permanecer: Recuérdese que la máquina de Turing sencilla sitúa la cabeza de lectura/escritura sobre el primer B que haya a la izquierda de la posición actual. Para hacerlo, busca fuera de la celda actual y retrocede. Esto es debido a la definición original que requiere que por cada transición se mueva la cabeza de la cinta.

La función de transición estaba definida como: d: Q x G ® Q x G x {R, L} y puede ser modificada como: d: Q x G ® Q x G x {R, L, S} donde S significa "permanecer", es decir no mover la cabeza de lectura/escritura.

Por tanto d (q, s)= (p, s ’, S) significa que se pasa del estado q al p, se escribe s’ en la celda actual y la cabeza se queda sobre la celda actual.


Máquina de Turing Multipista: Es aquella mediante la cual cada celda de la cinta se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celda subdividida en tres subceldas. Se dice que esta cinta tiene múltiples pistas. Puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-tuplas ordenadas. En el ejemplo anterior, las celdas de la cinta contienen (B, a, a), (b, a, a) y (b, b, B). Por tanto, los movimientos que realice está máquina dependerán de su estado actual y de la n-tupla que represente el contenido de la celda actual.

 
Una máquina de Turing multipista no tiene más potencia que la máquina de Turing original. Sin embargo, hace que sea más fácil la construcción de máquinas de Turing que resuelvan ciertos problemas.


Máquina de Turing de Cinta infinita en una Dirección: Máquina de Turing que usa una cinta que se extiende infinitamente en una única dirección. Generalmente, se tiene una cinta que se extiende infinitamente hacia la derecha. No está permitido realizar ningún movimiento hacia la izquierda a partir de la celda del extremo izquierdo. Desde luego, cualquier máquina de Turing de esta forma puede ser simulada por una de las que responden a la definición original. Para cada computación, simplemente se marca una de las celdas de la cinta infinita por los dos lados, como la celda que se encuentra en el límite izquierdo.
Máquina de Turing en Dos Direcciones: Una máquina de Turing con una cinta infinita en un sentido puede simular una máquina de Turing con la cinta infinita en los dos sentidos pero con dos pistas. Sea M una máquina de Turing con una cinta infinita en los dos sentidos. La máquina de Turing M’, que tiene una cinta infinita en un sentido, puede simular a M si tiene una cinta con dos pistas. La cinta superior contiene la información correspondiente a la parte derecha de la cinta M, a partir de un punto de referencia dado. La pista inferior contiene la parte izquierda de la cinta M (en orden inverso).


Máquina de Turing Multicinta: La máquina de Turing multicinta tiene varias cintas, cada una de las cuales tiene su propia cabeza de lectura/escritura. Las cabezas de lectura/escritura se controlan independientemente (es decir, al mismo tiempo, no tienen que moverse en la misma dirección, ni realizar el mismo número de movimientos, ni incluso, hacer nada a la vez). En un solo movimiento, esta máquina de Turing:

1. Cambia de estado dependiendo del estado actual y del contenido de las celdas de todas las cintas, que están analizando actualmente las cabezas de lectura/escritura.

2. Escriben un nuevo símbolo en cada una de las celdas barridas por sus cabezas de lectura/escritura.

3. Mueve cada una de sus cabezas hacia la izquierda o hacia la derecha (de forma independiente al resto de las cabezas).


Máquina de Turing Muldimensional: La máquina de Turing multidimensional es aquella que permite que la cinta tenga muchas dimensiones. Por ejemplo, una cinta de dos dimensiones que se extienda hacia abajo y hacia arriba, al igual que hacia la derecha y hacia la izquierda. Dependiendo del estado actual de la máquina de Turing y del símbolo analizado, cambia de estado, escribe un símbolo en la celda actual y se mueve a la izquierda, al derecha, hacia arriaba o hacia abajo. Por tanto, la función de transición para esta máquina de Turing será de la forma:

d : Q x G ® Q x G x {R, L, U, D}

Una máquina de Turing multidimensional simula una máquina de Turing estándar. Simplemente realizando todas sus computaciones en una única dimensión. Una máquina de Turing estándar también puede simular una máquina de Turing multidimensional y, por tanto, la complejidad y la flexibilidad adicional que se debe a la múltiple dimensión, no es una capacidad real. Para simular una máquina de Turing de dos dimensiones mediante una máquina de Turing estándar, primero se asociara una dirección a todas las celdas de la cinta. Una forma de hacerlo es fijar, de forma arbitraria, un lugar en la cinta a partir del cual se asignarán las coordenadas a las celdas de la misma forma que se realiza en un plano de coordenadas.

Entonces, se usara una cinta de dos pistas para simular la máquina de Turing. Una pista se encargará de almacenar el contenido de las celdas y la otra las coordenadas, utilizando un símbolo (*) para separar los valores de las coordenadas. Para simular un movimiento de una máquina de Turing de dos dimensiones, está máquina calcula la dirección de la celda a la que se moverá la máquina de Turing dos dimensiones. Entonces, localiza la pista inferior la celda con dicha dirección y cambia el contenido de la celda en la pista superior.


Máquina de Turing No determinista: La máquina de Turing No determinista es aquella que para un estado actual y el símbolo actual de la cinta, puede haber un número finito de movimientos a elegir. Por lo tanto, la regla de transición d de dicha máquina, satisface

d (q, s ) Í Q x G x {R, L}


Máquina de Turing con Múltiples Cabezales: Tiene k cabezales de L/E, como la multicinta, pero con una sola cinta. Los cabezales operan todos de forma independiente. Como en las Máquinas de Turing multicinta, se admiten movimientos L, R ó Z.


Máquina de Turing Offline: Es un caso particular de las Máquinas de Turing multicinta: tienen una cinta especial de sólo lectura en la que el cabezal, que sólo puede moverse hacia la derecha, no puede moverse de la zona delimitada por una par de símbolos especiales.

6. Cuáles son los lenguajes aceptados para una Máquina de Turing. De 3 ejemplos de cadena de estos lenguajes.

Una cadena de entrada w es aceptada por una MT M si el cómputo que se indica la configuración inicial q0w termina en una configuración instantánea:
 
p es un estado de aceptación, en la cual M se detiene completamente. El lenguaje L(M) aceptado por una MT M se define como:



M se para en: 
, Si la cadena de entrada en una máquina M pertenece a L(M), la maquina M siempre se detiene.

 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 determínistico o no determínistico. 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.



EJEMPLOS:

Ejemplo 1: Reconocimiento de un Lenguaje Regular.

  
Este es un lenguaje regular porque puede ser definido también por la expresión regular:  (a+b)b(a+b)*


Ejemplo 2: Reconocimiento de una GLC, aceptada por un APD determinista.



Ejemplo 3: Reconocimiento de una GLC, aceptada por un APD no determinista.


CONCLUSIONES:

Nuestro primer ejemplo era solamente un AF convertido, y el lenguaje que aceptaba era Regular.

El segundo ejemplo aceptaba un lenguaje Libre de Contexto y No Regular y la MT dada empleaba alfabetos separados para escribir y leer.

La tercera máquina aceptaba un lenguaje que era también Libre de Contexto, pero que solo podía ser aceptado por un APD No Determinístico, sin embargo la MT diseñada es Determinística.

lunes, 23 de mayo de 2011

7. Mediante un grafo explique la construcción modular de las Máquinas de Turing y describa cada uno de sus elementos.

El objetivo de la creación modular de una maquina de Turing es poder desarrollar máquinas complejas a partir de bloques elementales, a partir de maquinas 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 

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

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, la otra 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 de l/e de la segunda se situará, al comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primera.

Maquinas de Turing Compuesta.