Teoria da Computação: Máquinas, Programas e suas Equivalências

Thielyon Pinheiro, Álvaro Hauenstein, Daniel Dessbesell, Daniel Padilha, Douglas Rodrigues Almeida, Laércio Castro, Vanderlei Cardoso, Alex Telocken

Resumo


Este trabalho faz um comparativo, mostrando a equivalência entre maquinas e programas, entre os modelos universais mais conhecidos como Máquina de Turing, Máquina de Post, Autômato de Duas Pilhas e Máquina de Registradores NORMA. Para todos estes modelos são definidos formalmente sua estrutura e seu modelo de execução. Respectivamente, são apresentadas conversões entre Máquinas de Turing e Máquinas de Post; entre Máquinas de Post e programas para Máquinas Norma; entre programas para Máquinas Normas e Autômatos de Duas Pilhas; entre Autômatos de Duas Pilhas e Máquinas de Turing. O fechamento do ciclo prova que todos os modelos são equivalentes entre si. Adicionalmente, todas as traduções são provadas corretas, ou seja, a tradução preserva a linguagem reconhecida pelas máquinas.


Texto completo:

PDF

Referências


ALVES, Debora Pandolfi, Equivalência de Máquinas Universais: Demonstração, Análise e Simulação, julho de 2007 Universidade Do Vale Do Rio Dos Sinos.

PEREIRA, Andréa, Aula 5 Teoria da Computabilidade, Curso Ciência da Computação, 2006, Universidade de Cruz Alta UNICRUZ.

RAMOS, Marcus Vinícius Midena Ramos, maio de 2012, Universidade Federal do Vale do São Francisco UNIVASF

DIVERIO, Tiarajú A. MENEZES, Paulo B., Máquinas Universais e Computabilidade. 1999, Teoria da Computação - 3.Ed. - UFRGS Bookman Editora


Apontamentos

  • Não há apontamentos.