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.