Máquinas universais: demonstração, análise e equivalência

Abstract

ResumoA ciência da computação é fundamentada em modelos computacionais construídos na primeira metade do século XX, em 1936 foi publicado a Máquina de Turing modelo conhecido e aceito como a formalização de um algoritmo, esse que pertence à uma classe chamada de máquinas universais, detentora do maior poder computacional até hoje. A teoria da computação tem um papel importante na construção do conhecimento e proporciona desenvolvimento do raciocínio logico e formal, sendo que esse é cada vez mais necessário para a computação. É apresentado quatro modelos de máquinas universais (Máquina de Turing, Máquina de Post, Autômato de duas pilhas e Máquina de Norma), esses que são contextualizados e a partir disso desenvolvido simuladores para cada, além de demostrar também como um modelo pode ser simulado por outra máquina universal, afim de comprovar a Tese de Church. Ao final da pesquisa, foi desenvolvido um protótipo web responsável pelos simuladores e que efetua a conversão de Máquina de Post para Máquina de Turing e Autômato de Duas Pilhas para Máquina de Turing.