viernes, 6 de agosto de 2010

9. Ejemplos de aplicación de las MT

Ejemplo del Funcionamiento: se construye una MT que acepte el lenguaje L={a^i b^i c^i:i≥0}, sobre Σ={a,b,c}.


1. Se cambia la “a” por una X y se mueve hacia la derecha pasando por encima de todas las “a” e “Y”, hasta llegar a la primera “b”, cambia la primera “b” por una Y, se mueve a la derecha pasando por encima de las “b” y “Z”, y luego encuentra la primera “c” y la cambia por “Z” y se mueve a la izquierda.

2. Luego se mueve a la izquierda pasando por encima de “b”, “Y”, “a”, hasta encontrar la “X”, la reemplaza por una “X” y repite el proceso anterior, cuando la máquina reemplaza la cadena “X”, “Y” y “Z” reconoce la cadena vacía y busca el estado de aceptación.

Comprobación de la aceptación de la cadena w = aabbcc:



En cuanto a las aplicaciones de las MT, tenemos la Teoría de la computación:


Teoría de la computación:

La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas de acuerdo a su grado de dificultad.

La teoría de la computación comienza propiamente a principios del siglo XX, poco antes que las computadoras electrónicas fuesen inventadas. En esta época varios matemáticos se preguntaban si existía un método universal para resolver todos los problemas matemáticos. Para ello debían desarrollar la noción precisa de método para resolver problemas, es decir, la definición formal de algoritmo.

Algunos de estos modelos formales fueron propuestos por precursores como Alonzo Church (cálculo Lambda), Kurt Gödel (funciones recursivas) y Alan Turing (máquina de Turing). Se ha mostrado que estos modelos son equivalentes en el sentido de que pueden simular los mismos algoritmos, aunque lo hagan de maneras diferentes. Entre los modelos de cómputo más recientes se encuentran los lenguajes de programación, que también han mostrado ser equivalentes a los modelos anteriores; esto es una fuerte evidencia de la conjetura de Church-Turing, de que todo algoritmo habido y por haber se puede simular en una máquina de Turing, o equivalentemente, usando funciones recursivas. En 2007 Nachum Dershowitz y Yuri Gurevich publicaron una demostración de esta conjetura basándose en cierta axiomatización de algoritmos.

Uno de los primeros resultados de esta teoría fue la existencia de problemas imposibles de resolver algoritmicamente, siendo el problema de la parada el más famoso de ellos. Para estos problemas no existe ni existirá ningún algoritmo que los pueda resolver, no importando la cantidad de tiempo o memoria se disponga en una computadora. Asimismo, con la llegada de las computadoras modernas se constató que algunos problemas resolubles en teoría eran imposibles en la práctica, puesto que dichas soluciones necesitaban cantidades irrealistas de tiempo o memoria para poderse encontrar.


Máquinas Oráculo (O-Machines)

La máquina con oráculo, es una máquina de Turing equipada con un oráculo que es capaz de contestar preguntas sobre la pertenencia a un conjunto específico de números naturales.

Funcionamiento:

La máquina también tiene tres estados especiales: el "estado llamada", el "estado-1" y el "estado-0" y un símbolo marcador especial: μ (mú). Para usar su oráculo, la máquina debe escribir primero el símbolo μ en dos recuadros de la cinta, y entonces se entrará en el "estado llamada". En este estado se manda una petición al oráculo y la máquina termina en el "estado-1" si el número escrito en los cuadrados de la cinta entre los símbolos "μ" son un elemento del conjunto oráculo y termina en el "estado-0" en otro caso.

Una máquina oráculo con el "conjunto parada" en su oráculo puede computar la función del problema de la parada. Mientras este sería un ejemplo trivial del uso del conjunto oráculo, muchas otras funciones de interés pueden ser computadas utilizando el oráculo de la función de la parada. De hecho, esto permite que todas las funciones recursivamente enumerables sean computables.

Función Recursiva Enumerable:

Una función "f" es recursivamente enumerable por definición si y sólo si hay una máquina de Turing, m, tal que para todo n perteneciente a los ℕ, la máquina dará como salida 1 si f(n)=1 y dará salida 0 o un bucle infinito (la máquina diverge) en otro caso.

Además una O-Machine con el "oráculo de la parada" puede preguntar a su oráculo si m se detendrá para la entrada n. Si m no se detiene, la O-Machine puede devolver 0 (f(n) debe ser 0). Si m se detiene, entonces la O-Machine puede simplemente simular la entrada n en la máquina m y retornar su resultado.

Dada la potencia y la naturaleza del conjunto de parada, es utilizado a menudo en la teoría de la recursión para describir los diferentes niveles de computabilidad.

Si un conjunto es computable en una O-Machine con el oráculo X, se dice que es computable en X o recursiva en X. El conjunto de las funciones computables por una máquina de Turing puede encajar en esta jerarquía imaginando una máquina de Turing como una O-Machine con un oráculo vacío, por tanto hay un incremento obvio en la potencia de esta máquina. La generalización del conjunto de parada a las O-Machines con oráculo X se denota como X’, donde la (’) es conocida como el operador de salto. De esta manera, el problema de la parada (y todas las funciones recursivamente enumerables) se dice que son recursivas en el ∅’, mientras que el problema de la parada para máquinas con oráculo ∅’ son recursivas en el ∅’’, y así sucesivamente.

Las máquinas oráculo tienen una propiedad de que cualquier función de ℕ en ℕ es computable por alguna máquina oráculo, pero ningún oráculo es suficiente para permitir a las O-Machines que tengan acceso a este oráculo computar todas las funciones de ℕ en ℕ.

Esta situación nace del hecho de que una O-Machine es una combinación entre una parte clásica (la máquina de Turing de estados y transiciones finitas) y un oráculo (que es un conjunto posiblemente infinito de números). De alguna manera esto permite la trivialización de la computación generalizada (si pudiéramos elegir el oráculo una vez que conociéramos la función, ésta podría ser resuelta utilizando el oráculo como una tabla infinita de búsqueda). Sin embargo, el concepto de computación por una O-Machine es interesante y está bien fundado, ya que resolvemos funciones que pueden ser resueltas con un oráculo determinado.


MT como calculadora de funciones:


Como las maquinas de Turing pueden transformar cadenas de entradas, también se utilizan como mecanismos para calcular funciones.

MT M=(Q,Σ,Γ,q_0,T,B,δ)

Formalmente una

f:Σ^*→Γ^* (parcial o total)

calcula una función

q_0 w⊢*q_f v, donde v=f(w)

si para una entrada w se tiene:

Σ={a,b} y q_f

El modelo de MT no utiliza estado de aceptación, el estado es llamado estado final se usa para terminar el proceso de la entrada y producir la salida.



Ejemplo:

Supongamos que tenemos Σ={a,b} y q_f y que representamos los enteros positivos mediante cadenas solo de “as”. Así el entero “n” estaría representado por a^n.

Se puede construir la MT que calcule la función f(n,m) = n+m, implementando la transformación

a^n ba^m en a^(n+m) b

Solución:

Se recorren desde la izquierda todas las as hasta encontrar una “b”, esta se reemplaza por una “a”, cambiando de estado, en este mismo estado se recorren todas las “as” a la derecha y cuando se llega a un blanco se reemplaza por el mismo blanco se deja la cabecera a la izquierda y se reemplaza la “a” por un blanco para restarle la que adiciono y se mueve hacia la derecha y se cambia al estado final “q3”.

M=(Q,Σ,Γ,q_0,q_3,B,δ)

Donde la función se define así:

MT como generadoras de lenguaje


Otra de las capacidades importantes es la de generar lenguajes, tarea en la

MT M=(Q,Σ,Γ,q_0,T,B,δ)

Cual los estados finales son necesarios. Concretamente una MT genera un lenguaje L⊆Σ^* si:

M comienza a operar con la cinta en blanco en el estado inicial “q0”.

Cada vez que M retorna al estado inicial “q0”, hay una cadena u∈L escrita sobre la cinta.

Todas las cadenas de L son, eventualmente, generadas por M.

El siguiente MT genera cadenas con un numero par de “a” sobre Σ={a}


No hay comentarios:

Publicar un comentario en la entrada