Até o momento, vimos MTs de propósitos específicos. Ou seja, cada MT que demos como exemplo representava uma única linguagem simples, como: a linguagem das palavras formadas apenas por a’s ou a linguagem das palavras anbncn, com n≥1. Essas MTs seriam como computadores muito
restritos que resolvem um só problema.
Em contraste, os nossos computadores modernos podem resolver vários problemas – só depende do programa que é dado como entrada para ele. Isso
não seria um indicativo de que os computadores que usamos são mais poderosos do que as MTs?
Não! Como já dissemos no capítulo anterior, os computadores modernos são, no máximo, equivalentes às MTs (se esquecermos que eles têm memória finita). E nós vamos mostrar, nesta primeira seção, que também existe uma MT geral que pode ser “programada” para resolver diversos problemas. Em especial, essa MT pode simular qualquer outra MT imaginável. Por isso, ela recebe o nome de “Máquina de Turing Universal” ou MTU.
De certa forma, a MTU sozinha pode resolver todos os problemas que qualquer outra MT pode resolver. Mas para isso, a MTU precisa receber não só a cadeia w que será testada (ou a entrada de um problema), como também a descrição da MT X que se deseja simular. A MTU, então, vai simular o que X faria ao receber w, retornando, no final, o resultado (sim/não) que X retornaria. A figura abaixo ilustra essa idéia:
Essa descrição de X teria, na MTU, uma importância parecida com a que um “programa” tem nos computadores que usamos hoje em dia. Isso porque o que ambos fazem (tanto a descrição de X como o programa) é descrever como a máquina deve se comportar. Da mesma forma como usamos diferentes programas para fazer tarefas diferentes nos computadores modernos, também podemos dizer à MTU como resolver diferentes problemas passando para ela as descrições das diversas MTs que decidem cada problema.
Um detalhe na figura anterior que ainda não está muito correto é que ela mostra duas entradas para a MTU. No entanto, sabemos que toda Máquina de
Máquina de Turing Universal (vai simular a ação de X
quando X recebe w) w
sim/não descrição de
fazer dar uma descrição da máquina X na forma de uma cadeia, que representaremos abstratamente como <X>. Ainda assim, teríamos duas cadeias: <X> e w. Vamos unir essas duas cadeias em uma só cadeia, que vamos representar abstratamente como <X,w>.
Assim, quando escrevermos algo como <X,w>, entenda isso como uma cadeia em que podemos separar a parte <X> da parte w, onde a parte <X> é a descrição de uma máquina de Turing e w é uma cadeia de entrada para X.
ATENÇÃO
Fazer essa codificação de uma máquina de Turing X e de w em uma cadeia única <X, w> pode parecer difícil, mas você pode ter certeza de que é uma tarefa possível!
Aliás, é possível transformar em cadeias não só uma MT como também diversas outras informações complexas tais como: figuras, textos, músicas e vídeos. De fato, todas essas informações são codificadas nos nossos computares como cadeias (imensas) do alfabeto binário {0,1}.
Para o leitor interessado, nós explicamos detalhadamente no Apêndice A como fazer a codificação <X, w> usando esse mesmo alfabeto.
A figura abaixo ilustra a MTU de maneira mais correta, recebendo uma só cadeia:
MTU
(vai simular a ação de X quando X recebe w)
Não vamos definir a MTU em todos os seus detalhes, pois essa máquina teria, pelo menos, algumas dezenas de estados. O nosso objetivo é apenas mostrar que é possível usar o modelo Máquina de Turing para criar uma máquina universal que simula qualquer MT. Por isso, no restante da seção, daremos apenas a idéia geral de como essa máquina de Turing Universal funcionaria. Com base nesses detalhes e com algum esforço, um aluno interessado é capaz definir de maneira completa uma MTU.
Para o restante da explicação, vamos representar de maneira abstrata como a informação <X, w> é disposta na fita da MTU usando figuras. A figura abaixo mostra como a fita da MTU é iniciada. Considere que à esquerda de X e à direita de w, naturalmente, existem infinitos símbolos brancos.
Ao iniciar com a fita assim, a MTU vai acrescentar um espaço para uma terceira informação: uma cadeia representando o estado atual da máquina X. Essa informação será fundamental para simular o funcionamento de X. Inicialmente, a fita teria a descrição do estado inicial q posicionada imediatamente antes da cadeia w assim:
O nosso objetivo será usar a fita para simular uma computação na máquina X. Portanto, deixaremos a informação do estado imediatamente antes do próximo símbolo a ser lido da cadeia w, similar à representação das IDs que criamos na seção 2.2 para as MTs. Assim, a região da fita que começou com a cadeia w será sucessivamente alterada para refletir o que X faria na sua fita. Portanto, em um momento qualquer da simulação a fita pode aparecer assim:
MTU, mas a ID da máquina X que a MTU está simulando na sua fita). O que a MTU irá fazer a partir de uma situação como essa é similar ao que fazemos com as IDs quando representamos uma computação em uma máquina de Turing. Porém, o processo na MTU será um tanto mais trabalhoso por conta das limitações da fita.
A cada passo da computação, a MTU irá se comportar assim:
1. Ela irá fazer voltar a cabeça da fita até a definição da máquina X no começo da área útil da fita. Dentro da definição de X, ela irá procurar o trecho que codifica a primeira transição.
2. Digamos que a transição encontrada (mesmo que codificada de outra forma) represente δ(qor, Aler) = (qdest, Aescr, M).
3. A MTU irá comparar se o estado de origem qor da transição é igual
ao estado atual da máquina X, representado na figura como o trecho “q” da fita.
o Se forem distintos, ela vai procurar a próxima transição e volta
ao passo 2.
4. Se os estados forem iguais, ela irá voltar à transição para ver qual o símbolo que ela precisa ler, que representamos antes como Aler. Em
seguida, a MTU, vai comparar Aler com o símbolo atual da fita, que é
o primeiro símbolo da região representada como “fita-direita”.
o Se forem distintos, ela vai procurar a próxima transição e volta
5. Se os símbolos forem iguais, então a MTU achou a transição a ser realizada na máquina X. Assim, a MTU vai voltar na fita para encontrar os resultados da transição, que são: (qdest, Aescr, M).
6. A MTU avança na fita para mudar o estado atual de X, que passará de q para qdest.
7. A MTU vai mudar o símbolo atual de X, que passará de A para Aescr.
8. A MTU vai deslocar o estado atual (qdest) uma posição para a
esquerda (ficando a duas posições de distância de Aescr) ou uma
posição para a direita (ficando depois do símbolo Aescr), dependendo
do valor M (que pode ser E ou D).
Esse processo se repete enquanto a MTU encontrar, na descrição de X, alguma transição válida para realizar. Se, em algum momento, a MTU não achar uma transição, a MTU irá considerar que X parou. Nesse momento, a MTU irá procurar, na sua fita, o estado de X. Se for um estado de aceitação, a MTU aceita a cadeia w (indo para o seu estado de aceitação), senão ela rejeita. Dessa forma, ela dará a mesma resposta que X daria, como desejado.
Vemos que o comportamento da MTU é um tanto complexo e, por isso, as sua definição completa ficaria enorme. Mas o que queremos que você aprenda aqui é que definir uma MT Universal é algo possível de ser realizado! Isso é um resultado impressionante do modelo MT – ele é capaz de simular a si próprio. Nenhum dos outros modelos tem essa capacidade (por exemplo, não podemos
Na próxima seção, usaremos a idéia da MTU para provar outro resultado interessante sobre as MTs.