Aplica O De M Quina De Turing

Curso de Ciência da Computação

Aplicação de Máquina de Turing

Rio de Janeiro
2014
Curso de Ciência da Computação

Aplicação De Máquina De Turing

Rio de Janeiro
2014
SUMÁRIO

1. INTRODUÇÃO 4
2. DESENVOLVIMENTO 5
3. CONCLUSÃO 8
4. REFERÊNCIAS 9

1 Introdução

O inventor matemático Alan Mathison Turing em 1936 foi publicado um artigo intitulado "On Computable Numbers, with an Application on the Entscheidungsproblem", em resposta ao tratamento do problema da decisão, formulado por Hilbert. Turing estudava na universidade de Princeton, Nova Jersey‐EUA. Apesar da máquina de Turing não ter sido implementada fisicamente, na totalidade pelo seu autor, o processo computacional foi matematicamente demonstrado e provado no artigo. Turing mostrou que o dispositivo lógico que ele chamou de "automatic machine" (ou “a‐machine”), era capaz de realizar operações de leitura, escrita e exclusão de símbolos binários em uma fita de comprimento ilimitado com quadrados de igual tamanho e um dispositivo com um número finito de estados, que realizava as operações na fita. Uma cabeça de leitura/gravação se moveria em qualquer direção ao longo da fita, um quadrado por vez, e uma unidade de controle poderia interpretar uma lista de instruções simples, movendo‐se para a direita ou esquerda. A regra executada determina o que se convencionou chamar de estado da máquina. Se não existe uma máquina de Turing capaz de resolver um problema, ele não é computável.
Para Turing sua máquina era possível fazer o trabalho do calculador humano, indicando haver possibilidade de máquinas computacionais da união da matemática e lógica em processadores de símbolos. Durante a II Guerra Mundial, Turing trabalhou no Departamento de comunicação de Grã-Bretanha na tentativa de quebrar códigos da comunicação alemã, que eram produzidos por um tipo de computador denominado Enigma. Logo após, Turing foi para os EUA para estabelecer códigos seguros