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:

M.T. multicinta reconocedora de bloques de 0's ordenados ascendentemente

Recibe una cadena de entrada de bloques de 0's separados por 1's, devuelve en la cinta 2 el número de 0's más alto, dejando la cadena original intacta.

Cadena de entrada: B00100010000B

Cadena de salida:    B0000B (cinta 2)

Se ha elegido el diseño multicinta frente al multicabezal porque el segundo requeriría tantos cabezales como bloques de 0's hayan en la cadena para conseguir una buena eficiencia y como este dato no se conoce de antemano, se ha elegido multicinta.

Se han usado 2 cintas. En la primera se encontraría la cadena de entrada, mientras que la segunda se usará para guardar el número de 0's del ultimo bloque leído. Su funcionamiento es el siguiente:

1. Recorre la cadena de entrada anotando los 0's encontrados en la segunda cinta hasta encontrar un 1 y rebobina la cinta 2.
2. Si se encuentra en una posición 1,0 o B,0 la rechaza o bien borra la cinta 2 (dependiendo de la solucion escogida)
3. Si se encuentra en la posicion B,B, acaba satisfactoriamente.

El alfabeto empleado ha sido {0,1,B}. Se asume que la posición inicial en la cinta 1 es el primer símbolo de la cadena de entrada. La posición de la segunda cinta es indiferente. Se han implementado 2 posibles soluciones, una que cuando encuentra una cadena no valida, simplemente acaba y otra que borra la cinta 2.

M.T. simple reconocedora de bloques de 0's ordenados ascendentemente

Al recibir una cadena de entrada de bloques de 0's separados por 1's, debe aceptar las cadenas que sus bloques de 0's estén ordenados de forma ascendente, es decir, aceptar las cadenas tipo ...B0010010000100000B... y rechazar cadenas como ...B001000100100000B...

Cadena de entrada: B0010001000B

Cadena de salida:    B0010001000B (cadena aceptada)

Cadena de salida:    BBBBBBBBBBBB (cadena rechazada)

 El funcionamiento es el siguiente:

1. Recorre la cadena de entrada marcando los primeros 0's de cada bloque hasta llegar al final, marcando siempre el primero que encuentra con el simbolo Y. (q0, q1, q2)
2. Vuelve atrás hasta el símbolo Y y repite el paso 1.  (q3)
3. Si en el primer marcaje (q0) encuentra un 1, sigue al siguiente bloque, si encuentra un B, la cadena es válida y la recorre para cambiar todos los X e Y por 0's (q4)
4. Si en el segundo marcaje o sucesivos (q1) encuentra un 1 o un B, la cadena no es válida y la recorre borrando todos los símbolos (q5, q6)

En esta M.T. se ha usado el alfabeto {0,1,B,X,Y}. Se asume que la posición inicial es el primer símbolo de la cadena de entrada. Si tan sólo debiera rechazar la cadena y no dejarla a 0's se pueden comentar todos los estados q5 y q6 y f(q1,1), f(q1,B).

Resumen de actividades del 16 al 23 de Abril.

De nuevo nos reunimos el miércoles donde:

* Se planificó la faena a entregar para el 28 de Abril.
* Se decidió la demostración que realizariamos.
* Se repasó un poco lo visto en teoría:

-Dónde el viernes 18 se vieron 2 versiones de Generadores Canónicos (0+1)* , en las que , por ejemplo, dada la siguiente entrada ...B000011011B y sumándole un 1 en binario, obtuviese esta salida: ...B000011100B con su correspondiente acarreo ya introducido, por lo que la segunda versión vista en clase era más eficiente ya que desde la posición inicial, si encontraba un 1 lo convertia en 0, si encuentra un 0 se deja el acarreo y lo pasa a 1. En estado q2 se llega hasta el final y ya estaba en posición correcta para empezar a escribir en la salida, en estado q3 va copiando cada uno de los simbolos de la cadena que tengo en la cinta de salida.

-Hubieron un par de entregables:
* Un Generador Canónico (0+1+2)*, en el que se le sumaba 1 en base 3 y cuando llevaba acarreo el 0 lo convertia en 1 y el 1 en un 2. Un ejemplo, ...B00121012B debia producir la siguiente salida: ...B00121020B

* Y el otro entregable se trataba de la primera toma de contacto de un Sistema Formal...
El sistema axiomático MIU del libro:
“Gödel, Escher y Bach: un Eterno y Grácil Bucle”, Douglas R. Hofstadter. Tusquets editores.
El sistema es utilizado por el autor para explicar los sistemas formales planteando al lector
varios juegos y acertijos sobre él. El lenguaje sobre el que se define el sistema axiom´atico es el
lenguaje universal sobre el alfabero {M, I,U}.
Para más info:
http://www.satd.uma.es/a_valverde/Logica/complementos/EjemploMIU.pdf

-El lunes se cerraba el Tema 6 de teoría y se iniciaba el Tema 7 (Computabilidad), con breves explicaciones sobre grandes matemáticos culpables de que estemos estudiando TALF y muchas otras cosas. "Descubrir un método general para determinar si una fórmula de lógica formal es cierta o es falsa." by Hilbert, "El conjunto de los conjuntos que pertenecen a sí mismos ¿pertenece a sí mismo?." by Rusell y la explicación de su paradoja, etc, etc.
Finalizando con una recopilación de interesantes libros sobre estos temas. (El tio Petros y la Conjetura de Golbach está muy ameno)

Para más info:
http://aulavirtual.uji.es/file.php/3246/entscheidungsproblem.pdf

IA y el test de Turing

La búsqueda de un ingenio que "volara artificialmente" tuvo éxito cuando los hermanos Wright, entre otros, dejaron de imitar a los pájaros y comprendieron los principios de la aerodinámica. Los textos de ingeniería aeronaútica no definen el objetivo de su campo como la construcción de "máquinas que vuelen como palomas de forma que puedan incluso confundir a otras palomas"

Peter Norvig, en su libro Inteligencia Artificial

M.T. multicinta para calcular bloques de 0's

Funciona del mismo modo que la M.T. anterior. Recibiendo una cadena de entrada de bloques de 0's separados por 1's, devuelve el número de bloques que existen en la cadena de entrada. 

Cadena de entrada: B0010001000B

Cadena de salida:    B000B

Se ha elegido el diseño multicinta frente al multicabezal porque el segundo requiere estados para posicionarse en el lugar donde se van a escribir los resultados y también porque en este caso, el diseño multicinta, no requiere copiar ninguna cadena en la cinta extra, con el consiguiente ahorro de estados que ello conlleva. 

Para ello se han usado esta vez 2 cintas. En la primera se encontraría la cadena de entrada, mientras que la segunda se usará para guardar el número de bloques que va encontrando y por tanto es la de salida. Funciona de la siguiente manera:

1. Recorre la cadena de entrada borrando los 0's hasta encontrar un 1 que también borra.
2. En ese momento si la cadena se encuentra en [0, B] marca un 0 en la cinta dos. Si se encuentra en [B,B] también marca un 0 y acaba, puesto que se encuentra al final
3. Repetición de lo anterior.

En esta M.T. también se ha usado el alfabeto {0,1,B}. Se asume que la posición inicial en la cinta 1 es el primer símbolo de la cadena de entrada. La posición de la segunda cinta es indiferente. También recoge la posibilidad de que acepte 1's al principio y al final, con lo que si no se quiere que lo haga, se deberían eliminar las funciones f(q0,1,B) y f(q2,B,B).

Descarta las cadenas con varios 1's consecutivos (B00110010B), aunque tan sólo habría que añadir el estado (q2,1,B) para que también las reconociera.

M.T. simple para calcular bloques de 0's

Esta M.T. calcula algo parecido a lo que sería en C la variable "argc". Se encarga de devolver la cantidad de bloques de 0's que hay en la entrada, separados entre ellos por el símbolo 1. Así, un ejemplo sería:

Cadena de entrada:  B0010001000B

Cadena de salida:     B000B

En la M.T. construida, se han tenido en cuenta dos casos más. La posibilidad de que se encuentre un 1 al principio o un 1 al final:

B1001000100B

B0010001001B

En caso de no considerarse cadenas válidas, tan sólo debería eliminarseel estado q0 para que no acepte el 1 inicial y la f(q5,1) para que no acepte el 1 final.

El funcionamiento básico del autómata es el siguiente:

1. Borra todos los 0's hasta encontrarse un 1 (BBB10001000B)
2. Borra ese 1 y se mueve al final (BBBB0001000Bq3B)
3. Una vez encontrado un B salta a la derecha y anota un 0 (BBBB0001000B0B)
4. Vuelve y repite la operación hasta encontrar un blanco después de tachar 0's (BBBBBBBBBBBB000B)

Como se puede ver, el alfabeto utilizado vuelve a ser {0,1,B}. Además suponemos que la posición inicial del autómata se sitúa en el primer símbolo de la cadena de entrada.

EDITADO: Se ha modificado la M.T. para que acepte cadenas B00011100B. Si no se debieran aceptar, tan sólo habría que eliminar el estado f(q7,1)

Resumen de actividades del 9 al 16 de Abril.

Resumen de actividades. Grupo 10. Del 9 al 16 de Abril.

El grupo se reunió de nuevo el miércoles, donde:

* Se corrigieron las M.T. de la división, n^2 y multiplicación del grupo 9
* Se re-estructuró el grupo para abarcar toda la faena
* Se repasaron los temas expuestos en clase teoría:

- Demostración de que las M.T. Multicinta y multicabezal tienen el mismo poder computacional que las M.T. estándar realizada por el grupo 1

- Demostración de la equivalencia en cuanto a poder computacional entre las M.T. Deterministas y las No Deterministas realizada por el grupo 6

- El generador Canónico. Dado el alfabeto {a1, a2, ... aR} genera todas las combianciones de esos K simbolos en orden canónico.

- El Generador de Pares. Se llama Generador de Pares a la Máquina de Turing capaz de generar todos los pares (i, j) ' N × N, G(M) = {(i, j) | i, j ' N}.

Test de Turing

Turing en 1950 propuso una prueba que se conoce como el ‘test de Turing’, el cual se basa en la idea siguiente: si una persona se comunica sólo a través de un terminal con otras dos partes, que están escondidas, y no se puede discriminar a través de preguntas cuál de ambas partes es una persona y cuál es un ordenador, entonces no se puede negar que la máquina muestra la cualidad que, en las personas, se llama ‘inteligencia’. Tal procedimiento tiene la ventaja de no tener que definir lo que es la inteligencia. Turing creía firmemente que máquinas que piensen llegarían a existir y predijo que hacia el año 2000 una máquina jugaría al ‘juego de imitación’, como él llamó al test, de manera que un interrogador medio no tendría más del 70 por 100 de posibilidades de efectuar la identificación correcta tras cinco minutos de preguntas.

La Máquina de Turing 2,3 es Universal

Un chaval de 20 años, estudiante de electrónica y computación de la universidad de Birmingham se ha embolsado 25000$ por demostrar que la Máquina de Turing 2,3 es universal. 

¿Qué quiere decir eso?. Pues es bien simple. Quiere decir que se puede emular cualquier cálculo computable con una M.T. con dos estados y tres símbolos. 

Yo lo he flipado bastante con la demostración. Y más porque me siento incapaz de hacer siquiera una para la suma ;-)

Fuente: Neofronteras

Demostración (pdf): Demostración

MT divisores (Multicinta)

Esta M.T. calcula los divisores de un número. La diferencia con la anterior es que esta M.T. es multicinta. Usa 3 cintas, guardando en la primera el número, en la segunda los candidatos a divisores desde n/2 y en la tercera los que son divisores. El alfabeto usado sigue siendo {0,1,B}.

Formato de entrada: B000000000B (cinta 1)

Formato de salida   : B00010B  (cinta 3)

Y la definición queda así:

Simulador M.T. en perl

Es un pequeño programa que tan sólo reconoce las M.T. simples deterministas y tiene un formato de entrada de las definiciones de estados un poco complejo, pero al menos funciona bien... y en modo texto ;-P

Debería ser fácil de modificar para aceptar multicinta, multicabezal, cintas con sectores múltiples y demás, pero de momento lo dejo así. Si más adelante alguien se anima podría modificarlo por el bien de la salud mental del diseñador de M.T. ;-P

Turing Machine 0.1v 

Uso:

      Turing Machine <archivo> [cadena de entrada]

Descarga: AQUI

M.T. para calcular los divisores (OK)

Esta es la buena. Para solucionar el problema que teníamos de la cantidad de estados de la M.T. se ha programado un pequeño script en perl para simular máquinas de Turing simples. Hemos cambiado los formatos de entrada y salida de acuerdo a lo que se pedía y el resultado parece hacer sido satisfactorio. El alfabeto se mantiene el mismo {0,1,B} y ahora los 0's se toman como indicadores del número y los 1's como separadores:

Formato de entrada: B000000000B

Formato de salida   : B00010B

Por cierto, la otra M.T. definitivamente estaba mal, pero la dejo por si tenéis curiosidad por saber en que fallaba. Así ha quedado esta nueva versión:

Resumen de actividades del 2 al 9 de Abril (*)

Esta semana ha sido más bien tranquilita porque no había ninguna tarea pendiente... a principios de semana debíamos colgar en el blog del AV las soluciones para las MTs de la multiplicación, división y n^2.

En lo referente a las clases de teoría, el viernes 4 lo pasamos viendo cómo crear y configurar el nuevo blog y todavía hubo tiempo para que 'la profe de talf' nos mandase una nueva tarea, hallar una MT "clásica" y otra MT "modificada" (en nuestro caso una multicinta) que, dado un entero, devolviera sus divisores.
El lunes, después de dar un breve repasito a lo que habíamos dado de teoría hasta el momento (definición del modelo de MT, técnicas para la construcción de MTs y MTs modificadas) empezamos a ver la MT como 'Generador' de lenguajes.
Hasta el momento habíamos tratado a la MT como un reconocedor de lenguajes a la que le pasábamos una cadena de entrada y obteníamos una cadena de salida, dependiendo de si la cadena de entrada pertenecía o no al lenguaje reconocido por la máquina. Ahora además, podemos ver a la MT como un generador de lenguajes donde no existe una cadena de entrada pero sí una de salida, en la que se encuentran todas las cadenas del lenguaje generado. Como ejemplo vimos el generador de 0^n1^n, donde la cadena de salida sería de la forma ##01#0011#000111#00001111#... (utilizando el carácter # para separar cadenas).
Por último vimos las características físicas de una MT generadora. Una MT generadora es una MT multicinta con una cinta especial de salida, inicialmente en blanco en la que no se pueden reescribir símbolos, pues el movimiento del cabezal está restringido a la derecha.

(*) Nuestros resúmenes semanales se harán de miércoles a miércoles pues quedamos este día para reunirnos los miembros del grupo.

Programación a bajo nivel

"La programación en bajo nivel es buena para el alma del programador"

-- John Carmack

M.T. para calcular los divisores

Esta M.T. la hemos realizado al igual que las anteriores con un alfabeto {0,1,B}. Ha llegado un momento en que la cantidad de estados nos superaban, así que la vamos a dejar a modo de curiosidad y teniendo en cuenta que ni siquiera está repasada para ver si funciona bien en todos los casos. Así que si os da por comprobarla, ¡informad de fallos y se os agradecerá!.

Formato de entrada: B111111111B

Formato de salida:     B11101B

El 0 se usa de separador y el 1 para marcar los números. La B además se usa para marcar pares (Glub!).

Alan Turing

He encontrado un artículo muy interesante acerca de la vida de Alan Turing. Debería de ser de obligada lectura, ya que es simple, conciso e incluye casi todos los conceptos básicos que se necesitan saber sobre él. Para que veáis un poco de que va el tema os copio algunos párrafos:

En 1936, por ejemplo, publicó su famoso artículo “Los números computables” en el cual resolvía el problema de decisión, demostrando que era insoluble, e introducía por primera vez el concepto de Máquina Universal. En su artículo Turing nunca llega a hablar de una máquina física sino que su máquina es más bien un modelo matemático; pero el paso siguiente, llevar esas ideas a la práctica, es un concepto presente a lo largo de todo el ensayo.

(...)

Para hacernos una idea de la importancia de este artículo no debemos olvidar que las máquinas más complejas construidas hasta ese año, 1936, eran calculadoras muy básicas que sólo podían llevar a cabo cálculos muy simples, poco más que ábacos mecánicos. Y un joven matemático (Turing tenía veinticuatro años cuando público el artículo) planteaba no ya una máquina capaz de realizar cálculos complejos sino capaz de realizar todos los cálculos. La Máquina Universal de Turing podía resolver cualquier problema que pudiese ser expresado mediante un algoritmo matemático. Cualquier cálculo que pueda realizar un ordenador actual puede ser resuelto también por una máquina de Turing.

(...)

Turing construyó una máquina de cálculo para usarla en la ruptura de los códigos Enigma a la que llamo Bomba en honor a Rejewski. La lucha de los criptoanalistas de Bletchley Park contra la máquina Enigma alemana duró prácticamente toda la guerra. Los alemanes iban mejorando los modelos añadiéndole rotores y perfeccionando el método de encriptación mientras los ingleses rompían la mayoría de los códigos y, casi más difícil, intentaban que los alemanes no se percataran de que sus mensajes eran descifrados. Cualquier desliz era usado por los matemáticos aliados que se servían sobretodo de las repeticiones en los mensajes para romper los códigos. Por ejemplo, el habitual “Hail Hitler!” que se incluía en la mayoría de mensajes era una mina de oro para los criptoanalistas.

(...)

A Turing pareció importarle poco que fuera el diseño de Newman y no el suyo el que fue llevado a la práctica finalmente. Lo importante era que la Maquina se podía construir; así que inmediatamente Turing dio el paso siguiente. Los últimos artículos de Turing son perfectamente vigentes hoy día y se centran en la cuestión de la inteligencia artificial. Para Turing la solución al problema de si una Maquina de Turing podría desarrollar la inteligencia consistía en resolver otra pregunta: ¿es el cerebro humano una Máquina de Turing? Estos artículos eran enormemente avanzados y Turing manejaba conceptos e ideas que abrían nuevos campos completos de investigación. En uno de ellos es donde podemos encontrar su famoso test de Turing para determinar si una máquina es inteligente.

(...)

Turing tenía claro que aquella no era la vida que él quería vivir. No consideraba lógico mentir sobre algo tan trivial como su sexualidad y no estaba dispuesto a vivir toda su vida con aquellas inyecciones de hormonas. Él eligió su propio camino. Un día de 1954, inspirándose en su película preferida(blancanieves y los siete enanitos), compró una manzana y se encerró en su casa. Subió a su estudio, roció la manzana con cianuro y le dio un bocado.

El Profe se durmió para siempre.

Fuente: Un barco más grande

M.T. para calcular la división

Usamos el mismo alfabeto de siempre {0,1,B}, mismo poder computacional, más trabajo, masoquismo. El "0" se usa en este caso como separador y cada "1" indica un numero. Los formatos de entrada/salida son:

Entrada: ...B11111011B...

Salida:    ...B1011B...

Los primeros números que encontramos en la salida son el resto de la división. El número final es el cociente.

Descipción:

M.T. para calcular N cuadrado

Al igual que la anterior, esta Máquina de Turing se ha diseñado con un alfabeto reducido a los símbolos {0,1,B}. Incluye la M.T. de la multiplicación, aunque se añadieron estados previos para adecuar la cadena:

Entrada:                   ..B1111B.. 

Paso intermedio: ..B111101111B..

Salida:                       ..B1111111111111111B..

Descripción:

M.T. para calcular la multiplicación

La siguiente máquina de Turing se encarga de calcular la multiplicación de dos números enteros. Los formatos de entrada y salida son los siguientes:

Entrada:  ..B11101111B..

Salida:      ..B111111111111B...

Se ha usado un alfabeto reducido a los símbolos {0,1,B}, usando el símbolo "0" como separador.