Teoria da Computação

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO GRANDE DO SUL
FACULDADE DE INFORMÁTICA
CURSO: Engenharia da Computação
DISCIPLINA: Teoria da Computabilidade
Trabalho T1 - IMPLEMENTAÇÃO DE UMA UNIDADE ARITMÉTICA E LÓGICA COM MÁQUINA DE
TURING MULTIFITA

O trabalho consiste em construir e testar, com ajuda da ferramenta JFLAP, uma Máquina de Turing multifita que simula o funcionamento de uma ULA rudimentar a nível de linguagem de máquina.

Referências: livro do Hopcroft, Ullman & Motwani, seção 8.6.2 e livro de Lewis & Papadimitriou, seção
4.4.
Requisitos: o grupo (de até 2 alunos) deverá:
a) Construir uma máquina de Turing multifita com as características especificadas abaixo;
b) Elaborar pelo menos um caso de teste para cada instrução implementada;
c) Elaborar um pequeno documento que explique em alto nível a máquina produzida (estratégias, algoritmos, alternativas, etc.) e os casos de teste.

A máquina a ser simulada possui as seguintes características:
FITA 1: RI - registrador de instruções. Armazena a instrução a ser executada (ver abaixo).
FITA 2 e 3: registradores X e Y. Toda a computação é centralizada nos registradores X e Y(veja instruções abaixo).
Formato e conjunto de operações. Todos os registradores possuem o mesmo número fixo de bits
(mínimo 3 bits). Quando o conteúdo de um registrador é interpretado como instrução, os dois primeiros símbolos (bits) formam o código da instrução conforme abaixo (o 3º. bit é ignorado neste caso):
1. 000 Not: máquina coloca em X o inverso (bitwise) de X.
2. 010 And: máquina coloca no registrador X o “and” (bitwise) entre X e Y.
3. 100 Add: máquina coloca no registrador X a soma em binário de X e Y. Se houver overflow, a máquina deve parar em um estado de rejeição.
4. 110 Mult: máquina coloca no registrador X o produto em binário de X e Y. Se houver overflow, a máquina deve parar em um estado de rejeição.

A máquina deve possuir exatamente as fitas especificadas, na ordem acima. Se for necessário,