Máquina de Turing

MSPC - Informações Técnicas

Máquina de Turing

Descrição resumida e princípio de operação

Índice do grupo | Página anterior | Próxima página |

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 pode ter vários símbolos diferentes.

Fig 01

O cabeçote C pode ler o conteúdo do passo e nele escrever, deixando-o cheio ou vazio. Por exemplo, na posição do cabeçote da figura e dependendo da instrução, o cabeçote poderá deixar a marca * ou removê-la, tornando vazia a posição.

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 em alguns 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 é apenas uma questão de referência.

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).

Tabela 01
Estado	Ação se a célula estiver cheia (*)	Ação se a célula estiver vazia
0	Mover para direita, continuar no estado 0	Escrever *, mover para direita, ir para estado 1
1	Mover para direita, continuar no estado 1	Mover para esquerda, ir para estado 2
2	Apagar, parar

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	*   *   *   *   *   *   *

Os estados que a máquina pode assumir podem ser vistos como variáveis auxiliares para a tomada de decisões. Tudo isso lembra um pouco o software das máquinas de hoje.

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.

Topo | Página anterior | Próxima página | Última revisão ou atualização: Dez/2009