Paradigmas de programacao

A MÁQUINA DE TURING
Osvaldo Antonio Pozza, Sérgio Penedo Mestrado em Ciências da Computação 1º trimestre, 2002 CPGCC Universidade Federal de Santa Catarina(UFSC), Brasil Fone: [phone], Fax: [phone] [e-mail], [e-mail]

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. Em seguida foi examinada a teoria da idéia de Turing sobre a computabilidade, culminando com um exemplo de demonstração. Palavras-chave : Máquina de Turing, Teoria da Computação, Computabilidade.

Abstract
The present article has for objective to present a Simulation of the operation of a machine of Turing. Initially, he tried to locate the theme approached in the context of the Theory of the Computation. Soon after the theory of the idea of Turing was examined on the computability, culminating with a demonstration example. Key-words : Machine of Turing, Theory of the Computation, Computability.

Introdução 1. História: Neste parágrafo é conhecido um pouco da história do computador. 2. Sistemas Formais: Neste parágrafo fala como são estabelecidas as regras que caracterizam os sistemas formais. 3. Alan Mathison Turing: Neste parágrafo fala da origem de Alan Mathison Turing, sua consagração como matemático e sua grande idéia, “a máquina de Turing”. 4. A Máquina de Turing: Neste parágrafo explica todo o processo de funcionamento e também algumas regras a ser executada para o funcionamento da máquina de Turing.

1. História
Os primeiros passos em direção aos computadores digitais foram dados no Egito e Babilônia, há mais de 4 milênios, com os sistemas de medidas de distâncias e previsão do curso das estrelas. Durante a a florescente civilização grega, estas pré-ciências tomaram forma através dos sistemas axiomáticos. Em um sistema axiomático parte-se de premissas aceitas como verdadeiras e regras ditas válidas, que