por José Maria Silveira Neto e Cassiano F. C. Rocha para a disciplina de Teoria da Computação do Departamento de Computação da Universidade Federal do Ceará, 2007.1. Professor Francisco Heron de Carvalho Júnior.

Máquina de Turing

Uma máquina de Turing pode ser definida como uma 7-tupla M = <Q, Γ, Σ ,q0, b, F, δ>, onde:

  • Q é o estados.
  • Γ é o alfabeto de entrada.
  • Σ ⊆ Γ – {b} é o alfabeto da fita.
  • q0 ∈ Q, é o estado inicial.
  • b ∈ Γ, é o espaço em branco.
  • F ⊆ Q, é o conjunto de estados finais.
  • δ → Q×Γ→Q×Γ×{L,R} é a função de transição onde L é um movimento para a esquerda e R é um movimento para a direita.

Máquina de Turing com uma só fita

O comportamento da máquina de turing é determinado pela sua função de transição δ. A cada passo a cabeça lê um símbolo e dependendo de seu estado ela grava outro símbolo, muda de estado e vai para esquerda ou direita.

Chamaremos aqui essa máquina de MT¹ ou somente MT.

Máquina de Turing com múltiplas fitas e cabeças

Nessa extensão da Máquina de Turing, a máquina pode ter múltiplas fitas cada uma com sua cabeça com permissão para leitura e escrita. Vamos nos focar no caso onde há duas fitas, que chamaremos de MT².

Máquina de Turing com duas fitas e duas cabeças multi-tape multi-head turing machine

A cada passo a máquina lê um os símbolos lidos por suas cabeças e dependendo desses resultados e do estado da unidade central, cada cabeça move ou escreve e o estado central muda.

A função de transição δ² da MT² é da forma:

δ² → Q×Γ×Γ → Q×Γ×Γ×{L,R}x{L,R}

Note que os movimentos das cabeças são independentes. É possível que em um passo uma cabeça ande para a esquerda e a outra para a direita.

Equivalência

A MT² é equivalente a uma MT¹. Embora ela traga alguma facilidade e eficiência ela não traz nenhum poder computacional adicional. De forma que podemos simular uma MT² usando uma MT¹.

Podemos mostrar isso usando um raciocínio que converte MT² em MT¹.

  • Intercalamos as duas fitas em uma só fita.
  • Criamos símbolos adicionais para guardar a posição das duas cabeças.
  • Quando andamos para a direita em MT² andamos para a direita duas vezes em MT², e guardamos a posição da cabeça em questão de uma forma apropriada.
  • Quando andamos para a esquerda em MT¹ andamos para a esquerda duas vezes em MT², e guardamos a posição da cabeça em questão de uma forma apropriada.

Primeiro vamos converter as duas fitas em uma só, intercalando seus estados, da seguinte maneira:

Duas fitas em uma

Porém só isso não basta, pois perdemos a informação de onde estavam as cabeças na máquina.

Para resolver esse problema estendemos o alfabeto Σ com o alfabeto Σ² que é formado pelos símbolos de Σ acrescidos de ¹ e ². Por exempo se tínhamos um alfabeto {a,b} teremos um novo alfabeto {a,b,a¹,b¹,a²,b²}. Usaremos isso para simular a posição das cabeças na fita.

Se temos as fitas {a,b,a,a,a,b,a} e {a,a,b,a,a} com a primeira cabeça apontada para o primeiro símbolo da primeira fita e a segunda cabeça apontada para o quarto símbolo da segunda fita construiremos uma fita {a¹,b,a,a,a,b,a,a,a,b,a²,a}.

Como exeplo, seja o seguinte elemento da função de transição δ²:

  • (q,a,a) → (q’, b, b, R, R)

Ele pode ser transformado para estes elementos da função de transição δ¹:

  • (q, a¹) → (qtmp1, b, R)
  • (qtmp1, s) → (qput_head1, s, R), ∀s ∈ Σ∪Σ²
  • (qput_head1, s)→(qback, s¹, R), ∀s ∈ Σ
  • (qback, s)→(qfind2, s, L), ∀s ∈ Σ∪Σ²

O que aconteceu foi o seguinte: estavamos no estado q lendo o símbolo a¹ que (simboliza que a cabeça 1 está ali), então gravamos b e andamos para a direita e vamos para um estado temporário qtmp. Ao apagarmos o ¹ daquele símbolo estamos removendo a cabeça 1 daquele lugar.

Para sair do estado qtmp qualquer símbolo servirá e iremos para a direita novamente (com essa fomos duas vezes) e ficamos no estado qput_head1. O estado qput_head1 vai colocar a cabeça ¹ naquela posição e irá para a direita com o estado qback. No estado qback com qualquer coisa voltamos na direção oposta (esquerda).

Fizemos a primeira parte da transição δ² que foi a da primeira fita, mas temos ainda que encontrar onde está a segunda cabeça e executar as intruções da segunda fita da mesma forma que fizemos com a primeira fita.

O estado qfind2 vai tratar de encontrar ando está a segunda cabeça. Por motivos de simplicidade vamos omitir como é feita essa busca.

Quando estivermos sobre s² podemos acrescentar os elementos:

  • (q, a²) → (qtmp2, b, R)
  • (qtmp2, s) → (qput_head2, s, R), ∀s ∈ Σ∪Σ²
  • (qput_head2, s)→(qback, s², R), ∀s ∈ Σ
  • (qback, s)→(qfind1, s, L), ∀s ∈ Σ∪Σ²

Da mesma maneira qfind1 encontrará a primeira cabeça e deixará a máquina pronta para a próxima instrução.

Isso foi um exemplo de como transformar um certa instrução de δ² para δ¹. Utilizando o mesmo raciocínio podemos estender qualquer instrução de δ² para δ¹.

Generalização para MTk

Se ao invés de 2 fitas e 2 cabeças houvese k fitas e k cabeças poderíamos utilizar a mesma intercalação para transformarmos as k fitas e um única fita e poderíamos utilizar o mesmo raciocínio para transformar suas transições, tomando o cuidado de:

  • Quando houver um R em MT², andamos para direita K vezes em MT¹.
  • Quando houver um L em MT², andamos para esquerda K vezes em MT¹.

Referências: