Tarea7

TEORÍA DE COMPUTABILIDAD

La ciencia de la computación es un cuerpo sistematizado del conocimiento concerniente al cálculo, que sesostiene en dos áreas fundamentales: La Teoría de la Computabilidad, basada en las ideas y los modelosfundamentales subyacentes al cálculo, y las técnicas de la ingeniería para el diseño de algoritmos. Este artículoestá pensando en la importancia del primer aspecto.

La Teoría de la Complejidad computacional estudia losrecursos requeridos para resolver un problema como son el tiempo y el espacio; por su parte la teoría de lacomputabilidad se interesa en expresar los problemas como algoritmos sin tener en cuenta la información sobrelos recursos necesarios para ello.Para abstraer las variaciones entre los diferentes sistemas computacionales se utiliza una máquina deTuring como un referente fijo, considerado como un modelo de máquina isofórmica a cualquier otro sistemainformático.

La Tesis de Church-Turing nos dice que si la máquina de Turing no puede resolver un problema, ninguna otracomputadora podrá hacerlo, puesto que no existe algoritmo para resolver el problema. Por esa razón, laslimitaciones corresponderían a los procesos computacionales y no a la tecnología.Palabras clave: Complejidad computacional, computabilidad, eficiencia de

La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing. La teoría de la computabilidad se interesa a cuatro preguntas:
* ¿Qué problemas puede resolver una máquina de Turing? * ¿Qué otros formalismos equivalen a las máquinas de Turing? * ¿Qué problemas requieren máquinas más poderosas? * ¿Qué problemas requieren máquinas menos poderosas?
La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina.
¿Qué problemas puede resolver una máquina de Turing? [editar]
No todos los problemas pueden ser resueltos. Un problema indecidible es uno que no puede ser resuelto con un algoritmo aún si se dispone de espacio y tiempo ilimitado. Actualmente se conocen muchos problemas indecidibles, como por ejemplo:
* El Entscheidungsproblem (problema de decisión en alemán) que se define como: Dada una frase del cálculo de predicados de primer orden, decidir si ella es un teorema. Church y Turing demostraron independientemente que este problema es indecidible. * El Problema de la parada, que se define así: Dado un programa y su entrada, decidir si ese programa terminará para esa entrada o si correrá indefinidamente. Turing demostró que se trata de un problema indecidible. * Un número computable es un número real que puede ser aproximado por un algoritmo con un nivel de exactitud arbitrario. Turing demostró que casi todos los números no son computables. Por ejemplo, la Constante de Chaitin no es computable aunque sí que está bien definido.
¿Qué otros formalismos equivalen a las máquinas de Turing? [editar]
Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones. Las funciones que pueden ser computadas con el cálculo Lambda son exactamente aquellas que pueden ser computadas con una máquina de Turing. Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde a la noción de cómputo en una máquina de Turing.
Los computadores electrónicos, basados en la arquitectura Eckert-Mauchly así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una máquina de Turing si dispusieran de recursos ilimitados de tiempo y espacio. Como consecuencia, los lenguajes de programación tienen a lo sumo el mismo poder de expresión que el de los programas para una máquina de Turing y en la práctica no todos lo alcanzan. Los lenguajes con poder de expresión equivalente al de una máquina de Turing se denominan Turing completos.
Entre los formalismos equivalentes a una máquina de Turing están:
* Máquinas de Turing con varias cintas * Máquinas de Turing con cintas bidimensionales (o una infinidad de cintas lineales) * Máquinas de Turing con número limitado de estados y símbolos para la cinta * Máquinas de Turing con solo dos estados * Autómatas finitos con dos pilas * Autómatas finitos con dos contadores * Gramáticas formales * Sistemas de correspondencia de Post * Cálculo Lambda * Funciones recursivas parciales * Casi todos los lenguajes de programación modernos si dispusieran de memoria ilimitada * Autómatas celulares * El Juego de la vida de John Conway * Máquinas de Turing no determinísticas * Máquinas de Turing probabilísticas * Computador cuántico
Los últimos tres ejemplos utilizan una definición ligeramente diferente de aceptación de un lenguaje. Ellas aceptan una palabra si cualquiera, cómputo acepta (en el caso de no determinismo), o la mayoría de los cómputos aceptan (para las versiones probabilística y cuántica). Con estas definiciones, estas máquinas tienen el mismo poder de expresión que una máquina de Turing.
¿Qué problemas requieren máquinas más poderosas? [editar]
Se considera que algunas máquinas tienen mayor poder que las máquinas de Turing. Por ejemplo, una máquina oráculo que utiliza una caja negra que puede calcular una función particular que no es calculable con una máquina de Turing. La fuerza de cómputo de una máquina oráculo viene descrita por su grado de Turing. La teoría de cómputos reales estudia máquinas con precisión absoluta en los números reales. Dentro de esta teoría, es posible demostrar afirmaciones interesentes, tales como «el complemento de un conjunto de Mandelbrot es solo parcialmente decidible».Obtenido de "http://es.wikipedia.org/wiki/Teoría_de_la_computabilidad"

Tarea 6

AUTÓMATAS
PROBABILÍSTICOS O
ESTOCÁSTICOS
Autómatas Probabilísticos
􀁺 En su funcionamiento interviene el concepto de probabilidad,
asociada a que se produzca una determinada transición.
􀁺 Son autómatas finitos en los que las transiciones entre estados
a partir de símbolos de entrada pueden no producirse de forma
segura (probabilidad = 1) sino que existe una determinada
probabilidad asociada a que se produzca la transición.
􀁺 No se habla del estado en el que se encuentra el autómata en
un determinado instante, sino de la probabilidad de que se
encuentre en cada uno de los estados del autómata.
􀁺 Aplicaciones reales basadas en comportamientos probabilísticos
de transición, pej. Movimiento de robots, reconocimiento de voz,
lenguaje natural, etc.

Definición
AFP = (Σ, Q, M, P(0), F), es una quíntupla
􀂾 Σ: alfabeto de entrada
􀂾 Q: conjunto de estados, finito y no vacío
􀂾 M: conjunto de matrices de probabilidad de transición entre estados.
M = {Ma  a ∈ Σ}, Ma contiene las probabilidades de transición de un
estado a otro cuando se recibe el símbolo a. Para cada
símbolo del alfabeto, existe una matriz de probabilidades
􀂾 P(0): vector de estado inicial: contiene la probabilidad de
encontrarse en el estado inicial. Cada estado de Q tiene asociada
una probabilidad de ser el estado inicial
􀂾 F⊆Q: Conjunto de estados finales o de aceptación (no vacío).
Matrices de Probabilidad de Transición
􀁺 Por cada símbolo a de Σ se define una matriz de probabilidad de
transición, M(a), que define la probabilidad de dado que el autómata se
encuentre en un determinado estado y reciba el símbolo de entrada a,
transite a cada uno de los demás estados.
∀a ∈ Σ, ∃ M(a) =
donde:
􀂾 n: número de estados: Q
􀂾 pij: probabilidad de que estando en el estado i y recibiendo una a
como entrada, transite al estado j. 0 ≤Pij ≤ 1
􀂾 para cada estado i, se cumple:
p11 p12 ... p1n
p21 p22 ... P2n
... ...... ....
pn1 pn2 ....pnn
Σ = = n
j pij 1 1
Vectores de estados
􀁺 P(t) es el vector de estados en un instante t. Indica la probabilidad de
cada estado en el instante t
􀂾 Tiene una componente para cada estado del AFP.
􀂾 P(t) = (P1(t), ..., Pn(t)), para un AFP con n estados
􀂾 Cada Pi(t) es la probabilidad de que el AFP se encuentre en el estado i.
􀂾 Se cumple:
􀂾 La probabilidad de que el AFP se encuentre en el instante t+1 en el estado i,
si el símbolo que se lee es “a”, deberá considerar la suma de las
probabilidades de llegar a i desde cada uno de los j posibles:
􀂾 Para el vector completo:
Σ = = ∀ n
i pi t 1 1,
Σ = + = n
j Pi t pj t xMji a 1 ( 1) ( ) ( )
P(t +1) = P(t) xM(a)
􀁺 Según los valores de M(a) y M(b) (I):
􀂾 M (a) = M (b) =
􀂾 t = 0, P(0) = {Pp(0) Pq(0)}
􀂾 t = 1, a la llegada de una “a” o una “b”:
P(1) = {Pp(0) x 1 + Pq(0) x 0 Pp(0)x 0+ Pq(0) x 1} = {Pp(1) Pq(1)}
AF Probabilísticos. Ejemplo
1 0
0 1
Ppp=1 p q Pqq=1
􀁺 Según los valores de M(a) y M(b) (II):
􀂾 M (a) = M (b) =
􀂾 t = 0, P(0) = {Pp(0) Pq(0)}
􀂾 t = 1, a la llegada de una “a” o una “b”:
P(1) = {Pp(0) x 0 + Pq(0) x 1 Pp(0)x 1+ Pq(0) x 0} = {Pq(1) Pp(1)}
AF Probabilísticos. Ejemplo
0 1
1 0
p q
Ppq=1
Pqp=1
􀁺 Según los valores de M(a) y M(b) (III):
􀂾 M (a) = M (b) =
􀂾 t = 0, P(0) = {Pp(0) Pq(0)}
􀂾 t = 1, a la llegada de una “a” o una “b”:
P(1) = {Pp(0) x 0.5 + Pq(0) x 0.5 Pp(0)x 0.5+ Pq(0) x 0.5} = {Pp(1) Pq(1)}
Ppp=0.5 Pqq=0.5
AF Probabilísticos. Ejemplo
0.5 0.5
0.5 0.5
p q
Ppq=0.5
Pqp=0.5
􀁺 Sea el AFP, AFP1= ({0,1}, {q1, q2, q3}, M, (1/3 1/3 1/3), {q3}), donde
M = {M(0), M(1)}
M (0) = y M(1) =
Si P(0) = (1/3 1/3 1/3) y se recibe un 0, escribir P(1).
P(1) = {P1(1) P2(1) P3(1)}
P1(1) =
P2(1) =
P3(1) =
P(1) = (5/18 4/9 5/18), por lo que en el instante t=1, el estado más probable es
q2
AF Probabilísticos. Ejemplo
1/3 1/3 1/3
1/2 0 1/2
0 1 0
1/2 1/2 0
1/3 2/3 0
0 0 1
(0) (0) 1/ 3 1/ 3 1/ 3 1/ 2 1/ 3 0 5/18 3
1 1 Σ = + + = = x x x x j Pj M j
(0) (0) 1/ 3 1/ 3 1/ 3 0 1/ 3 1 4 / 9 3
1 2 Σ = + + = = x x x x j Pj M j
(0) (0) 1/ 3 1/ 3 1/ 3 1/ 2 1/ 3 0 5/18 3
1 2 Σ = + + = = x x x x j Pj M j
􀁺 Sea el AFP = (Σ, Q, M, P(0), F, Θ), donde Θes un umbral con valores
entre 0 y 1.
􀂾 Se recibe la palabra x = a1a2...ap
􀂾 El vector de estados en el instante p será:
P(p) = P(0) x M(a1) x M(a2) x ... x M(ap)
􀂾 El lenguaje aceptado por el AFP es:
L = {x  x∈Σ + y Pf(x) ≥ Θ} siendo Pf(x): probabilidad del estado final
Lenguaje aceptado por un AFP
P(1)
P(2) ................ Desde el estado inicial con x
Una palabra es aceptada por un AFP cuando la probabilidad del
estado final, una vez calculado el vector de estados, es ≥ Θ
􀁺 En el APF1 anterior, calcular el vector de estados P(x) al recibir la
palabra x = 01 y decir si sería aceptada por el AFP1.
P(01) = P(0) x M(0) x M(1) =
(1/3 1/3 1/3) x x = (5/18 4/9 5/18) x =
= (31/108 47/108 5/18)
Para Θ = 1/2 la palabra x = 01 no sería aceptada Pf =5/18 < x =" 01" pf ="5/18≈"> 0.25
El lenguaje aceptado depende del umbral, Θ
Lenguaje aceptado por un AFP. Ej
1/3 1/3 1/3
1/2 0 1/2
0 1 0
1/2 1/2 0
1/3 2/3 0
0 0 1
1/2 1/2 0
1/3 2/3 0
0 0 1
􀁺 Se pueden ver los AFD’s como un caso particular de AFP:
donde:
􀂾 P(0) es un vector booleano, que contiene un único 1, en la
componente del estado inicial.
􀂾 ∀ a∈Σ, M(a) es una matriz de 0’s y 1’s que se construye a partir de
f, haciendo Maij = 1 si f(qi,a) = qj y Maij = 0 en caso contrario.
􀂾 Todas las filas de M(a) tendrán un solo 1.
􀂾 Θ>0, lo habitual es Θ=1.
AFD’s como AFP’s
AFD = (Σ,Q, f ,q0, F) ⇒ AFP = (Σ,Q,M,P(0),F,Θ)
∀ AFD ∃ AFP equivalente ⇒ L. Regulares ⊂ L. reconocidos por AFP’s

Tarea 5

Diseñe los sig AFNs
a) En el alfabeto {a,b} el AFNque acepta el lenguaje en donde las palabras no contienen la cadena "aba"o terminan en "baa"


b) En el alfabeto {0,1} el AFN que acepta el lenguaje en donde las palabras contienen una secyuencia 0010 a la izquierda y 0011 a la derecha.

TAREA 4

Reducir los autómatas de la tarea 3 por clase de equivalencia

TAREA 3.2

Simplifique el siguiente autómata a través del método de tabla de estados distinguibles

Resolución:

1) tabla de estados distinguibles

2) simplificando y redibujando:

finalmente:


El autómata se reduce hasta dos estados

y ahora observamos el árbol par ver que si son equivalentes.

TAREA 3.1

Simplifique por el método de tabla de estados distinguibles el siguiente autómata:

1)tabla







2) aplicando el método y redibujando


3)Finalmente



Es equivalente, revisando el árbol:

TAREA 3

Determine si los siguientes autómatas son equivalentes:



Desarrollo del árbol




Concluimos que sí son equivalentes M1 y M2