MSPC | Início | Mapa | Uso | Pesquisar no Site | Fim pág | Voltar



Máquina de Turing

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

Descrição Resumida e Princípio de Operação

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. Nela, é possível encontrar alguns princípios semelhantes aos computadores atuais.

A Figura 1-1 mostra o conceito simplificado: uma fita que pode se mover de passo em passo para a direita ou para a esquerda (para resolver qualquer função, a fita deveria ter um comprimento infinito).

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.

Máquina de Turing
Fig 1-1

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 fita perfurada pela impossibilidade de recomposição do furo, mas fita magnética poderia ser usada).

O próximo componente é um conjunto de instruções específico para cada função a resolver, conforme exemplo simples a seguir (há programas de computador que simulam a máquina de Turing).

O exemplo é 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).

Tabela 02
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, lembrando 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 | Rev: Dez/2009