16.7.05

A Máquina de Turing

Que tal uma Máquina de Turing toda feita de LEGO?

Introduzida por Alan M. Turing em 1936, a Máquina de Turing é uma abstração usada no estudo da Teoria da Computação: o que um computador pode ou não fazer.

O processo computacional foi graficamente mostrado no artigo de Turing quando 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 determina o que se convencionou chamar 'estado' da máquina. A fita é potencialmente infinita.

2 comentários:

Andrei Formiga disse...

O exercício agora é construir uma máquina de Turing universal com Lego :)

Rafael Torres disse...

Sempre quiz comprar uma lego mindstorm deste para mim :D com os controladores RCX... Para poder programar java com o lejos.... O unico problema é que eles custam mais de mil reais :( ...