A máquina de Turing

Prévia do material em texto

A máquina de Turing
Desenvolvida com o com o intuito de quebrar o código das comunicações alemãs durante a 2ª Guerra Mundial, produzido por um tipo de computador chamado Enigma. Este código era constantemente trocado, obrigando os inimigos a tentar decodifica-lo correndo contra o tempo, antes que mudasse novamente. 
Enigma 
Turing e um grupo de cientistas, liderados por  Tommy Flowers, trabalharam num sistema que foi chamado de Colossus, um enorme emaranhado de servo-motores e metal, considerado um precursor dos computadores digitais, responsável por decodificar as mensagens da Enigma.
Colossus – Máquina de Turing
Todo o funcionamento da Colossus foi demonstrando em artigo por Turing. Ele pediu ao leitor que considerasse em dispositivo que pudesse ler e escrever símbolos em uma fita que estava dividida em quadrados. 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 sobre leitura e gravação de símbolos nos quadrados, movendo-se, ou não, para a direita ou esquerda. O quadrado que é "lido" em cada etapa é conhecido como "quadrado ativo". 
A regra que está sendo executada para a leitura/gravação da fita determina o que se convencionou chamar 'estado' da máquina. A fita é potencialmente infinita. Imagine os símbolos "I" e "-"(branco). Suponha que o dispositivo possa limpar qualquer um deles quando ele os lê em um quadrado ativo e trocá-lo por outro (apagar "I" e substituir por "-" e vice-versa). O dispositivo pode mover a cabeça de leitura e de gravação para a direita ou esquerda, de acordo com instruções interpretadas pela unidade de controle. As instruções podem limpar um símbolo, escrevê-lo ou deixá-lo como está, de acordo com o símbolo lido.
Em sua essência, toda máquina de Turing movesse ou move símbolos, de uma posição para outra em uma fita. Nos dias de hoje estes símbolos podem ser impulsos eletrônicos em um microcircuito e a fita uma série de endereços de memória em um chip , mas a idéia é a mesma. Turing provou que sua hipotética máquina é uma versão automatizada de um sistema formal especificado por uma combinação inicial de símbolos e as regras. Os movimentos são mudanças de 'estado' da máquina que correspondem a específicos passos de computação. 
Turing provou que para qualquer sistema formal existe uma máquina de Turing que pode ser programada para imitá-lo. Era este sistema formal genérico, com a habilidade de imitar qualquer outro sistema formal, o que Turing procurava. Tais sistemas chamam-se Máquinas de Turing Universais. A teoria foi estabelecida pela primeira vez em um 'paper' que tinha o título "On Computable Numbers, with an application on the Entscheidungsproblem".
Turing estabeleceu um modelo formal de algoritmo e um pouco depois Church proporia que qualquer procedimento efetivo poderia ser realizado por uma Máquina de Turing (Tese de Church). Quer dizer, qualquer processo aceito por nós homens como um algoritmo é precisamente o que uma Maquina de Turing pode fazer
Referência
[1] www.cic.unb.br/tutores/turing/untroduc.html 
[2] Hodges, Andew Turing Um Filósofo da Natureza 1ª Edição 
[3] Osvaldo Antonio Pozza, Sérgio Penedo A Maquina de Turing UFSC
[4] Barreto, Jorge Muniz Inteligência Artificial 3ª Edição A MÁQUINA DE TURING