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.