Em 1936, antes do advento do computador digital, o matemático inglês Alan Turing idealizou uma máquina que seria capaz de calcular qualquer função matemática mediante um determinado conjunto de instruções. Naturalmente, o propósito não era a criação de um computador como os atuais (na realidade, não havia na época tecnologia disponível para isso), mas é possível encontrar alguns princípios semelhantes.
O esquema da máquina de Turing é bastante simples, conforme Figura 01: uma fita que pode se mover de passo em passo para a direita ou para a esquerda (para resolver qualquer função, essa fita deverá ter um comprimento infinito, o que não é possível na prática. Mas aqui está informado o conceito teórico).
Cada passo (também chamado de célula) pode estar cheio (representado por *) ou vazio. No exemplo da figura, em a existe um passo vazio e em b, dois passos vazios adjacentes.
Por simplicidade, é aqui suposto que uma célula cheia só pode ter um único símbolo (*), mas também pode ter vários símbolos diferentes.
Figura 01
Agora um cabeçote C que pode ler o conteúdo do passo e escrever no mesmo, deixando-o cheio ou vazio.
Por exemplo, na posição do cabeçote da figura e dependendo da instrução, este poderá deixar a marca * ou removê-la, fazendo-o vazio.
Notar que, numa construção prática, não seria viável uma do tipo fita perfurada, pois seria muito complicado recompor um local furado, mas seria perfeitamente possível o uso de fita magnética como nos equipamentos atuais.
O próximo componente é um conjunto de instruções específico para cada função a resolver, conforme exemplo a seguir, que é simples, apenas para demonstração. Existem muitos outros que podem ser apresentados, inclusive programas de computador que simulam a máquina de Turing.
Na descrição anterior foi comentado que a fita se move e o cabeçote é fixo, similar a um gravador atual. Entretanto, para facilitar a representação em tabela, considera-se agora que o cabeçote se move e a fita é fixa, o que dá o mesmo resultado (a diferença seria numa construção prática, muito mais problemática nessa hipótese).
O exemplo considerado é uma operação matemática elementar: somar dois números inteiros. Supõe-se que se deseja somar os números 3 e 4.
A entrada dos dados seria uma fita com a disposição: *** ****, ou seja, representando os números 3 e 4.
A saída dos dados seria a seguinte informação na fita: *******, ou seja representando o número 7 (3 + 4).
A Tabela 01 acima, também denominada tabela de ações, instrui a máquina para adicionar dois números consecutivos e apresentar o resultado conforme estabelecido.
Abaixo a operação passo a passo da máquina (a posição do cabeçote é indicada pelo fundo cinza).
Estado Dados da fita 0 * * * * * * * 0 * * * * * * * 0 * * * * * * * 0 * * * * * * * 1 * * * * * * * * 1 * * * * * * * * 1 * * * * * * * * 1 * * * * * * * * 1 * * * * * * * * 2 * * * * * * * * Parar * * * * * * *
Notar os estados que a máquina pode assumir são como variáveis auxiliares para a tomada de decisões. Tudo isso lembra um pouco o software das máquinas de hoje.
Observar que o procedimento poderia somar qualquer par de números inteiros, independente dos valores. Entretanto, o número de células necessárias deve acompanhar. Assim, por exemplo, para somar 40000 com 60000 seriam, no mínimo, 100000 células. Na realidade, uma máquina de Turing universal, isto é, capaz de efetuar qualquer operação matemática e com quaisquer valores, deveria ter uma fita de comprimento infinito.