Teoria da Computação

SIMULADOR DE MÁQUINA DE TURING PADRÃO
POR ESTADO FINAL
RESUMO
O presente artigo tem por objetivo apresentar uma simulação do funcionamento de uma máquina de Turing. Inicialmente, procurou-se situar o tema abordado no contexto da Teoria da Computação e em seu fator histórico. Em seguida foi examinada a teoria da ideia de Turing sobre a computabilidade em que foi projetado um programa para demonstrar suas especificações e sua real importância.
Palavras-chaves: Computabilidade, Máquina de Turing, Simulação, Teoria da Computação.

ABSTRACT
Title: “Simulator turing machine standard in final stage”
The present article aims to present a simulation of the operation of a Turing machine. Initially, we tried to situate the issue addressed in the context of the Theory of Computation and its historical factor. Then we examined the theory of Turing on the idea of computability in a program that was designed to demonstrate your specifications and the real importance.
Key-words: Computability, Machine of Turing, Simulation, Theory of the Computation.

1

INTRODUÇÃO

Alan Mathison Turing (23 de Junho de 1912 — 7 de Junho de 1954) foi um matemático, lógico, cripto analista e cientista da computação britânico. Foi influente no desenvolvimento da ciência da computação e na formalização do conceito de algoritmo e computação com a máquina de Turing, desempenhando um papel importante na criação do computador moderno. Ele também é pioneiro na inteligência artificial e na ciência da computação. (NUNES Mayza, acessado em 20/02/2014;)
A máquina de Turing é um dispositivo teórico conhecido como máquina universal, muitos anos antes de existirem os modernos computadores digitais. Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento de memória, estados, transições e não à sua implementação física. (SARAIVA Márcio, acessado em 20/02/2014;)
Uma máquina de Turing consiste em:
1. Uma fita composta