Maquinas De Turing

UNIVERSIDAD DE CHILE
FACULTAD DE CIENCIAS FÍSICAS Y MATEMÁTICAS
EL-4102 ARQUITECURA DE COMPUTADORES

Tarea N 3
Máquina de Turing

Nombre: Felipe Zuñiga P.
Profesor: Francisco Rivera

Fecha:20 de Agosto del 2012

Presentación del problema
Este trabajo consta en desarrollar una Máquina de Turing, la cual sea capaz de dividir dos números
binarios sin signo. Para esto se considera quela máquina de Turing cuenta con una cinta infinita,
para leer, escribir y sobrescribir caracteres.

El programa debe dividir dos números binarios sin signo. Los números pueden ser de cualquier
largo y siempre en la etapa inicial en la cinta deben estar separados por un signo $
(Dividendo$Divisor). Al final de la operación, los números deben mostrarse como: Dividendo,
Divisor, Cociente yResto, todos separados por un signo $, es decir:
$

$

$

Además se deberá suponer que no hay “overflow” y para la simulación se debe utilizar el
simulador que se encuentra en la web en: http://morphett.info/turing/turing.html

Consideraciones
a) Se debe entregar un informe que explique el algoritmo utilizado y las consideraciones que
se tuvieron para optimizar el programa (minimización dela cantidad de pasos).
b) Como parte del informe, se debe entregar un Diagrama de Estados como el desarrollado
en los ejemplos de la clase con una explicación de lo que significan cada uno de dichos
estados.
c) Se puede tomar como referencia la multiplicación de números binarios sin signo que está
dado como ejemplo en el simulador.
d) No es necesario que el programa aborde la posibilidad dedesbordamiento (“overflow”)
dado que se supondrá que siempre el resultado es representable. Se debe detectar la
situación de división por cero.
e) El programa debe ser simulado en http://morphett.info/turing/turing.html y debe ser
comentado en cada una de sus instrucciones o filas.

2
EL-4102 Arquitectura de Computadores

Solución
Dada la extensión del código que se concreto y la grancantidad de diagramas de estados utilizados
para lograr la solución, se limitara a explicar el funcionamiento mediante diagramas más
generalizados de esta forma se resume y queda en forma más clara el funcionamiento planteado
para la máquina de Turing.

•Se verifica que es posible la division
•Se busca el caso de division de cero por cualquier número.
Inicio

Se crea el resto y lareserva

Se toman los bits
del resto y del
divisor

•Dado que estamos en el inicio de la division el dividendo es igual al resto.
•Al cumienzo se crea una reserba parala resta de cero.

•Se toman el mismo numero de bits del divisor, del resto y se comparan ambos números.
Se

•Si el número del resto es mayor al del divisor, se realiza la resta y se agrega un uno al cuociente.
•En casocontrario se guarda el pimer bit del resto en la reserva y se borra este bit del resto. Se
agrega un cero al cuociente y se repire la operación.
Resta

•Si se llega a un punto en que el numero de bits del resto es menor al cuociente , se agrega la reserva
Si
al resto y se termina la división
Verificación

•Luego de terminado los procesos aritmeticos se ordenan los datos en el formatoestablecido.
Luego
Ordenamieto

•Se posiciona la maquina de turing en el primer bit del dividendo y se termina el programa.
Termino

3
EL-4102 Arquitectura de Computadores

A continuación se muestra cómo funciona el algoritmo en el simulador, para ello usaremos el
ejemplo de división entre con los parámetros 25 como dividendo y 7 como divisor.
25
7

= 11001
= 111

1. En primera instanciase tienen los valores iníciales:

2. Luego se copia el dividendo creando el resto y la reserva (la codificación es a=1 y b=0 ):

3. Se seleccionan los bits a restar:

4. Se comparan estos números para comprobar que se puede realizar la resta (codificación
c=1 y d=0 ):

5. Dado que no es posible restar (el número del resto es menor al del divisor),se agrega un
cero al inicio (lugar...