Maquina de Turing simple para calcular Divisores
Hemos utilizado una maquina de turing en la que hemos dividido su cinta en dos sectores. Uno contiene la cadena en si y otro para marcar si hemos leído o no cierto símbolo.
Objetivo: Dado un numero entero, calcular sus divisores.
Entrada: ...BB000000BBB...
Salida: ...BBB000000101001000BB...
Como resultado, tenemos el numero inicial y sus divisores (incluido el 1) separados por 1's.
A continuación explicamos que "hace" la MT en cada grupo de estados, es decir, la distintas fases del proceso de calculo de divisores:
De q0 a q2 prepara la cadena poniendo el primer numero con el que vamos a comprobar si es divisor y el simbolo $.
De q3 a q9 se mira si es divisor el numero, si es divisor pasa a q10, si no a q11.
En q10 ( si es divisor ) ponemos el 1 al final de la cadena y vamos a q17, si no es divisor ( estamos en q11) vamos a q12 a ver el siguiente numero.
Desde q17 hasta q21 copia la cadena, o sea el numero que es divisor, al final de la cadena y despues va a q12 para comprobar si el siguiente numero es divisor.
Desde q12 a a q16 añade un 0 al numero que queremos ver si es divisor y comprobamos que sea menor o igual que la mitad del que queremos ver sus divisores.
En q22 y q23 preparamos la cadena para ver si el numero es divisor y vamos a q3 .
En q24 y 25 acabamos por dejar la cadena con solo el numero del que hemos calculado sus divisores y sus divisores detrás separados por "1".
No hay comentarios:
Publicar un comentario