Resumen semana 26/5 al 30/5

Esta semana hemos tenido que realizar la exposición de "El problema de correspondencia de Post".No ha sido una cosa muy complicada porque aparte no había mucho que exponer y además los ejercicios del SCP son bastante sencillos.Los que si que parecían un poco mas complicados son los del SCPM, que tenían un poco más de miga.
Aparte de eso nos hemos dedicado a preparar la ultima tarea y a subirla al blog.Por último nos quedará corregir las tareas 5 y 6 pero eso lo dejamos para el viernes.

Generador de todas las Mt's(última tarea)

a)En principio nuestra idea para este apartado consistiría en colocar un generador canónico que se encargaría de ir sacando cadenas de 0's y 1's. Estas cadenas se le pasarían a una M1 tal que aceptaría las cadenas en caso de ser Mt's codificadas y que las rechazaría en caso de no ser Mt's codificadas. De esta forma las cadenas que fuesen Mt's se irían escribiendo en una cinta de salida. La idea sería algo parecido al siguiente dibujo:


b)Respecto apartado b, suponemos que es la segunda respuesta. Pensamos que es esa porque aunque generemos infinitas máquinas de turing siempre quedará una que aun no se ha generado.

Resumen semanal 19/5 al 23/5

Esta semana la hemos dedicado a preparar el tema que teníamos que exponer en clase.En principio lo teníamos que exponer el viernes pero luego por unos ajustes que hubo en clase se ha atrasado al día 26 (lunes) de la semana que viene.El tema a exponer es el Sistema de correspondencia de Post. Pedro se encargará de la parte teórica y yo me encargaré de resolver el ejercicio 13.

Correcciones tarea 3 y tarea 4

Hemos dejado un comentario en las entradas de las respectivas tareas de cada grupo. La tarea 3 del grupo 10 estaba bastante bien solo producia un par de fallos. Por último la tarea 4 del grupo 6 también funcionaba correctamente pero le faltaba generar la cadena con n=0.

Resumen semanal (12/05 a 16/05)

Esta semana la hemos dedicado a la corrección de las tareas de los otros grupos.
Así, el lunes hemos estado corrigiendo las tareas 3 del grupo 10 y la 4 del grupo 6 en las que estuvimos alrededor de las 2 h. para corregirlas.La tarea del grupo 10 estaba muy bien comentada lo que facilita bastante la faena. A la tarea del grupo 6 le faltaría comentarse un poco más.
Luego,el jueves hemos estado corrigiendo la tarea 2 del grupo 9, esta tarea tenía errores más graves que las de los otros grupos por lo que aun no la hemos acabado de corregirla, así en cuanto el grupo 9 nos responda el comentario que le dejamos en su post, seguiremos con la corrección. Por último decir que podrían comentar algo más las tareas pues no tienen ningún comentario.
Tanto las correcciones de unos como de otros han sido publicadas como opiniones en las entradas de los correspondientes blogs de cada grupo.

Resumen semanal 5/5 al 9/5

Esta semana la hemos dedicado a preparar la tarea de "la intersección de dos LR's es otro LR".Pensamos que ha sido una tarea bastante sencilla, pues si se tomaba como ejemplo la explicación de la unión de dos LR's se podía obtener facilmente la intersección de dos LR's.
Después de dejar la tarea preparada yo mismo me encargué hacer el dibujito que la explica y de subirla al blog.
Hemos empezado a corregir ejercicios de nuestros compañeros pero esto lo acabaremos la semana que viene.

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

Demostración:
Si L1 es un LR→∃ M1|L1=L(M1) y M1 siempre para.
Si L2 es un LR→∃ M2|L2=L(M2) y M2 siempre para.

Entonces si L=L1∩L2={x | xєL1 Λ xєL2}
¿Existe M|L=L(M) y M siempre para? SI que existe, ya que:
M para y acepta si xєL1 Λ xєL2 →xєL1∩L2

M para y rechaza si x∉L1 v x∉L2 →x∉L1∩L2

POR LO TANTO L1∩L2 ES LR.

Mt generadora de cadenas a^nb^2na^n, con n mayor o igual a 0

Mt generadora(con multicinta)

Hemos optado por una MT multicinta porque de esta forma podemos utilizar una cinta de trabajo, donde realizaremos las operaciones pertinentes para ir generando las cadenas y otra cinta que será la de salida y que es donde iremos escribiendo todas las cadenas que vamos generando.
Idea: En principio partimos de dos cintas que solo contienen blancos. En la cinta de trabajo iremos escribiendo ceros y por cada cero que escribimos en la cinta de trabajo escribimos un a^nb^2na^n siendo n igual al número de ceros que hay en la cinta de trabajo.Las cadenas que vamos escribiendo en la cinta de salida están separadas por #.
El funcionamiento de la MT es bastante sencillo en q0 y q1 se escribe en la cinta de salida la cadena vacía.Luego se escribe el primer cero en la cinta de trabajo y empiezan las operaciones.Primero se sitúa el cabezal al comienzo de la cinta (q2). Después se recorre la cinta de trabajo hacia la derecha y se escriben en la cinta de salida el número de a's en proporción al de ceros de la cinta de trabajo(q3).Luego se recorre hacia la izquierda y se escriben las b's (q4, q5).Por último se vuelve a recorrer la cinta de trabajo hacia la derecha y se vuelve a escribir las a's(q6).Para poder generar más cadenas se tiene que incrementar el número de ceros de la cinta de trabajo por eso en q1 se incrementa en uno el número de ceros.Al poner este cero el cabezal no se queda en el principio de la cadena por eso en q2 lo que hacemos es situarlo al principio de la cadena de 0's para poder comenzar a hacer el recorrido de izquierda a derecha y por lo tanto la escritura de nuevas cadenas.

Resumen semana 28/4 al 2/5

Durante el comienzo de esta semana colgamos las tareas que teníamos que entregar para el día 28 en el blog.Después nos pusimos manos a la obra con la tarea que nos quedaba pendiente para el día 2 de mayo.El martes acabamos con esta tarea ya que no nos supuso mucho calentamiento de cabeza. Ahora solo nos falta subirla al blog y comentarla un poco para que se sepa cual es la idea de nuestro diseño.

Resumen semana 21/4 al 25/4

Esta semana hemos quedado el martes para empezar con las máquinas que teníamos que entregar el 28 de abril. Ese mismo día las acabamos y por lo tanto dedicamos el jueves para probarlas un poco y ver si tenían algún fallo. Al ver que todo iva bien y que todo parecía correcto las dejamos preparadas para subirlas al blog.Por último las subimos al blog el día 28 que era el día límite para subirlas.
Como conclusión tenemos que decir que las MT's que se propusieron para el día 28 de abril nos parecieron bastante más sencillas que las que hicimos en tareas anteriores.

MT's para cadenas que incrementan el número de 0's

Importante: Las MT's solo aceptarán cadenas del tipo 00100100010000. Es decir, solo cadenas que comiencen y acaben por 0 y que solo tengan un 1 como separador. Por tanto, las cadenas del tipo: 1001000, 0010001,001000100,000110000, no serán aceptadas.

MT normal(Con marcaje de símbolos)

Inicialmente el cabezal se encuentra en el primer 0.
Idea:La idea es ir comparando los bloques de 0's mediante el marcaje de símbolos. Así pues vamos marcando un cero antes del separador y un cero después del separador, hasta que no hay más ceros por marcar en alguna de las partes del separador.Si nos quedamos sin ceros que marcar en la parte derecha del separador entonces la cadena no se acepta porque el número de ceros es decreciente. Si por el contrario nos quedamos sin ceros que marcar en las dos partes o en la parte derecha del marcador la cadena si que se aceptará porque el numero de ceros no se reduce o es creciente.

MT modificada(multicabezal)

Hemos elegido una MT multicabezal porque es la modificación que nos da una solución mas rápida a la hora de comparar el tamaño de cada bloque de 0´s.
Inicialmente el primer cabezal esta en el primer 0 y el segundo cabezal esta después del primer separador, es decir, después del primer 1.
Idea: La idea es ir recorriendo la cadena de izquierda a derecha comparando el número de 0's que lee el primer cabezal respecto del segundo.Si el número de 0's que lee el primer cabezal es igual que el del segundo o menor la cadena se aceptará, pero si es mayor entonces la cadena no se aceptará.

MT's contadoras de bloques de 0's

Importante:Las dos máquinas solo aceptan cadenas del tipo 00100100100, es decir, bloques de 0's separados por un 1 solo. Además las cadenas empezarán y terminarán con un 0. Las MT's no aceptarán cadenas del tipo: 100100, 001100100, 001001 ...

MT normal

El cabezal se encuentra inicialmente encima del primer 0.
Idea:La idea de esta máquina es que vallamos recorriendo la cadena de izquierda a derecha y por cada bloque de ceros que vamos encontrando nos vamos al final de la cadena y escribimos un cero después del primer blanco que encontramos. Cada bloque de 0's que queda contado se borra de la cadena. Los 0's tienen que estar separados siempre por un 1, menos en ultimo bloque de 0's que tiene un blanco detrás y no un 1.

MT modificada (multicinta)

Hemos elegido una máquina multicinta de 2 cintas porque en este caso resulta más fácil trabajar con una cinta y ir escribiendo los resultados en otra cinta.
Idea:El funcionamiento en este caso es sencillo, le pasamos una cadena en la cinta de entrada y vamos escribiendo un 0 en la cinta de salida por cada bloque de 0's que vamos encontrando en la cinta de entrada.Los cabezales inicialmente están encima del primer 0 en la cinta de entrada y encima de un blanco en la cinta de salida.

Resumen semana 14/4 al 18/4

Quedamos el martes y el jueves y corregimos las MT's de nuestros compañeros del grupo 7. Primero probamos las MT's y al ver que tenían algunos fallos nos pusimos manos a la obra. Cogimos el estado donde se producía el fallo y fuimos arreglando transiciones hasta que las MT's funcionasen correctamente.
Cuando conseguimos que las máquinas hiciesen lo que se les pedía las subimos a nuestro blog y dejamos marcado que es lo que habíamos modificado.

Correcciones de las MT's del grupo07

MT para n-cuadrado.
En esta MT nosotros cambiaríamos en el estado q2, cuando encuentre un cero hará la transición a qi0 , escribirá una X y moverá el cabezal a la derecha, y no a la izquierda como pone en la tabla del blog del grupo07.Si mueve a la izquierda hay un momento en que la máquina deja de funcionar.
La tabla quedaría como en la imagen, la única transición que se ha corregido es la que está en rojo.

MT para multiplicación.
En esta MT hemos añadido o modificado las transiciones que están en rojo y hemos añadido el estado qi6.

MT para división.
En esta MT estamos intentando encontrar la forma de corregirla sin cambiar mucho la tabla pero parece algo complicado.Cuando dividimos 5 entre 2 llega un momento en que se pasa al estado q2 y se esta leyendo un 1, ese caso no se contempla en la tabla por lo que la máquina no sigue funcionando.Para que siga funcionando le hemos añadido una serie de estados que creemos que hacen que la máquina devuelva la cadena que se pedía.

Resumen semanal (07/04 a 13/04)

El trabajo semanal ha estado distribuido de la siguiente forma:

-Lunes: El lunes estuvimos analizando las ideas acerca de como realizar la Mt de divisores, y empezamos a construir .Este día fue uno de los más relajados ya que casi no hicimos nada.

-Martes:Estuvimos desarrollando la MT de divisores sin modificaciones, fue bastante costoso pues es una MT que requiere muchos estados tal y como se puede observar en nuestra tabla de transiciones. Después del duro trabajo realizado ese día parecía que la MT funcionaba correctamente, aunque faltaba revisarla otra vez antes de colgarla en el blog.

-Jueves: El jueves volvimos a quedar para realizar la MT con multicinta. En principio queríamos hacerla con 3 cintas, pero como nos surgieron algunos problemas que no supimos solucionar optamos por la multicinta de dos cintas. En esta máquina tendríamos una cinta de entrada y de trabajo y otra cinta de salida donde escribiríamos los divisores. El día fue bastante duro por los problemas surgidos con la MT de 3 cintas, aunque al final conseguimos realizar la máquina y lo mejor es que parecía que funcionaba bastante bien.

-Domingo: El domingo le dimos los últimos retoques a las MT´s y las subimos al blog.

Esto ha sido todo por esta semana.

MT división, n-cuadrado y multiplicación

En todas las MT´s el cabezal se encuentra en el primer cero.

MT para multiplicación

Cadena de entrada:B0^n10^mB
Cadena de salida:B0^nxmB

MT para n-cuadrado

Cadena de entrada:B0^nB
Cadena de salida:B0^n^2B

MT para la división

Cadena de entrada:B0^n10^mB
Cadena de salida:B0^n%m10^n/mB

MT divisores N con multicinta

Se le pasan dos cadenas 1 la de trabajo que sera del tipo B0^NB y otra la de salida que solo tiene blancos.El cabezal esta en el primer cero en la primera cadena.El formato de la cadena de salida es Bdiv^N1B

Divisores con MT normal

MT para los divisores de N

Al inicio el cabezal se encuentra en el primer cero.
Cadena de entrada:B0^NB
Ejemplo:B0000B

Cadena de salida:B0^N$divN1
Ejemplo:B0000$010010000B