Tarea 6 y ultima

a)¿Cómo se podría construir un generador de todos los códigos de Máquinas de Turnig sintácticamente correctos?


Para construir un generador de todos los codigos necesitamos un generador canonico del alfabeto {0,1,B} y un automata reconocedor de MT´s que sabemos que existe ya que lo hemos dado en clase.

Para empezar el generador ira sacando cadenas w que le pasaremos al reconocedor de MT´s que nos dira si la cadena pertence a una MT(como hemos visto en clase las maquinas de Turing se pueden codificar mediante 0,s y 1,s).

Las cadenas w pueden ser por ejemplo {0},{1010},{00010}...

El problema es que aunque podamos saber el codigo de infinitas MT´s siempre habra mas maquinas de Turing por tanto nunca tendremos suficientes codigos para todas las maquinas.

b)Pues creemos que como se ha demostrado en el primer apartado nunca podremos conseguir suficientes maquinas porque siempre podremos tener una cadena mas y por tanto siempre necesitamos mas maquinas.Asique nosotros nos decidimos por la respuesta 2 (La de que no tiene bastantes maquinas)





Por lo tanto no podremos resolver todos los problemas siempre habra alguno que no se pueda.

Demostracion de que la interseccion de dos LRE´S es un LRE

Sean L1 y L2 dos lenguajes regulares enumerables.

Sea L el lenguaje interseccion entre L1 y L2.

Las clases Lre de los lenguajes recursivamente enumerables son cerradas respecto a la intersección.

X es una cadena que pertenece al lenguaje L.

Tenemos M1 que sabemos que es una maquina que acepta las cadenas del lenguaje L1.

Tenemos M2 que sabemos que es una maquina que acepta las cadenas del lenguaje L2.

Queremos saber si la interseccion de dos LRE´S tambien va a ser un LRE.

Con las maquinas M1 y M2 podemos construir una maquina M que nos diga si va a reconocer a una cadena X del lenguaje L.

Funcionamiento de M:

Le pasamos una cadena X a la maquina M.Para que la maquina acepte esa cadena la cadena X tiene que pertenecer al lenguaje L1 , lo acepta la maquina M1,y tambien al lenguaje L2, lo acepta la maquina M2. Cuando haya aceptado las dos maquinas entonces podremos decir que la acepta la maquina M y por lo tanto pertenecera al lenguaje L que es la interseccion de los lenguajes L1 y L2.

Sabemos por definicion que la interseccion de dos LRE´S son cerrados, por lo que sabemos que

X pertenece al lenguaje L que lo acepta la maquina M y que L es un LRE.

Resumen semanal ( 28 de abril - 5 de mayo)

4ª semana de trabajo:

Esta semana fue todo muy rápido ya que había fiesta de por medio; quedamos el martes 29 sobre las 16h, como siempre, y maduramos las ideas que teníamos sobre la MT a realizar.
Elegimos multicinta porque... hasta este trabajo todas las MT's que habíamos hecho eran multicabezal.
Y empezamos con la maquinita, que no nos dió excesivos problemas, pero un ligero dolor de cabeza que me duró todo el día, es que pensar tanto es malo Gloria ( por si lo lees ).
Pero allí estaba Roberto Turing, así le llaman ahora, jajaja, esa almendra que tiene le funciona bien al tio. Acabó por encontrar el error que teníamos y parece que va bene, y si tuto va bene...avanti con...
Sabemos que tenemos trabajo que va con retraso, por ejemplo nos falta corregir las MT's de otros grupos, pero todo a su debido tiempo, que no solo existen las máquinas de turing... ;-)

Resumen Semanal ( 21 - 28 de abril)

3ª semana de trabajos forzados:

El martes 22 quedamos de 16 - 18h y pensamos la idea para realizar las máquinas que contaban bloques de 0's ( una simple y la otra multicabezal ), fue bastante bien porque todo salió a la primera. Ya que nos veiamos con ganas continuamos con las MT's para saber si los bloques de 0's estan ordenados, pensamos antes la idea para el multicabezal pero no dábamos con la MT simple, así que mejor dejarlo para el dia siguiente.
El miercoles apareció Roberto con ese arte y con ese cairel, ese cairel español, jajaja. Se le ocurrió a él la MT que faltaba, para que engañarnos (el que tiene cabeza ... tiene cabeza) y asunto finiquitado. Durante el transcurso de la semana colgamos las MT's en este maravilloso blog y c'est fini.

Mañas, ... si te hubiera conocido antes, ;-)

Generador de cadenas del tipo AnB2nAn

Es multicinta , en la primera cinta ira poniendo 0´s y en la segunda ira escribiendo las cadenas que genera empezando por la cadena vacia.