Httpwww

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO

MÔNICA XAVIER PY

Análise da Máquina de Turing
Persistente com Múltiplas Fitas de
Trabalho

Dissertação apresentada como requisito parcial para a obtenção do grau de
Mestre em Ciência da Computação

Prof. Dr. Tiarajú Asmuz Diverio
Orientador

Prof. Dr. Antônio Carlos da Rocha Costa
Co-orientador

Porto Alegre, maio de 2003

CIP – CATALOGAÇÃO NA PUBLICAÇÃO
Py, Mônica Xavier
Análise da Máquina de Turing Persistente com Múltiplas Fitas de Trabalho / Mônica Xavier Py. – Porto Alegre:
PPGC da UFRGS, 2003.
74 f.: il.
Dissertação (mestrado) – Universidade Federal do Rio
Grande do Sul. Programa de Pós-Graduação em Computação, Porto Alegre, BR–RS, 2003. Orientador: Tiarajú Asmuz
Diverio; Co-orientador: Antônio Carlos da Rocha Costa.
1. Máquina de Turing Persistente Paralela. 2. Máquina de Turing. 3. Teoria da Computação. 4. Teoria da Computação Interativa. 5. Máquina de Turing Persistente. I. Diverio,
Tiarajú Asmuz. II. Costa, Antônio Carlos da Rocha. III. Título.

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
Reitora: Profa . Wrana Maria Panizzi
Pró-Reitor de Ensino: Prof. José Carlos Ferraz Hennemann
Pró-Reitora Adjunta de Pós-Graduação: Profa . Jocélia Grazia
Diretor do Instituto de Informática: Prof. Philippe Olivier Alexandre Navaux
Coordenador do PPGC: Prof. Carlos Alberto Heuser
Bibliotecária-chefe do Instituto de Informática: Beatriz Regina Bastos Haro

“Este trabalho é dedicado à mãe Imara, ao meu irmão Diogo e a minha Vó Heride.”

AGRADECIMENTOS

Gostaria de agradecer a todos aqueles que, em contextos diferentes, contribuíram para que chegasse até aqui. Na impossibilidade de citar todas as pessoas, gostaria de destacar alguns nomes, que de alguma forma direta ou indiretamente contribuíram para o desenvolvimento desse trabalho. Agradeço especialmente aqueles que estiveram diariamente envolvidos nesse trabalho.
• Aos meus familiares, especialmente a minha mãe,