Generador de todos los códigos de M.T. existentes

Partimos de las siguientes bases:

* Cualquier lenguaje sobre el alfabeto {0,1} se puede reconocer en una M.T. cuyo alfabeto de cinta sea {0,1,B}

* No hay necesidad de más de un estado final en cualquier M. T.

Sea la Máquina de Turing 

M = ⟨{0, 1}, {q1 , q2 , q3 }, {0, 1, B}, f , q1 , B, {q2 }⟩ 

con 

f(q1 , 1) = (q3 , 0, R) 

f(q3 , 0) = (q1 , 1, R) 

f(q3 , 1) = (q2 , 0, R) 

f(q3 , B) = (q3 , 1, L)

Podemos codificarla de la siguiente manera:

11101001000101001100010101001001100010010010100110001000100010010111 

(Más info en los apuntes 8.2.1) 

Teniendo en cuenta esta codificación descrita y conociendo el alfabeto Σ = {0, 1}, entonces crearemos un generador canónico de 0's y 1's tal que se vayan generando cadenas Σ* =  λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011...

Este generador irá sacando números en binario indefinidamente. A las cadenas generadas las hacemos pasar por otra M.T. que nos acepte las cadenas de entrada que se adecuen al formato correcto de una M.T. codificada. Si es correcta, generará la cadena, sino seguirá esperando más cadenas correctas.

Esta segunda M.T. M1 aceptaría cualquier cadena del siguiente lenguaje, 

L(M1) ={x ∈ Σ+ | x = 111(0i10j10k10l10m11)n1 / i,k,n > 0,  0 > j, l <= 3, k > 0,  0 > m <= 2 }

Y el Generador de M.T. sintácticamente correctas (M2) vendría a ser algo parecido a esto:

Donde si w ∈ L(M1) entonces la cadena w es una máquina de turing sintácticamente correcta.

En caso de no pertenecer a L(M1) no se generaría nada.

Por tanto queda demostrado que es posible la construcción de una M.T. capaz de generar todos los códigos de M.T. sintácticamente correctas.

En cuanto al apartado B de la cuestión, la respuesta es 2) Tengo infinitas máquinas, pero va a ser que no tengo bastantes.

Al estar involucrados los números enteros como indices de estados (y el propio generador incorporado), y sabiendo que son infinitos, es lógica esta conclusión. Dado que pueden existir M.T.'s con infinitos estados (infinitos pero contables) y a su vez el generador extrae infinitas cadenas, infinito se nos quedará corto.

Resumen de actividades del 14 al 21de Mayo.

* El grupo se volvió a reunir un miércoles más.
* Organizamos la faena
* Se repasó un poco la teoria vista en clase.

- Donde el viernes 16 de Mayose habló del infinito contable y del infinito incontable.
"El infinito se hace largo, sobre todo al final..."
El grupo 07 presentó en clase los Lenguajes Diagonales (su exposición te la puedes descargar en su blog, o aquí)

Consta de:

1. Introducción ( Cuyo objetivo es estudiar un lenguaje No recursivamente enumerable para utilizarlo como herramienta para caracterizar el caracter recursivo o recursivamente enumerable de otros lenguajes)
2. Como obtener un LNRE (LNRE para hacer referencia a un Lenguaje No Recursivamente Enumerabe)
3. Lenguaje Diagonal LD (Con los elementos nulos de la tabla se construye el LD, el lema del LD y su demostración)

Finalizando la clase con unas tablas generando el LD y unas imágenes de M.C. Escher:


- El viernes 19 Mayo en clase repasamos lo que sabemos a día de hoy, que una MT se puede codificar como una cadena de 1's y 0's, que existe un lenguaje que NO es RE: El lenguaje diagonal.
Dando paso después a la explicación del lenguaje Universal, que es un LRE pero no recursivo (no hay método automático para decidir cuando una computación tendrá éxito)
Se demostró el theorema 8.2 (LU es un lenguaje recursivamente enumerable no recursivo) y la definición 8.5 (Máquina Universal de Turing, MU) Máquina de Turing con una sola cinta, limitada a la izquierda, y con alfabeto {0, 1, B} que acepta el lenguaje LU.
Finalizando la clase con las demostraciones de que Lu No es LR sin lema de bombeo.
Con las reducciones de problemas.
Una reducción es una "traducción".

Resumen de actividades del 7 al 14 de Mayo.

* El grupo se volvió a reunir el miércoles y organizarse otra vez.

* Se repasó un poco la teoria vista en clase.

-Dónde el viernes 9 de Mayo empezó la clase con la demostración del theorema 7.6: Si un lenguaje L y su complementario son LRE, entonces L y su complementarios son lenguajes recursivos, dando paso a la demostración:

Y por culpa de los theoremas 7.5 t 7.6 sólo pueden ocurrir dos cosas si considero L y su complementario:

1. L y su complementario son LR's
2. L es un LRE no R y su complementario es no RE (OJO! Th. 76.)
3. L es no RE y su complementario es LR no R (OJO! Th. 76.)
4. L no es RE y su complementario tampoco

Con lo que se dio por finalizado el tema 7 dándo paso al tema 8: INDECIDIBILIDAD !

¿Porqué es importante que un problema sea decidible? DECIDIBLE: Garantizo respuesta SI/NO.

Se explicó Computable, Lenguaje Universal, Indecible.
Con las buenas noticias de que no hay lema de Bombeo.
Y con las malas noticias de que no hay lema de Bombeo.

-> * <- Ale, nos buscamos la vida, nos inventamos un lenguaje NO Recursivo Enumerable a posta.

Acabando la clase con un entregable sobre Codificación de MT's.

- El lunes 12 de Mayo se vio en clase los convenios para codificar máquinas de Turing, aunque ya se vieron en el tema 6.

1. Sólo son necesarios tres imbolos: 0, 1 y B
2. El estado inicial es q1
3. Es suficiente en un único estado final y será q2.

Con lo que después se resolvió el entregable con las cadenas correspondientes y que su RESULTADO puedes ver aquí (pero has de estar registrado en el aulavirtual.uji.es).

1110101010100110100010101001101001010100111 111010101010011010010010010011010001000010100111 111010010001000100110001010010100111

Resumen de actividades del 30 de Abril al 5 de Mayo.

Un miércoles más nos volvimos a reunir dónde:

* Se planificó la faena a entregar para el 13 de Mayo.
* Se planfificó corrigir el trabajo anterior publicado por el grupo i+2, grupo i-2.
* Se repasó un poco la teoria vista en clase:

- Dónde el viernes 2 de Mayo se volvió a repasar por encima la exposición del lema 7.2: ¿Podemos hacerlo? ¿Lo podemos realizar?¿Para en infinitos pasos? ...

Volviendo al bucle infinito de Glo ...

i=0;
while (x!=v[i] && i < style="text-align: justify;">en el que si está lo que buscamos parará y si no está, no parará nunca, así que... ¿En qué mejorará nuestra vida si nos dicen que el Vector está ordenado? Ya nunca más iré a por el distinto!! jejeje iré a por el menor!

i=0;
while (x!=v[i] && i )
i++;
if (v[i]==x)
return 1; (lo he encontrado)
else
return 0;

Después continuó la clase con la demostración del lema 7.3, el de "<==" (ya que el otro lema está demostrado), del que sacamos la cloncusión de que su objetivo es asegurar que existe un reconocedor de L que siempre para.

-El lunes 5 de Mayo la clase empezó con una exposición de LRE y LR durante unos 20 minutos. De la que se saca la conclusión que LRE (trabaja en pararlelo: Q1 ç Q1 x Q2) es más complicada de construir que la LR que trabaja en serie (Q ç Q1 U Q2).

Se vieron las Operaciones de Clausura:
-> La unión de LR's es LR
-> La unión de LRE'S es LRE'S
-> El complemento de LR es LR
-> El complemento de LRE NO es LRE

Si sabeis contestar SI o NO a una pregunta... ¿Sabéis contestar SI o NO a la pregunta contraria?
Se explicó el lema 7.5 (El complemento de LR es LR) y el lema 7.6:

La intersección de dos LR's es un LR

Esta entrada tratará de demostrar que la familia de los Lenguajes Recursivos (L.R.) es cerrada respecto de la intersección, es decir, que la intersección de dos lenguajes regulares da como resultado un L.R.

Hemos encontrado dos formas de demostrarlo:

• Demostración 1: De Morgan
  

Sean L1 y L2  L.R. . Se sabe por los teoremas 7.4 y 7.5 que los L.R. son cerrados bajo las operaciones de unión y complementación. De esto podemos deducir usando las leyes de De Morgan que la intersección también lo es:

¬(L1 ∪ L2) <=> ¬L1 ∩ ¬L2

Como sabemos que la primera parte de la equivalencia da como resultado un L.R. (por los teoremas antes mencionados), podemos afirmar que la intersección de los complementarios de ambos L.R. también es un L.R. y por tanto, la intersección en una propiedad de clausura para los L.R.

• Demostración 2: Contruyendo la Máquina
  

Sean L1 y L2 , L.R. ⇒ ∃ M1 , M2 | L1 = L(M1), L2 = L(M2) y M1 y M2 siempre paran:

- si x ∈ L1 , M1 acepta la cadena x y si x no pertenece a L1 , M1 rechaza la cadena x. 

- si x ∈ L2 , M2 acepta la cadena x y si x no pertenece a L2 , M2 rechaza la cadena x.

Sea L = L1 ∪ L2 , ¿∃ M | L = L(M) y M siempre para? Sí, construyendo la máquina que se presenta en la figura: 

La construcción es correcta puesto que 

 - si x ∈ L1 AND x ∈ L2 ⇒ x ∈ L1 ∩ L2 = L (M1 y M2 aceptan ⇒ M acepta) 

 - si x no pertenece a L1 OR x no pertenece a L2 ⇒ x no pertenece a L1 ∩ L2 = L (M1 ó M2 rechazan ⇒ M rechaza). 

Por lo tanto, M siempre para y si x ∈ L, M acepta y si x no pertenece a L, M rechaza. 

Resumen de actividades del 23 al 30 de Abril.

Un miércoles más nos volvimos a reunir dónde:

* Se planificó la faena a entregar para el 2 de Mayo.
* Se corrigió el trabajo anterior publicado por el grupo i+1.
* Se repasó un poco la teoria vista en clase:

- Dónde el viernes 25 Abril repasamos en clase la búsqueda lineal através del bucle , aquello de "Bucles infinitos, en los que el problema es el 'problema' " vs "Bucles infintios, en los que el problema es ... el programador!!" pasando tras esto al punto LRE'S y funciones recursivas parciales dónde se vieron las definiciones de LRE y LR.

-(Lenguaje Recursivamente Enumerable) Se dice que L es un Lenguaje Recursivamente enumerable si existe una Máquina de Turing M, tal que:

-> Si x pertenece L, M para y acepta.
-> Si x No.pertenece L, M para y rechaza o M no para.

-(Lenguaje Recursivo) Se dice que L es un Lenguaje Recursivo si existe al menos una Máquina de Turing M, tal que :

-> Si x pertenece L, M para y acepta.
-> Si x No.pertenece L, M para y rechaza.

Se explicó también la Cebolla de Chonsky (Lenguajes, lenguajes malpensaos!)

- Y el lunes 28 Abril debian de exponer el lema 7.1 y 7.2 pero por ciertos motivos no fue así y se pospuso para el viernes, así que el lunes se vieron igualmente estos lemas.

Se empezó la clase con un pequeño recordatorio de la anterior y con la Caracterización de LRs y LREs mediante generadores, ya que dice un bonito lema (el 7.2) que L es un LRE si y sólo si L se puede generar.

Entrados en este punto, se explicó el lema 7.1 dónde Glo nos dejó claro que a ella no le valen como demostración los dibujitos al examen para explicarles estos teorema.

Que se quedan una bellas líneas en el folio y poco más.

Lema 7.1 Para este lema y el siguiente, voy a copiar la descripción de los apuntes y después pasaré al objetivo principal y a qué se debe contestar (+o-) cuando se explica dicho teorema.

Objetivo: construir una MT M2 y ser capaces de asegurar que M2 acepta cualquier cadena de L en un número finito de pasos.

Las preguntas que se debe hacer uno para responder a la pregunta de exámen sobre este lema serían: (a parte de entenderlo y que se pudiera explicar) ¿Es factible la construcción de M1? (Dispongo de los elementos que uso?) y ¿La construcción sirva pra lo que quiero demostrar? ...

Lema 7.2

Objetivo: Construir M1, asegurando que cualquier cadena de L aparece en la cinta de salida en un número finito de pasos.

Para garantizar la construcción de que cualquier cadena de L se imprime en un número finito de pasos en la cinta de salida se utilizaria el generador de pares para "dirigir" el tráfico con lo que ya es factible y cualquier cadena de L es reconocida en un número infinito de pasos.

MT generadora del lenguaje anb2nan

Se trata de una máquina de Turing generadora. Las cadenas generadas son las correspondientes a:

Lenguaje a generar: L={ anb2nan, con n mayor o igual a 0}

Cadenas generadas: abba#aabbbbaa#aaabbbbbbaaa#...#anb2nan

El alfabeto interno es {0,B} y el de salida {a,b,#} (siendo # el separador de cadenas). 

 El funcionamiento es el siguiente:

1. La en la cinta 1 se van introduciendo 0's, uno por cada cadena (sería lo correspondiente a n>=0)
2. Recorre los 0's de la cinta uno y escribe tantas a's como 0's hayan.
3. Vuelve al inicio de la cinta 1 y la recorre anotando tantas b's como 0's hay.
4. Al volver atrás en la cinta 1, vuelve a anotar una b por cada 0.
5. Finalmente la recorre por última vez volviendo a anotar a's
6. Vuelve al comienzo, donde se continua añadiendo 0's a la cinta 1 y continua el proceso

Finalmente, la M.T. queda como sigue: