 |
M.P.-I - 2000/01 - Trabalho Prático Nr. 1
|
|
[ DI/UM ]
|
|---|
Este trabalho deve ser realizado por grupos com um máximo de três
alunos. O trabalho deve ser entregue até ao dia na
Recepção do Departamento de Informática
(ext. 4430) e nele deve constar a
listagem do código desenvolvido assim como um pequeno relatório.
A máquina de Turing
é um formalismo matemático introduzido por
Alan Turing (1936) para captar a noção que hoje temos de
algoritmo ou procedimento computável .
As máquinas de Turing são de uma natureza surpreendentemente concreta.
Quase conseguimos imaginar dispositivos físicos que reagem conforme
o comportamento que lhes é especificado - e.g. um leitor de 'cassettes',
um 'robot' - o que é extraordinário se
nos recordarmos que estas são anteriores aos primeiros computadores.
O seu impacto na teoria da computação é enorme,
nomeadamente na
teoria da computabilidade e da complexidade (o que,
aliás, justificará o seu estudo adiante na licenciatura).
O objectivo do trabalho é o de realizar um animador de máquinas de Turing
em HASKELL
.
Uma máquina de Turing é constituída por:
- uma fita organizada por quadrículas, cada uma destas
podendo conter um dado símbolo (de um alfabeto finito
pré-determinado) ou encontrar-se vazia (o que pode ser entendido
como um símbolo particular). Não se impõe qualquer limite ao tamanho
desta fita (i.e. pode considerar-se infinita)
- uma cabeça de leitura/escrita que permite
consultar/escrever o conteúdo de uma dada quadrícula da fita (a
quadrícula sobre a qual a cabeça se encontra posicionada). Podemos
então particionar a fita em:
- segmento que se encontra à esquerda da cabeça
- quadrícula corrente
- segmento à direita da cabeça.
Já referimos que não limitamos o tamanho da fita mas admitimos que
só as quadrículas que se encontram numa vizinhança finita da cabeça
estão ocupadas em cada momento.
- a máquina dispõe de um dispositivo capaz de movimentar a fita
para a direita/esquerda (possibilitando assim a leitura/escrita de
outra quadrícula)
Vejamos agora como funciona:
- A máquina dispõe de um conjunto finito de estados
internos . Cada um destes estados determina qual a reação da
máquina na presença de um dado símbolo. Mais precisamente, num
dado estado interno faz-se corresponder ao símbolo lido
- que símbolo é escrito (sobrepondo-se ao lido)
- qual o movimento da fita (direita ou esquerda)
- se deve prosseguir a computação num novo estado interno ou
parar a máquina (concluindo a execução).
Podemos designar por programa o conjunto de estados internos
juntamente com a especificação das acções descritas.
- Para iniciar o processo, é fornecida uma fita cujo segmento
da esquerda está vazio e identifica-se um dado estado: o
estado inicial .
Este trabalho envolve uma certa pesquisa de informação adicional no WWW.
Para um excelente simulador de máquinas de Turing
aconselha-se a consulta de
www.nmia.com/cgi-bin/cgiwrap/%7Esoki/turing
.
Aí é possível
ver exemplos da execução de algumas máquinas de Turing assim como
experimentar ``novos programas''.
Outras referências à (e descrições da) máquina de Turing,
incluindo exemplos de execução, são as seguintes:
A pesquisa no WWW permitirá identificar algumas centenas de
outros sites potencialmente interessantes...
A equipa de avaliação espera que sejam codificados,
no simulador em HASKELL
a desenvolver no trabalho,
alguns dos exemplos apresentados nas páginas acima
referidas (e.g. a soma unária).
Os seguintes aspectos serão também tidos em conta na avaliação deste trabalho:
- 1.
- Recurso a mónadas em HASKELL
.
- 2.
- Interacção com o utilizador (i.e. utilização da mónada IO).
- 3.
- Definição de uma sintaxe simples (à escolha) para permitir
carregar directamente ficheiros com a descrição do programa
(i.e. acções para cada um dos estados internos).
- 4.
- Teste do simulador com um programa que incremente um número
(em notação binária) de uma unidade.
- 5.
- Demonstração de outros exemplos de utilização do simulador.
Voltar à página principal de MP-I
.
Outras disciplinas leccionadas pelo DIUM
10/11/2000
Jose Nuno Oliveira