Reconocer cadenas que los grupos de 0´s son crecientes

Bueno pos esta vez pero que no sea de precedente subo yo unos de los ejercicios propuestos. Comcretamente subo la MT y su modificacion usando multicabezal para poder saber si una cadena del estilo 0010001000010000 los ceros van de forma creciente.

Bueno primero la MT con un solo cabezal y una sol cinta:


Ahora la MT modificada usando dos cabezales:


PD: si os extrañais por lo de q27 no le hagais mucho caso es una marca personal del grupo. Fue despues de la MT de los divisores que terminamos hasta las... orejas y decidimos llamar a estads finales qXX donde XX es un numero alto xD simplemente.

un saludo gente

Conteo Grupo de Ceros

MAQUINA DE TURING CLASICA
Cadena de Entrada: ...B00100100B...
Cadena de Salida: ...B000B...

El cabezal empieza a la izquierda de todo, leyendo un blanco. Empieza a recorrer la cadena poniendo a blanco los ceros que lee, hasta llegar a un 1. Al leer un 1, se va a la derecha hasta encontrar un blanco, se salta dicho blanco y escribe un cero, entonces vuelve hasta el 1, lo pone a blanco y empieza de nuevo con los ceros. En el ultimo paso encuentra un Blanco no un 1, por tanto pone ese blanco a 0 y de ese modo la cadena queda así ...B000B...




MAQUINA DE TURING MULTICABEZAL
Cadena de Entrada: ...B00100100B...
Cadena de Salida: ...B000B...

Empiezan los dos cabezales en el primer blanco, se desplaza el segundo cabezal hasta el final. Una vez alli,empieza a moverse el primer cabezal,cada vez que encuentre un 1, el segundo cabezal pondra un 0 y asi hasta el final.

F(Q0,B,B)= (Q1, {B,Z},{B,R})

F(Q1,B,0)= (Q1, {B,Z},{0,R})

F(Q1,B,1)= (Q1, {B,Z},{1,R})

F(Q1,B,B)= (Q2, {B,R}{B,R})

F(Q2,0,B)=(Q2, {B,R},{B,Z})

F(Q2,1,B)= (Q2, {B,R},{0,R})

F(Q2,B,B)= (Q4, {B,R}{0,R})

Q4 ESTADO FINAL

MT Divisores Multicabezal

Partimos de la misma idea que con la MT simple, salvo que con esta vez no buscaremos la mitad del numero a obener los divisores, ya que eso nos aumentaria considerablemente el numero de simbolos en el alfabeto de la cinta.

Para esta MT partimos con los cabezales puestos en posicion:
Bq0$000q0$q0B

F(q_0, $, $, B)=(q1,{$,L},{$,L},{B,Z})
F(q0, B, 0, B)=(q7,{B,Z},{0,Z},{B,Z})
F(q0, 0, 0, B)=(q0,{0,R},{0,Z},{B,Z})
F(q0, $, 0, B)=(q3,{$,L},{0,Z},{B,Z})
F(q0, 0, $, B)=(q0,{0,R},{$,Z},{B,Z})
F(q1, B, 0, B)=(q1,{0,L},{0,L},{B,Z})
F(q1, B, $, B)=(q2,{B,R},{$,R},{B,Z})
F(q1, 0, 0, B)=(q3,{0,Z},{0,Z},{B,Z})
F(q2, $, $, B)=(q3,{$,L},{$,L},{B,Z})
F(q2, 0, 0, B)=(q2,{0,R},{0,R},{B,Z})
F(q2, $, 0, B)=(q2,{$,Z},{0,R},{B,Z})
F(q3, B, 0, B)=(q0,{B,R},{0,Z},{B,Z})
F(q3, B, $, B)=(q4,{B,R},{$,R},{B,Z})
F(q3, 0, 0, B)=(q3,{0,L},{0,L},{B,Z})
F(q3, 0, $, B)=(q5,{0,L},{$,Z},{B,Z})
F(q4, $, $, B)=(q5,{$,L},{$,Z},{1,R})
F(q4, 0, 0, B)=(q4,{0,R},{0,R},{0,R})
F(q4, $, 0, B)=(q4,{$,Z},{0,R},{B,Z})
F(q5, B, 0, B)=(q6,{B,R},{$,R},{B,Z})
F(q5, 0, $, B)=(q5,{0,L},{$,Z},{B,Z})
F(q6, 0, 0, B)=(q6,{0,Z},{0,R},{B,Z})
F(q6, 0, $, B)=(q0,{B,R},{$,Z},{B,Z})
F(q7)=Estado Final

Dentro de poco publicaremos ese tocho de arriba como tabla tambien.

MT Divisores

Objetivo: Dado un número, hallar sus divisores

Entrada: ...$0000$...

Salida: ...$0000$00...

La idea básica es leer el número(empezando con el cabezal a la izquierda del todo, por tanto lo primero que encontrará será un $), encontrar la mitad (marcarla como blancos). Con esto conseguimos el máximo divisor, por tanto lo copiamos al principio de la cadena y vamos comparando si es o no divisor. En caso de serlo, copiamos el número(el de mas a la izquierda '00'$00BB$B...) a la derecha, y ponemos un 1 para separalo del siguiente divisor(..00$00BB$001...) y le borramos un 0 desde la izquierda al candidato (..0$00BB$001...). En caso de que no sea divisor borramos el cero de la más a la izquierda y empezamos de nuevo(..0$00BB$...)

Este ejercicio lo hemos hecho a lo largo de la semana, quedando por las mañanas el viernes 11, y lunes,martes y miercoles de esta semana.
Problemas... un monton xDD, desde borrar todo y tener que empezar desde el principio... hasta si marcar o no un $, pero esto ya lo pondra david en una entrada lol.

MT División

Objetivo: Dados dos enteros n y m, obtener resto$cociente.

Entrada: ...B00000001000B...

Salida: ...B0$00B

MT Multiplicación

Objetivo: Dados dos enteros n y m, obtener n x m.

Entrada: ...B001000B...

Salida: ...BBBBBBB000000B...

Maquina Turing N cuadrado

Objetivo: Dados dos enteros n y m, obtener n x m.

Entrada: ...B00100B...

Salida: ...BBBBBBB0000B.