Teoria da Computação

CONTEÚDO PROGRAMÁTICO

01. Máquinas de Turing

• Definição da Máquina de Turing
• Computando com máquinas de Turing
• Extensões da máquina de Turing
• Máquinas de Turing de acesso aleatório
• Máquinas de Turing não-determinísticas

02. Indecidibilidade
• A tese de Church-Turing
• Máquinas de Turing universais
• O problema da parada
• Problemas indecidíveis sobre máquinas de Turing
• Problemas insolúveis de gramática
• Um problema insolúvel de organização lado a lado
• Propriedades das linguagens recursivas

03. Complexidade Computacional

• A classe P
• Satisfazibilidade booleana
• A classe NP

04. Completude NP
• Reduções de tempo polinomial
• O teorema de Cook
• Problemas NP-completos
 2

BIBLIOGRAFIA BÁSICA

Lewis, H. R. e Papadimitriou, C. H., Elementos de Teoria da

Computação, Bookman, 2a. Edição, 2000.

Hopcroft, J. E., Motwani, R. e Ullman, J. D., Introdução à Teoria de

Autômatos, Linguagens e Computação.

MÁQUINAS DE TURING

Definição da Máquina de Turing

Uma máquina de Turing consiste em um controle finito, uma fita e

uma cabeça que pode ser utilizada para ler ou gravar na fita.

As máquinas de Turing podem ser formalizadas de forma

semelhante aos autômatos finitos e aos autômatos de pilha, todavia
ao contrário desses, as máquinas de Turing são mais expressivas
para caracterizar a computação, sendo usada na própria definição
de algoritmo.

Outra questão a respeito das máquinas de Turing refere-se ao fato

de que embora elas possam ser potencializadas (máquinas de
Turing com dupla cabeça, com duas fitas etc.), qualquer máquina
de Turing aumentada pode ser expressa por uma combinação de
máquinas de Turing básicas.

As máquinas de Turing foram projetadas para satisfazer

simultaneamente aos seguintes critérios:

1. Elas devem ser autômatos, isto é, sua construção e função

devem estar no mesmo espírito geral dos autômatos finitos.

2. Elas devem ser simples de descrever, de definir e de

raciocinar a respeito.
 3

3. Elas devem ser o mais geral possível em termos de cálculos

que podem realizar.
“A máquina de Turing é um dispositivo
teórico, conhecido como máquina
universal, que foi concebido pelo
matemático britânico Alan Turing (1912-
1954), muitos anos antes de existirem os
modernos computadores digitais (o artigo
de referência foi publicado em 1936).
Num sentido preciso, é um modelo
abstrato de um computador, que se
restringe apenas aos aspectos lógicos do
seu funcionamento (memória, estados e
transições) e não à sua implementação
física. Numa máquina de Turing pode-se
modelar qualquer computador digital.”
(Wikipedia)

Em essência, uma máquina de Turing consiste em um conjunto de

estado finito e de uma unidade de fita (veja figura a seguir). A
comunicação entre o controle finito e a fita é fornecida por uma
simples cabeça, a qual lê símbolos da fita e é também utilizada para
alterar os símbolos ali contidos.

a b a a

Cabeça de leitura/gravação
(move-se em ambas as direções)
q0
h
q1 Controle finito
q3
q2

A unidade de controle opera em passos discretos, realizando duas

funções a cada passo de acordo com o seu estado atual e com o
símbolo da fita atualmente lida pela cabeça de leitura/gravação:

1. Colocar o controle em seu novo estado.

2. Ou:
a. Gravar um símbolo no quadro da fita atualmente lida,
substituindo um que já está lá; ou
 4

b. Mover a cabeça de leitura/gravação um quadro de fita

para a esquerda ou para a direita.

A fita tem um final à esquerda, mas estende-se indefinidamente

para a direita. Para impedir que a máquina mova a sua cabeça até
o fim esquerdo da fita, assumimos que a extremidade esquerda da
fita está sempre marcada por um símbolo especial, denotado por .

Assumimos também que todas as nossas máquinas de Turing estão

projetadas de modo que sempre que a cabeça lê um , ela
imediatamente se move para a direita.

Utilizaremos também os símbolos → e ← para denotar o movimento

da cabeça de leitura/gravação para a direita e para a esquerda,
respectivamente. Uma máquina de Turing é alimentada com
entrada, gravando-se a string de entrada em quadros à esquerda do
final da fita, imediatamente à direita do símbolo .

O resto da fita inicialmente contém símbolos de espaços em branco,

denotados por ¬. A máquina é livre para alterar a sua entrada de
qualquer modo que considere apropriado, bem como para gravar
nos espaços em branco ilimitados em qualquer parte à direita da
fita.

Uma vez que a máquina pode mover sua cabeça somente um

quadro por vez, após qualquer computação finita, apenas um
número finito de quadros da fita terá sido visitado.

Podemos agora apresentar a definição formal da máquina de

Turing.

Definição: A máquina de Turing é o quíntuplo (K, Σ , δ , s, H), onde

K é o conjunto finito de estados;
Σ é um alfabeto que contém o símbolos de espaços em
branco ¬ e o símbolo de final esquerdo , mas que não
contém os símbolos → e ←;
s ∈ K é o estado inicial;
H ⊆ K é o conjunto de estados de parada;
δ , a função de transição, é a função de (K - H) x Σ para K x
(Σ ∪ {→, ←}), tal que
 5

(a) para todos os q ∈ K – H, se δ (q, ) = (p, b), então b =

→
(b) para todos os q ∈ K – H e a ∈ Σ , se δ (q, a) = (p, b),
então b ≠ .
Se q ∈ K – H, a ∈ Σ e δ (q,a) = (p,b), então M, quando no estado q
e varrendo o símbolo a, entrará no estado p e:

(a) Se b for um símbolo em Σ , M irá regravar o símbolo

atualmente lido a como b ou,
(b) Se b é → ou ←, M moverá sua cabeça na direção b.

Uma vez que δ é uma função, a operação de M é determinística e

irá parar somente quando M entrar em um estado de parada (final).
Note a exigência (a) em δ : Quando vê o final esquerdo da fita ,
ele deve mover-se para a direita. Desse modo, a extremidade 
esquerda nunca é apagada, e M nunca ultrapassa o final esquerdo
de sua fita.

Por (b), M nunca grava um  e, portanto,  é o sinal inequívoco do

final esquerdo da fita.

A função δ não é definida no estado em H; quando a máquina

alcança um estado de parada, sua operação pára.

Exemplo: Considere a máquina de Turing M = (K, Σ , δ , s,

H), onde K = {q0, q1, h}, Σ = {a, ¬, }, s = q0, H ={h}, δ é
dado por:

q σδ (q,
σ )
q0 a (q1,¬)
q0 ¬ (h,¬)
q0  (q0,→)
q1 a (q0,a)
q1 ¬ (q0,→)
q1  (q1,→)

Quando M é iniciado em seu estado inicial q0, move sua

cabeça de leitura para a direita, mudando todos os a’s para
 6

¬’s à medida que trabalha, até encontrar um quadro da fita

que já contém ¬; então pára.

A ação de trocar um símbolo de não espaço em branco pelos

símbolos de espaço em branco será chamada de apagar o
símbolo de não espaço em branco.

Para ser especificada, suponha que M seja iniciada com sua

cabeça varrendo os quatro primeiros a’s, o último dos quais é
seguido por um ¬. Então M irá para trás e para frente, entre os
estados q0 e q1, quatro vezes alternadamente, mudando um
a para um ¬ e movendo a cabeça para a direita.

A primeira e quinta linhas da tabela para δ são uma das mais

relevantes durante essa seqüência de movimentos. Nesse
ponto, M encontrar-se-á no estado q0 varrendo ¬ e, de acordo
com a segunda linha da tabela, irá parar.

Note que a quarta linha da tabela, isto é, o valor δ (q1,a), é

irrelevante uma vez que M nunca pode estar no estado q,
varrendo um a, se ele tiver iniciado no estado q0. Contudo
algum valor deve ser associado com δ (q1,a), já que se exige
que δ seja uma função com domínio K x Σ .

Definição: A configuração da máquina de Turing M = (K, Σ , δ , s,

H) é o membro de K x Σ * x (Σ *(Σ - {¬}) ∪ {ε }).

Isto é, todas as configurações são assumidas como iniciando com o

símbolo de final esquerdo e nunca acabando com um de espaço em
branco a não ser que os espaços em branco estejam sendo
atualmente varridos.

Como exemplos de configurações, temos: (q, a,aba); (h, ¬ ¬

¬,¬a) e (q, ¬ a ¬ ¬,ε ). Por outro lado as seguintes tuplas não são
exemplos de configurações: (q, baa,a,bc¬) e (q,¬aa,ba).

Uma configuração cujo estado componente está em H será

chamada de configuração de parada.
 7

Devemos utilizar uma notação simplificada que representa o

conteúdo da fita (incluindo a posição da cabeça): devemos gravar
wau para o conteúdo da fita na configuração (q,wa,u); o símbolo
sublinhado indica a posição da cabeça.

Além disso, podemos gravar configurações, incluindo o estado junto

com a notação da posição da fita e da cabeça. Isto é, podemos
gravar (q,wa,u) como (q,wau).

Definição: Suponha que M = (K, Σ , δ , s, H) seja a máquina de

Turing e considere duas configurações de M (q1,w1a1,u1) e
(q2,w2a2,u2), onde a1 e a2 ∈ Σ , então,

(q1,w1a1,u1) |-M (q2,w2a2,u2)

Se, e somente se, para algum b ∈ Σ ∪ {→, ←} δ (q1,a1) = (q2,b) e

1. b ∈ Σ , w1 = w2, u1 = u2 e a2 = b, ou
2. b = ←, w1 = w2a2 e
a. u2 = a1u1, se a ≠ ¬ ou u1 ≠ ε , ou
b. u2 = ε se a = ¬ e u1 = ε , ou
3. b = →, w2 = w1a1 e
a. u1 = a2u2, ou
b. u1 = u2 = ε , e a2 = ¬

No caso 1, M regrava um símbolo sem mover a sua cabeça. No

caso 2, M move sua cabeça um quadro para a esquerda; se estiver
se movendo para a esquerda, além dos espaços em branco da fita,
 8

o símbolo de espaço em branco no quadro recém-lido desaparece

da configuração.

No caso 3, M move a sua cabeça um quadro para a direita; se ele

está se movendo para os espaços em branco da fita, um novo
símbolo de espaço em branco surge na configuração como o novo
símbolo varrido.

Note que todas as configurações, exceto para uma das paradas,

resultam exatamente em uma configuração.

Exemplo: Para ilustrar esses casos, suponha que w, u ∈ Σ * onde

u não termina com um ¬ e que a, b ∈ Σ .
Caso 1. δ (q1,a) = (q2,b)
Exemplo: (q1, wau) |-M (q2, wbu)
Caso 2. δ (q1,a) = (q2, ←)
Exemplo para (a): (q1, wbau) |-M (q2, wbau)
Exemplo para (b): (q1, wb¬) |-M (q2, wb)
Caso 3. δ (q1,a) = (q2, →)
Exemplo para (a): (q1, wabu) |-M (q2, wabu)
Exemplo para (b): (q1, wa) |-M (q2, wa¬)

Definição: Para qualquer máquina de Turing M, suponha que |-M*

seja o fechamento transitivo reflexivo de |-M; dizemos que a
configuração C1 resulta na configuração C2 se C1 |-M* C2. Uma
computação por M é uma seqüência de configurações C0, C1,... Cn
para algum n ≥ 0, tal que

C0 |-M C1 |-M C2 |-M ... |-M Cn.

Dizemos que a computação é de comprimento n ou possui n passos

e escrevemos C0 |-Mn Cn.
 9

Exemplo: Considere a máquina de Turing do exemplo da página 5.

Se M é iniciado na configuração (q0,aaaaa), sua computação
seria representada formalmente como segue:

(q0,aaaaa) |-M (q1,¬aaaa)

|-M (q0,¬aaaa)
|-M (q1,¬¬aaa)
|-M (q0,¬¬aaa)
|-M (q1,¬¬¬aa)
|-M (q0, ¬¬¬aa)
|-M (q1, ¬¬¬¬a)
|-M (q0, ¬¬¬¬a)
|-M (q1, ¬¬¬¬¬)
|-M (q0, ¬¬¬¬¬¬)
|-M (h, ¬¬¬¬¬¬)

A computação tem onze passos.

Uma notação para as máquinas de Turing

No sentido de visualizar melhor as máquinas de Turing,

empregaremos uma notação hierárquica na qual máquinas cada
vez mais complexas são construídas a partir de materiais simples.
Para esse fim, devemos definir um repertório muito simples de
máquinas básicas, junto com as regras para combinar
máquinas.

As máquinas básicas

Iniciamos com componentes bem simples: as máquinas de

escrever símbolos e as máquinas de mover cabeças.
 10

Vamos fixar o alfabeto Σ de nossas máquinas. Para cada a ∈ Σ ∪

{←, →} – {}, definimos uma máquina de Turing Ma = ({s, h}, Σ , δ ,
s, {h}), onde para cada b ∈ Σ – {}, δ (s,b) = (h,a). Naturalmente,
δ (s, ) é ainda sempre (s,→).

Isto é, a única coisa que essa máquina faz é realizar a ação a:

gravar a, se a ∈ Σ , movendo na direção indicada por a, se a ∈ {←,
→} e então parar imediatamente. Naturalmente, há uma única
exceção para esse procedimento: se o símbolo lido é um , então
a máquina irá mover-se para a direita.

Como as máquinas de gravar símbolos são utilizadas com tanta

freqüência, abreviamos seus nomes e escrevemos simplesmente a
ao invés de Ma. As máquinas de mover cabeça M← e M→ serão
abreviadas como L (para a esquerda) e R (para a direita).

As regras para combinar máquinas

As máquinas de Turing serão combinadas de um modo sugestivo

da estrutura de um autômato finito. Máquinas individuais são como
os estados de um autômato finito e podem ser conectadas umas às
outras, de modo que os estados de um autômato finito sejam
conectados entre si.

A conexão de uma máquina à outra não é procurada até que a

primeira máquina pare; a outra máquina é então iniciada a partir de
seu estado inicial com a posição da fita e da cabeça como foi
deixada pela primeira máquina.

Assim, se M1, M2 e M3 são máquinas de Turing, a máquina

mostrada na próxima figura opera como segue:

1. Inicie no estado inicial de M1;

2. Opere como M1 operaria até M1 parar;
3. Se o símbolo atualmente lido é um a, inicie M2 e opere como
M2 operaria;
 11

4. Caso contrário, se o símbolo atualmente lido é b, então inicie

M3 e opere como M3 operaria.

M1 M2
a
b

M3

É simples e direto dar uma definição explícita da combinação da

máquina de Turing e de seus constituintes.
No exemplo da figura anterior, suponha que as três máquinas de
Turing M1, M2 e M3 são M1 = (K1, Σ , δ 1, s1, H1), M2 = (K2, Σ , δ 2, s2,
H2) e M3 = (K3, Σ , δ 3, s3, H3). Assumindo que os estados dessas
máquinas são disjuntos, a máquina combinada M1 = (K, Σ , δ , s, H)
seria:

• K = K1 ∪ K2 ∪ K3
• s = s1
• H = H2 ∪ H3
• Para cada σ ∈ Σ e q ∈ K – H, δ (q,σ ) é definida como
segue:
(a) Se q ∈ K1 – H1, então δ (q,σ ) = δ 1(q,σ )
(b) Se q ∈ K2 – H2, então δ (q,σ ) = δ 2(q,σ )
(c) Se q ∈ K3 – H3, então δ (q,σ ) = δ 3(q,σ )
(d) Por fim, se q ∈ H1 (o único caso restante), então δ (q,σ ) =
s2, se σ = a, δ (q,σ ) = s3, se σ = b, e δ (q,σ ) ∈ H, caso
contrário.

Exemplo: A figura a seguir ilustra uma máquina que consiste em

duas cópias de R. A máquina representada por este diagrama move
sua cabeça para a direita um quadro; então se o quadro contém um
a, um b, um  ou um ¬, ela move sua cabeça mais um quadro para
a direita.
 12

b
a, b, ¬, 
R
>R ¬ >R R

Será conveniente representar essa máquina como na figura anterior

mais à direita, isto é, uma seta rotulada com vários símbolos é o
mesmo que várias setas paralelas, uma para cada símbolo.

Se uma seta é rotulada por todos os símbolos no alfabeto Σ das

máquinas, então os rótulos podem ser omitidos. Portanto, se
sabemos que Σ = {a, b, ,¬}, então podemos mostrar a máquina
acima como

R → R,

onde, por convenção, a máquina mais à esquerda é sempre a

inicial. Às vezes uma seta não rotulada, conectando duas máquinas
pode ser inteiramente omitida pela justaposição das representações
das duas máquinas. Sob essa convenção, a máquina anterior torna-
se simplesmente RR ou, ainda, R2.

Exemplo: Se a ∈ Σ é qualquer símbolo, podemos às vezes

eliminar múltiplas setas e rótulos utilizando !a para representar
“qualquer símbolo exceto a”. Portanto, a máquina mostrada na
figura a seguir (mais à esquerda) varre sua fita para a direita, até
encontrar um espaço em branco. Devemos denotar essa máquina
mais útil por R¬.
 13

Outra versão abreviada da mesma máquina da figura anterior (mais

à esquerda) é mostrada na mesma figura mais à direita. Aqui a ≠ ¬
é lido como “qualquer símbolo a que não ¬”.

A vantagem dessa notação é que a pode então ser utilizado em

outra parte no diagrama como o nome de uma máquina. Para
ilustrar, a próxima figura descreve uma máquina que varre para a
direita até encontrar um quadro com espaço não branco e então
copia o símbolo imediatamente para a esquerda de onde ele foi
encontrado.

Exemplo: Máquinas para localizar quadros marcados ou

desmarcados são ilustradas na próxima figura. Elas são as
seguintes:

R¬, o qual encontra os primeiros quadros com espaços em branco

para a direita do quadro atualmente lido.
L¬, o qual encontra o primeiro quadro com espaços em branco para
a esquerda do quadro atualmente lido.
R!¬, o qual encontra o primeiro quadro com espaços não brancos
para a direita do quadro atualmente lido.
L!¬, o qual encontra o primeiro quadro com espaços não brancos
para a esquerda do quadro atualmente lido.
 14

Exemplo: A máquina de copiar C realiza a seguinte função: se C

inicia com entrada w, isto é, se a string w, que contém somente
símbolos de espaço não branco, mas possivelmente vazia, é
colocada de outro modo em uma fita em branco, com um quadro
em branco à esquerda, e a cabeça é colocada no quadro com
espaço em branco à esquerda de w, então a máquina acabará
parando com w¬w em um fita em branco. Dizemos que C
transforma ¬w¬ em ¬w¬w¬.

Um diagrama para C é dado pela figura a seguir:

Exemplo: A máquina de deslocamento para a esquerda S←

transforma ¬w¬, onde w não contém espaços em branco, em w¬.
Ela é ilustrada na figura a seguir:
 15

Computando com máquinas de Turing

Vamos fixar algumas convenções para trabalhar com as máquinas

de Turing.

Primeiro, adotamos a seguinte diretiva para apresentar entradas às

máquinas de Turing: a string de entrada, sem símbolos de espaços
em branco nela, é gravada à direita do símbolo  mais à esquerda,
com um espaço em branco à sua esquerda e espaços em branco à
sua direita; a cabeça é posicionada no quadro da fita que contém os
espaços em branco entre o  e a entrada; e a máquina inicia
operando em seu estado inicial.

Se M = (K, Σ , δ , s, H) é uma máquina de Turing, e w ∈ (Σ –

{¬,})*, então a configuração inicial de M na entrada w é (s,
¬w).

Definição: Suponha que M = (K, Σ , δ , s, H) seja a máquina de

Turing, tal que H={y,n} consiste em dois estados distintos de parada
(y e n para sim e não respectivamente). Qualquer configuração de
parada cujo componente de estado é y é chamada de
configuração de aceitação, enquanto a configuração de parada
cujo estado componente é n é chamada de configuração de
rejeição.

Dizemos que M aceita uma entrada w ∈ (Σ – {¬,})*, se (s, ¬w)

produz uma configuração de aceitação; dizemos que M rejeita w, se
(s, ¬w) produz uma configuração de rejeição.
 16

Suponha que Σ 0 ⊆ Σ – {¬,} seja um alfabeto, chamado alfabeto

de entrada de M; fixando Σ 0 como um subconjunto de Σ – {¬,},
permitimos que nossas máquinas de Turing utilizem símbolos extras
durante sua computação, além daqueles que aparecem em sua
entrada.

Dizemos que M decide a linguagem L ⊆ Σ 0*, se, para qualquer

string w ∈ Σ 0*, o seguinte é verdadeiro: se w ∈ L, então M aceita w;
e se w ∉ L, então M rejeita w.

Por fim, chamamos a linguagem L de recursiva se há uma máquina

de Turing que a decide.

Uma máquina de Turing decide uma linguagem L se, quando

iniciada com a entrada w, ela sempre pára em um estado de parada
que é a resposta correta à entrada: y, se w ∈ L, n, se w ∉ L. Note
que nenhuma garantia é dada quanto ao que acontece se a entrada
para a máquina de Turing contém espaços em branco ou o símbolo
de final esquerdo.

Há um ponto sutil em relação às máquinas de Turing que decidem

linguagens. Com outros reconhecedores de linguagens, uma das
duas situações pode acontecer: ou a máquina aceita a entrada ou a
rejeita. Uma máquina de Turing, por outro lado, mesmo que tenha
somente dois estados de parada, y e n, sempre tem a opção não
responder (sim ou não), falhando em parar.

Dada uma máquina de Turing, ela pode ou não decidir uma

linguagem e não há um modo óbvio de dizer se ela faz isso.

Funções recursivas

Definição: Seja M = (K, Σ , δ , s, {h}) a máquina de Turing; Σ 0 ⊆ Σ

– {¬,}, um alfabeto; e w ∈ Σ 0*. Suponha que M pára na entrada w
e que (s, ¬w) |-M* (h,¬w) para algum y ∈ Σ 0*. Então y é
chamado de saída M na entrada w e é denotada M(w).
 17

Note que M(w) é definido somente se M pára na entrada w e ele, de

fato, faz assim na configuração da forma (h,¬w), com y ∈ Σ 0*.

Agora suponha que f seja qualquer função de Σ 0*. Dizemos que M

computa a função f, se, para todos os w ∈ Σ 0*, M(w) = f(w). Isto é,
para todo w ∈ Σ 0*, M, por fim, pára na entrada w e, quando isso
acontece, sua fita contém a string ¬f(w). Uma função f é chamada
de recursiva, se há uma máquina de Turing M que computa f.

Exemplo: A função κ : ∑* → ∑* definida como κ (w) = ww pode ser

computada pela máquina CS←, isto é, a cópia da máquina seguida
pela máquina de deslocamento à esquerda.

Strings em {0,1}* podem ser utilizadas para representar os inteiros

não-negativos na familiar notação binária. Qualquer string w =
a1a2 ... an ∈ {0,1}* representa o número

num (w) = a1.2n-1 + a2.2n-2 + ... + an.

 18

E qualquer número natural pode ser representado de um único

modo por uma string em 0 ∪ 1 (0 ∪ 1)*, isto é sem zeros
redundantes no início.

De acordo com isso, as máquinas de Turing que computam funções

de {0, 1}* a {0, 1} podem ser pensadas como funções de
computação dos números naturais para os números naturais.

Na verdade, as funções numéricas com muitos argumentos, como

adição e multiplicação, podem ser executadas por máquinas de
Turing para computar funções de {0, 1,;}* para {0, 1}*, onde “;” é um
símbolo utilizado para separar argumentos binários.

Definição: Suponha que M = (K, Σ , δ , s, {h}) seja a máquina de

Turing tal que 0, 1,; ∈ e suponha que f seja qualquer função de Nk
para N para algum k ≥ 1. Dizemos que M computa a função f, se
para todo w1 ... wk ∈ 0 ∪ 1 {0, 1}* (isto é para quaisquer k strings
que são codificações binárias de inteiros), num (M(w1; ...; wk)) =
f(num(w1) ... num(wk)).

Isto é, se M é iniciado com as representações binárias dos inteiros

n1, ..., nk como entrada, então, em algum momento, ele por fim pára
e, quando isso acontece, sua fita contém a string que representa o
número f(n1, ..., nk) –– o valor da função.

Uma função f: Nk → N é chamada de recursiva, se há uma máquina

de Turing M que computa f.

Exemplo: Podemos projetar uma máquina que computa a função

sucessora succ(n) = n + 1 (na próxima figura, SR é a máquina de
deslocamento para a direita). Essa máquina primeiro encontra a
extremidade direita da entrada e então vai para a esquerda,
contanto que veja 1’s mudando todos eles para 0’s.

Quando vê um 0, transforma-o em um 1 e então pára. Se vê um ¬

enquanto procura um 0, isso significa que o número de entrada tem
uma representação binária que é inteiramente composta de 1’s (é
 19

uma potência de dois menos 1) e assim a máquina novamente

grava um 1 no lugar do ¬ e pára após toda a string mudar uma
posição para a direita.

Estritamente falando, a máquina mostrada não computa n + 1,

porque ela falha sempre em parar com a sua cabeça à direita do
resultado, mas isso pode ser corrigido, adicionando uma cópia de
R¬.

0
> R¬L 0

¬ 1
1SR

A observação feita anteriormente sobre a nossa capacidade de

dizer se uma máquina de Turing decide uma linguagem, também se
aplica à função de computação. O preço que devemos pagar para o
amplo intervalo de funções que as máquinas de Turing podem
computar, é que não podemos dizer se uma dada máquina de
Turing de fato computa tal função, isto é, se ela pára em todas as
entradas.

Extensões da máquina de Turing

Estender as máquinas de Turing não implica em criar um outro

modelo para computação que seja mais poderoso do que a
máquina original. Na verdade, a máquina de Turing original é o
modelo computacional definitivo, ou seja, qualquer aplicação feita
por máquinas de Turing estendidas pode ser implementada também
pela máquina de Turing original.

As extensões das máquinas de Turing apenas facilitam a

programação de problemas mais complexos, visto que elas
oferecem recursos de mais alto nível.
 20

Fitas múltiplas

Pode-se pensar que as máquinas de Turing têm várias fitas (ver

próxima figura). Cada fita é conectada ao controle finito por meio de
uma cabeça de leitura/gravação (uma em cada fita). A máquina
pode, em um passo, ler os símbolos lidos por todas as suas
cabeças e, então dependendo de quais símbolos e qual seu estado
atual, regravar alguns dos quadros lidos e mover algumas cabeças
para a esquerda ou para a direita, além de mudar de estado.

Para qualquer inteiro fixo k ≥ 1, uma máquina de Turing de k fitas é

uma máquina de Turing equipada, como anteriormente descrita,
com k fitas e cabeças correspondentes. Portanto, uma máquina de
Turing “padrão” é apenas uma máquina de Turing de k fitas com
k = 1.

Definição: Suponha que k ≥ 1 seja um inteiro. Uma máquina de

Turing de k fitas M é um quíntuplo (K, Σ , δ , s, H), onde K, Σ , s e
H são as definições da máquina de Turing normal e δ , a função de
transição, é a função de (K – H) x Σ k para K x (Σ ∪ { →,←})k.
Isto é, para cada estado q e cada k tuplas de símbolos de fita
(a1, ..., ak), δ (q, (a1, ..., ak)) = (p, (b1, ..., bk)), onde p é, como antes,
o novo estado e bj é, intuitivamente, a ação assumida por M na fita j.
Naturalmente, se aj =  para algum j ≤ k, então bj = →.
 21

.
.
.

q0
h
q1 Controle finito
q3
q2

A computação ocorre em todas as k fitas de uma máquina de Turing

de k fitas. Correspondentemente, uma configuração de tal
máquina deve incluir informações sobre todas as fitas.

Definição: Suponha que M = (K, Σ , δ , s, H) seja a máquina de

Turing de k fitas (Σ exclui ). Uma configuração de M é um
membro de:

K x (Σ * x (Σ *(Σ – {¬}) ∪ {ε }))k

Isto é, a configuração identifica o estado, o conteúdo da fita e a

posição da cabeça em cada k fitas.

Se (q, (w1a1u1, ..., wkakuk)) é uma configuração (excluiu-se ) de

uma máquina de Turing de k fitas (onde utilizamos a versão k vezes
da notação abreviada para configurações) e se δ (q, (a1, ..., ak)) =
(b1, ..., bk), então em um passo, a máquina se moveria para a
 22

configuração (p, (w’1a'1u’1, ..., w’ka’ku’k)), onde para i = 1, ..., k,

w’1a'1u’1 seria w1a1u1 modificada pela ação b1.

Dizemos que (q, (w1a1u1, ..., wkakuk)) produz um resultado em um

passo na configuração (p, (w’1a'1u’1, ..., w’ka’ku’k)).

Exemplo: Adotaremos a convenção de que a string de entrada em

uma máquina de Turing de k fitas é posicionada na primeira fita, do
mesmo modo como ela seria apresentada a uma máquina de Turing
padrão.

As outras fitas são inicialmente espaços em branco, com a cabeça

no espaço em branco mais à esquerda de cada uma. No final de
uma computação, uma máquina de Turing de k fitas está para
deixar a sua saída na sua primeira fita; o conteúdo das outras fitas é
ignorado.

Múltiplas fitas muitas vezes facilitam a construção de uma máquina

de Turing para realizar uma função em particular. Considerando a
máquina de copiar vista anteriormente que transforma ¬w¬ em
¬w¬w¬, onde w ∈ {a, b}*. Uma máquina de Turing de 2 fitas pode
executar isso da seguinte maneira:

(1)Movendo a cabeça de ambas as fitas para a direita, copiando

cada símbolo da primeira na segunda fita, até que um espaço
em branco seja encontrado na primeira fita. O primeiro quadro
da segunda fita deve ser deixado em branco.

(2)Movendo a cabeça na segunda fita para a esquerda até que

um espaço em branco seja encontrado.

(3)Novamente, movendo as cabeças em ambas as fitas para a

direita, dessa vez copiando os símbolos da segunda fita para
a primeira, Pára quando um espaço em branco é encontrado
na segunda fita.

Essa seqüência de ações pode ser representada como segue:

 23

No início: Primeira fita: ¬w

Segunda fita: ¬
Após (1): Primeira fita: ¬w¬
Segunda fita: ¬w¬
Após (2): Primeira fita: ¬w¬
Segunda fita: ¬w
Após (3): Primeira fita: ¬w¬w¬
Segunda fita: ¬w¬

As máquinas de Turing com mais de uma fita podem ser descritas

do mesmo modo que as máquinas de Turing de uma única fita.
Simplesmente anexamos como um sobrescrito ao símbolo
denotando para cada máquina o número da fita em que ela vai
operar; toda as outras fitas não são afetadas.

Por exemplo, ¬2 grava um espaço em branco na segunda fita, L1¬

procura à esquerda um espaço em branco na primeira fita e R1,2
move para a direita as cabeças das fitas 1 e 2. Um rótulo a1 em uma
seta denota uma ação tomada se o símbolo lido na primeira fita for
a. E assim por diante.

Quando representamos as máquinas de Turing de múltiplas fitas,

evitamos empregar a abreviação M2 para MM. A figura a seguir
apresenta a máquina de copiar C com duas fitas.

Fita infinita de duas vias

Suponha agora que a nossa máquina tenha uma fita que é infinita
em ambas as direções. Todos os quadros são inicialmente espaços
e branco, exceto aqueles contendo a entrada; a cabeça fica
inicialmente à esquerda da entrada. Além disso, nossa convenção
com o símbolo  seria desnecessária e sem sentido para tais
máquinas.
 24

Não é difícil ver que, como ocorre com fitas múltiplas, fitas infinitas
de duas vias não representam poder substancial às máquinas de
Turing. Uma fita infinita de duas vias pode ser facilmente simulada
por uma máquina de duas fitas: uma fita sempre contém a parte da
fita à direita do quadro que contém o primeiro símbolo de entrada e
a outra contém a parte da fita à esquerda dessa ao inverso.

A máquina de Turing de duas fitas, por sua vez, pode ser simulada
por uma máquina de Turing padrão. De fato, na simulação,
precisamos levar apenas um tempo linear, em vez de um tempo
quadrático, já que a cada passo, somente uma das trilhas está
ativa. Seria desnecessário dizer, mas as máquinas com várias fitas
infinitas de duas vis também podem ser simuladas do mesmo
modo.

Múltiplas cabeças

O que ocorre se uma máquina de Turing tem uma fita, mas várias
cabeças?

Todas as cabeças lêem os símbolos varridos e movem ou gravam

independentemente. Alguma convenção deve ser adotada sobre o
que acontece quando duas cabeças varrem o mesmo quadro da
fita, ao mesmo tempo em que tentamos gravar diferentes símbolos.
Talvez a cabeça com o número mais baixo ganhe.
 25

Além disso, vamos assumir que as cabeças não possam

compreender cada presença no mesmo quadro da fita, exceto
talvez indiretamente, por meio de gravações malsucedidas.

Não é difícil ver que uma simulação como a que utilizamos para
máquinas de k fitas pode ser realizada para máquinas de Turing
com várias cabeças em uma fita.

A idéia básica é novamente dividir a fita em trilhas, todas as quais

exceto uma, são utilizadas somente para gravar as posições da
cabeça. Para simular um passo computacional pelas máquinas de
múltiplas cabeças, a fita deve ser lida duas vezes: uma para
localizar os símbolos nas posições das cabeças e outra para alterar
esses símbolos ou mover as cabeças apropriadamente. O número
de passos necessários é novamente quadrático.

O uso de múltiplas cabeças, como o de múltiplas fitas, pode às

vezes, simplificar drasticamente a construção de uma máquina de
Turing.

Fita bidimensional

Outro tipo de generalização da máquina de Turing permitiria que

sua fita fosse uma grade bidimensional infinita. Uma poderia até
permitir um espaço de dimensão mais alta. Tal dispositivo pode ser
muito mais útil que as máquinas de Turing padrão para resolver
problemas como um “quebra-cabeça”.

Mais uma vez, entretanto, não resulta nenhum aumenta

fundamental no poder computacional. Curiosamente, o número de
passos necessários para simular t passos das máquinas de Turing
bidimensionais na entrada x pela máquina de Turing normal é
novamente polinomial em t e |x|.

As extensões do modelo da máquina de Turing podem ser

combinadas: pode-se pensar nas máquinas de Turing com várias
fitas, todas ou algumas das quais são de algum modo infinitas de
 26

duas vias e têm mais de uma cabeça nelas ou, ainda, são
multidimensionais.

Novamente, é bastante simples e direto ver que as capacidades da

máquina de Turing, em última instância permanecem as mesmas.
Resumimos nossa discussão sobre as diversas variantes das
máquinas de Turing como segue.

Teorema 1: Qualquer linguagem decidida, semidecidida e qualquer

função computada por máquinas de Turing com várias fitas,
cabeças, fitas infinitas de duas vias ou fitas multidimensionais,
podem ser decididas, semidecidida ou computadas,
respectivamente, pela máquina de Turing padrão.

Convém definir linguagens semidecididas pelas máquinas de

Turing:

Definição: Suponha que M = (K, Σ , δ , s, H) seja a máquina de

Turing, que Σ 0 ⊆ Σ – {¬,} seja um alfabeto e que L ⊆ Σ 0* seja a
linguagem. Dizemos que M semidecide L se, para qualquer string
w ∈ Σ 0*, o seguinte é verdadeiro: w ∈ L se e somente se M pára na
entrada w. Uma linguagem L é enumerável recursivamente se e
somente se há uma máquina de Turing M que semidecide L.

Portanto, quando M é apresentada com a entrada w ∈ L, exige-se

que ela pare no fim. Não nos importaremos com precisamente qual
configuração de parada ela alcança, contanto que ela, por fim,
chegue a uma configuração de parada. Se, entretanto, w ∈ Σ 0* – L,
então M nunca deve entrar no estado de parada.

Máquinas de Turing de acesso aleatório

As máquinas de Turing vistas até o momento possuem como

limitação o fato de se fazer acesso seqüencial à sua memória. Para
alcançar a capacidade de acesso aleatório como os computadores
reais, devemos equipar as máquinas de Turing com registradores
capazes de armazenar e manipular os endereços dos quadros de
uma fita.
 27

Uma máquina de Turing de acesso aleatório tem um número fixo de

registradores e fita infinita de uma via (figura na página 30). Cada
registrador e cada quadro da fita são capazes de conter um número
arbitrário natural.

A máquina age sobre os quadros da sua fita e seus registradores

como determinado por um programa fixo – o análogo da função de
transição das máquinas de Turing normais. O programa de uma
máquina de Turing com acesso aleatório é uma seqüência de
instruções, de um tipo reminiscente do conjunto de instruções reais
para computadores.

Os tipos de instruções permitidos são enumerados na tabela a

seguir:

Instrução Operando Semântica

read j R0 := T[Rj]
write j T[Rj] := R0
store j Rj := R0
load j R0 := Rj
load =c R0 := c
add j R0 := R0 + Rj
add =c R0 := R0 + c
sub j R0 := max{R0 – Rj, 0}
sub =c R0 := max{R0 – c, 0}
half R0 :=  R0 / 2
jump s K := s
jpos s se R0 > 0 então K := s
jzero s se R0 = 0 então K := s
halt K := 0
Notas: j significa o número de registrador, 0 ≤ j < k. T[i] denota o
conteúdo atual do quadro i da fita. Rj denota o conteúdo atual do
registrador j. s ≤ p denota qualquer número de instrução no
 28

programa. c é qualquer número natural. Todas as instruções

alteram K para K + 1, a não ser que seja dito explicitamente de
outro modo.

Inicialmente, o valor dos registradores é 0, o contador de programa

é 1 e o conteúdo da fita codifica a string de entrada de uma maneira
simples que será explicada brevemente.

A máquina executa a primeira instrução do programa. Isso irá

alterar o conteúdo dos registradores ou o conteúdo da fita. Além
disso, o valor do contador de programa K é um inteiro que
identifica a instrução sendo executada.

Note o papel especial do registrador 0: ele é o acumulador, onde

todas as operações aritméticas e lógicas ocorrem. A k-ésima
instrução do programa será executada em seguida e assim por
diante até que uma instrução halt seja executada – nesse ponto a
operação da máquina de Turing de acesso aleatório termina.

Definição: A máquina de Turing de acesso aleatório é o par M = (k,

Π ), onde k > 0 é o número de registradores e Π = (π 1, π 2, …, π p),
o programa, é a seqüência finita de instruções, onde cada
instrução π i é um dos tipos mostrados na tabela anterior.
Assumimos que a última instrução, π p, é sempre a instrução halt (o
programa pode conter outras instruções halt também).

A configuração da máquina de Turing de acesso aleatório (k, Π ) é a

k+2-upla (K, R0, R1, …, Rk-1, T), onde

K ∈ N é o contador de programa, que contém um inteiro entre 0 e

p. A configuração é a configuração de parada se K é zero.

Para cada j, 0 ≤ j < k, Rj ∈ N é o valor atual do registrador j. T, o

conteúdo da fita, é um conjunto finito de pares de inteiros positivos,
isto é, um subconjunto finito de (N – {0}) x (N – {0}) tal que para
todos os i ≥ 1 há, no máximo, um par na forma (i, m) ∈ T.
 29

Intuitivamente, (i, m) ∈ T significa que o i-ésimo quadro da fita

realmente contém o inteiro m > 0. Todos os quadros de fita não
aparecem como os primeiros componentes de um par em T, que
são assumidos como contendo 0.

Suponha que M = (k, Π ) seja o acesso aleatório da máquina.

Dizemos que a configuração C = (k, R0, R1, …, Rk-1, T) de M produz
em um passo a configuração C’ = (k’, R’0, R’1, …, R’k-1, T’) denotada
C |-M C’, se, intuitivamente, os valores de k’, os R’js e o T’ refletem
corretamente a aplicação a k’, os R’js e o T da semântica (da tabela
anterior) da atual instrução π k.

Será detalhada a definição de configuração para apenas uma das

instruções:

Se π k está na forma read j, onde j < k, então a execução dessa

instrução tem o seguinte efeito: o valor contido no registrador 0
torna-se igual ao valor armazenado no quadro número Rj – o quadro
endereçado pelo registrador j.
Isto é, R’0 = T[Rj], onde T[Rj] é o único valor m, tal que (Rj, m) ∈ T,
se tal m existe, e 0, caso contrário. Além disso, K’ = K + 1. Todos os
outros componentes da configuração C’ são idênticos aos de C.

Exemplo: A seqüência de instruções a seguir implementa a

multiplicação em uma máquina de Turing de acesso aleatório. Se o
registrador 0 inicialmente contém um número natural x e o
registrador 1 inicialmente contém y, então a máquina irá parar com
o registrador 0 contendo o produto de xy.

A multiplicação é feita por sucessivas adições, onde a instrução half

é utilizada para revelar a representação binária de y.

1. store 2
2. load 1
3. jzero 20
4. half
 30

5. store 3
6. load 1
7. sub 3
8. sub 3
9. jzero 13
10. load 4
11. add 2
12. store 4
13. load 2
14. add 2
15. store 2
16. load 3
17. store 1
18. load 4
19. jump 2
20. load 4
21. halt

Máquinas de Turing não-determinísticas

Formalmente, uma máquina de Turing não determinística é um

quíntuplo (K, Σ , ∆ , s, H), onde K, Σ , s e H são como as máquinas
de Turing padrão e ∆ é um subconjunto de ((K – H) x Σ ) x (K x (Σ
∪ {←,→})), em vez de uma função de (K – H) x Σ para K x (Σ ∪
{←,→}).

As configurações e as relações |-M e |-M* são definidas de modo

natural, mas agora |-M não precisa ter um único valor: uma
configuração pode produzir várias outras em um passo.
 31

Registradores

R3

k Contador de programa

R2

R1 T[0] T[1] T[2] T[3] T[4] .......

R0

Máquina de Turing de Acesso Aleatório

INDECIDIBILIDADE

A tese de Church-Turing

Vimos no último capítulo que nem todas as máquinas de Turing

merecem ser chamadas de algoritmos, ou seja, máquinas de Turing
que semidecidem lingugens e que, portanto, rejeitam por nunca
parar não são dispositivos computacionais úteis, enquanto as
máquinas de Turing que decidem linguagens e computam funções
(e desse modo param em todas as entradas) o são.

Nossa noção de um algoritmo deve excluir máquinas de Turing que

não podem parar em algumas entradas.

Assim, propomos adotar a máquina de Turing que pára em todas as

entradas como a noção formal precisa correspondente para a
intuitiva idéia de um algoritmo.

Nada será considerado como um algoritmo se não puder ser

reproduzido como uma máquina de Turing, cuja parada é garantida
em todas as entradas e, todas serão chamadas algoritmos.

Esse princípio é conhecido como a tese de Church-Turing. Ela é

uma tese, não um teorema, porque não é um resultado matemático:
ela simplesmente afirma que um certo conceito informal (algoritmo)
corresponde a um certo objeto matemático (máquina de Turing).
 32

Não sendo uma instrução matemática, a tese de Church-Turing não

pode ser provada. Teoricamente é possível, entretanto, que a tese
de Church-Turing possa ser “desprovada” em alguma data no
futuro, se alguém propuser um modelo alternativo de computação
que seja publicamente aceitável como plausível e razoável e que,
ainda, seja comprovadamente capaz de realizar computações que
não podem ser realizadas por qualquer máquina de Turing.
Ninguém considera isso provável.

Adotar uma noção matemática precisa de um algoritmo abre a

intrigante possibilidade de formalmente provarmos que certos
problemas computacionais não podem ser resolvidos por algoritmo
algum.

Máquinas de Turing universais

A base da computação é o hardware ou o software? O formalismo

para algoritmos discutidos até o momento (máquina de Turing)
trata-se de uma peça de hardware “não programável”, especializada
em resolver um problema em particular, com instruções que são
“construídas de fábrica”.

Devemos agora pegar o ponto de vista oposto. Devemos discutir

que máquina de Turing também são software. Isto é, mostrar que
há uma certa máquina de Turing “genérica” que pode ser
programada, mais ou menos da mesma maneira como pode sê-lo
um computador de propósito geral, para solucionar qualquer
problema que pode ser resolvido por máquinas de Turing.

O “programa” que faz essa máquina genérica comportar-se como

uma máquina específica M deve ser uma descrição de M. Em
outras palavras, devemos pensar o formalismo das máquinas de
Turing como uma linguagem de programação na qual podemos
escrever programas.

Programas escritos nessa linguagem podem então ser

interpretados por uma máquina de Turing universal, o que
significa dizer, outro programa na mesma linguagem.

A idéia de um programa gravado em uma linguagem pode

interpretar qualquer programa na mesma linguagem não é uma
idéia muito nova. Ela é a base do método clássico para
processadores de linguagem de “rotina de partida” (bootstraping).
 33

Agora, devemos apresentar um modo geral de especificar as

máquinas de Turing, de modo que suas descrições possam ser
utilizadas como entradas para outras máquinas de Turing, ou seja,
devemos definir uma linguagem cujas strings sejam todas
representações legais das máquinas de Turing.

Um problema já se manifesta sozinho: independentemente do

tamanho do alfabeto que escolhermos para essa representação,
haverá máquinas de Turing que têm mais estados e mais símbolos
de fita.

Evidentemente, devemos codificar estados e símbolos de fita como

strings sobre um alfabeto fixo. Adotamos a seguinte convenção: a
string representando um estado da máquina de Turing tem a forma
{q}{0,1}*; isto é, a letra q, seguida por uma string binária.
Similarmente, um símbolo de fita é sempre representado como uma
string em {a}{0,1}*.

Supondo que M = (K, Σ , δ , s, H) seja uma máquina de Turing e

que i e j sejam os menores inteiros, tal que 2i ≥ |K| e 2j ≥ |Σ | + 2.
Então, cada estado em K será representado como um q seguido por
uma string binária de comprimento i; cada símbolo em Σ será, do
mesmo modo, representado como a letra a seguida por uma string
de j bits.

As direções da cabeça ← e → também serão tratadas como

“símbolos de fita honorários” (eles eram a razão para o termo “+ 2”
na definição de j).

Fixamos as representações dos símbolos especiais ¬, , ← e →

para serem lexicograficamente menores símbolos, respectivamente:
¬ será sempre representado como a0j,  como a0j-1, ← como a0j-210
e → como a0j-211.

O estado inicial será sempre representado como o primeiro estado

lexicográfico, q0i.

Note que queremos o uso de zeros iniciais nas strings que se

seguem aos símbolos a e q, para tornar o comprimento total
compatível com o nível exigido.
 34

Devemos denotar a representação de toda a máquina de Turing M

como “M”, “M” consiste da tabela de transição δ . Isto é, ela é uma
seqüência de strings na forma (q, a, p, b), com q e p representações
de estado e a, b de símbolos, separados por vírgulas e incluídos
entre parênteses.

Adotamos a convenção de que os quádruplos são relacionados em

uma ordem lexicográfica crescente, começando com δ (s,¬).

O conjunto de estados de parada H será determinado indiretamente

pela falta de seus estados como primeiros componentes em
qualquer quádruplo de “M”.

Se M decide uma linguagem e, portanto, H = {y,n}, adotaremos a

convenção de que y é, lexicograficamente, o menor dos dois
estados de parada.

Dessa maneira, qualquer máquina de Turing pode ser

representada. Devemos utilizar o mesmo método para representar
strings no alfabeto da máquina de Turing.

Qualquer string w ∈ Σ * terá uma única representação, também

denotada “w” a saber, a justaposição das representações de seus
símbolos.

Exemplo: Considere a máquina de Turing M = (K, Σ , δ , s, {h}),

onde K = {s, q, h}, Σ = {¬, , a} e δ é dado nessa tabela:

Estado Símbolo δ
s a (q, ¬)
s ¬ (h, ¬)
s  (s, →)
q a (s, a)
q ¬ (s, →)
q  (q, →)

Uma vez que há três estados em K e três símbolos em Σ , temos i =

2 e j = 3. Esses são os menores inteiros, tal que 2i ≥ 3 e 2j ≥ 3 + 2.
Os estados e símbolos são representados como segue:
 35

Estado/ Símbolo Representação

s q00
q q01
h q11
¬ a000
 a001
← a010
→ a011
a a100

Portanto, a representação da string aa¬a é:

“aa¬a” = a001a100a100a000a100.

A representação “M” da máquina de Turing M é a seguinte string:

“M” = (q00, a100, q01, a000), (q00, a000, q11, a000), (q00, a001,
q00, a011), (q01, a100, q00, a011), (q01, a000, q00, a011), (q01,
a001, q01, a011).

Agora estamos prontos para discutir uma máquina de Turing

universal U, que utiliza codificações de outras máquinas como
programas para direcionar sua operação. Intuitivamente, U tem dois
argumentos: uma descrição de uma máquina M, “M” e uma
descrição de uma string de entrada w, “w”.

Queremos que U tenha a seguinte propriedade: U pára na entrada

“M” “w”, se e somente se, M parar na entrada w. Para utilizar a
notação funcional para máquinas de Turing, devemos desenvolver:

U(“M” “w”) = “M(w)”

De fato, descrevemos não uma máquina de uma única fita U, mas

uma máquina de 3 fitas U' intimamente relacionada (então U será a
máquina de Turing de uma única fita que simula U’).

Especificamente, U' utiliza suas três fitas como segue: a primeira

contém a codificação do conteúdo da fita atual de M; a segunda
contém a codificação do próprio M; e a terceira fita contém a
 36

codificação do estado de M no atual ponto da computação

simulada.

A máquina U' é iniciada com alguma string “M” “w” em sua primeira
fita e as outras duas fitas com espaços em branco (não importa
como U’ se comporta, se sua string de entrada não está nessa
forma).

Primeiro U' move “M” na segunda fita e desloca “w” para baixo, para
o final esquerdo da primeira fita, precedendo-a com “¬”. Portanto,
nesse ponto a primeira fita contém “¬w”.

U' grava na terceira fita a codificação do estado inicial s de M,

sempre q0i (U' pode facilmente determinar i e j, examinando “M”).

Agora U' passa a simular os passos da computação de M. Entre

esses passos simulados, U' manterá as cabeças da segunda e
terceira fitas nos seus finais esquerdos, e a cabeça da primeira fita
varre o a da versão codificada do símbolo que M estaria varrendo
no tempo correspondente.

U' simula um passo de M como segue: ele varre sua segunda fita
até encontrar um quádruplo cujo primeiro componente corresponde
ao estado codificado gravado em sua terceira fita e cujo segundo
componente corresponde ao símbolo codificado lido na primeira fita.

Se encontrar esse quádruplo, ele muda o estado para o terceiro

componente desse quádruplo e realiza na primeira fita a ação
sugerida pelo quarto componente.

Se o quarto componente codifica um símbolo do alfabeto da fita de

M, esse símbolo é gravado na primeira fita.

Se o quarto componente é a0j-210, (a codificação de ←), então U'

move sua primeira cabeça para o primeiro símbolo a à esquerda e,
se for a codificação de →, para a direita. Se um ¬ é encontrado, U'
deve convertê-lo para a0j, o código de um espaço em branco de M.

Se em algum passo a combinação de estado-símbolo não é

encontrada na segunda fita, isso significa que o estado é um estado
de parada.
 37

U’ também pára em um estado apropriado. Isso completa nossa

descrição da operação de U’.

O problema da parada

Suponha que você tenha gravado um programa em sua linguagem

de programação favorita, que realiza o seguinte feito notável: pega
como entrada qualquer programa P, gravado na mesma linguagem,
e uma entrada X desse programa.

Utilizando alguma engenhosa análise, seu programa sempre

determina corretamente se o programa P irá parar na entrada X (ele
retorna “sim” se isso acontece) ou se ele iria executar eternamente
(ele retorna “não”).

Você chamou esse programa de halts (P, X).

Este é um programa inestimável. Ele descobre todos os tipos de

bugs sutis que fazem outros programas executar eternamente em
certas entradas.

Utilizando esse programa, você pode conduzir com êxito muitas

coisas notáveis. Eis um exemplo relativamente sutil: você pode
utilizá-la para escrever outro programa, com o nefasto nome de
diagonal (X) (lembrando-se da prova por diagonalização, constata-
se que 2N não é contável):

diagonal (X)
a : se halts (X, X), então vá para a, senão pare

Note o que diagonal (X) faz: se seu programa halts decide que o
programa X iria parar se lhe fosse apresentado ele próprio como
entrada, então diagonal (X) faz um loop sem fim; caso contrário,
ele pára.

E agora vem a questão inexplicável: a função diagonal (diagonal)

pára?

Ela pára se, e somente se, a chamada halts (diagonal, diagonal)

retorna “não”; em outras palavras, pára se, e somente se, ela não
parar.
 38

Isso é uma contradição: devemos concluir que a única hipótese com

que iniciamos esse caminho é falsa, que o programa halts (P, X)
não existe.

Isto é, não pode haver programa ou algoritmo para resolver o

problema que halts resolveria: dizer se programas arbitrários iriam
parar ou entrar em loop.

Esse tipo de argumento deve ser familiar não apenas pela sua
experiência com ciências da computação, mas também pela cultura
geral do século XX.

A questão é que agora introduzimos toda a parafernália necessária

para apresentar uma versão formal, matematicamente rigorosa,
desse paradoxo. Temos uma completa notação para algoritmos, um
tipo de “linguagem de programação”: a máquina de Turing.

De fato, na última seção introduzimos uma nova característica de

que precisamos: desenvolvemos uma estrutura que permite a
nossos “programas” manipular outros programas e suas entradas –
exatamente como o nosso o fictício halts (P, X) faz.

Já estamos prontos, portanto, para definir uma linguagem que não é

recursiva e provar que ela não o é. Suponha que:

H = {“M” “w”: a máquina de Turing M pára na string de entrada w}.

Note primeiro que H é enumerável recursivamente: ela é

precisamente a linguagem semidecidida por nossa máquina de
Turing universal U na seção anterior.

De fato, na entrada “M” “w”, U pára precisamente quando a entrada

está em H.

Além disso, se H é recursiva, então cada linguagem enumerável

recursivamente é recursiva. Em outras palavras, H tem a chave
para a pergunta que fizemos no capítulo anterior, se todas as
linguagens enumeráveis recursivamente são também decidíveis por
Turing: a resposta é positiva se, e somente se H é recursiva.

Para tanto, suponha que H é de fato decidida por alguma máquina

de Turing M0. Então, dada qualquer máquina de Turing M particular
 39

que semidecide uma linguagem L(M), podemos projetar uma

máquina de Turing M' que decide L(M) como segue:

Primeiro, M' transforma sua fita de entrada de ¬w¬ para para

“M” “w”¬ e, então, simula M0 nessa entrada. Por hipótese, M0
decidirá corretamente se M aceita w ou não.

Podemos dizer que há reduções de todas as linguagens

enumeráveis recursivamente para H e, portanto, H é completo para
a classe de linguagens enumeráveis recursivamente.

Mas podemos mostrar, formalizando o argumento para halts (P, X)

acima, que H não é recursiva. Primeiro, se H fosse recursiva, então:

H1 = {“M”: a máquina de Turing M pára na string de entrada "M”}

Também seria recursiva. (H1 significa a parte halts (X, X) do

programa diagonal.).

Se existisse uma máquina de Turing M0 que pudesse decidir H,

então uma máquina de Turing M1 que decidisse H, necessitaria, tão
somente, transformar sua string de entrada ¬”M”¬ em ¬“M” “M”
¬ e, então, passar o controle para M0. Portanto, é suficiente mostrar
que H1 não é recursiva.

Segundo, se H1, fosse recursiva, então seu complemento também

seria recursivo:

!H1 = {w: ou w não é a codificação de uma máquina de Turing ou w

é a codificação de “M” de uma máquina de Turing M que não pára
em “M”}.

Isso é assim, porque a classe de linguagens recursivas é fechada

sob complemento. Incidentalmente, !H1 é a linguagem diagonal,
análoga ao nosso programa diagonal e o último ato da prova.

Mas !H1, não pode mesmo ser enumerável recursivamente –

supondo que sozinho seja recursivo. Vamos supor que M* estava
em uma máquina de Turing que semidecide !H1. Está “M*” em !H1?

Por definição de !H1, “M*” ∈ !H1, se, e somente se, M* não aceita a
string de entrada “M*”. Mas M* é suposto para semidecidir !H1,
assim, “M*” ∈ !H1, se, e somente se, M* aceita “M*”. Temos
 40

concluído que M* aceita “M*” se, e somente se, M* não aceita “M*”.
Isso é absurdo, assim como a suposição de que M0 existe deve ter
sido um erro.
Vamos resumir o desenvolvimento desta seção. Queríamos
descobrir se cada linguagem enumerável recursivamente é
recursiva. Observamos que isso seria verdadeiro se e somente se,
a particular linguagem enumerável recursivamente H fosse
recursiva.

De H derivamos, em dois passos, a linguagem !H1, a qual tem de

ser recursiva a fim de que H seja recursiva. Mas a suposição de que
!H1 é recursiva conduz a uma contradição lógica, por
diagonalização. Provamos, desse modo, o seguinte e mais
importante teorema:

Teorema: A linguagem H não é recursiva; portanto, a classe de

linguagens recursivas é um estrito subconjunto da classe das
linguagens enumeráveis recursivamente.

Tínhamos dito anteriormente que esse argumento é uma instância

do princípio de diagonalização que pode ser utilizado para mostrar
que 2N não é contável.

Para ver por que e para sublinhar mais uma vez a essência da
prova, vamos definir uma relação binária R em strings sobre o
alfabeto utilizando a codificação de máquinas de Turing: (u, w) ∈ R
se e somente se u = “M” para alguma máquina de Turing M que
aceita w. (R é uma versão de H.) Agora, supondo que, para cada
string u,

Ru = {w: (u, w) ∈ R}

os Ru's correspondem às linguagens enumeráveis recursivamente)

e considerando a diagonal de R, isto é,

D = {w: (w, w) ∉ R}

(D é !H1), pelo princípio da diagonalização, D ≠ Ru para todo u; isto

é, !H1, é uma linguagem diferente de qualquer linguagem
enumerável recursivamente.
 41

E por que D ≠ Ru para qualquer u? Porque D difere, exatamente

pela sua construção, de cada Ru (e, portanto, de cada linguagem
enumerável recursivamente) no mínimo uma string – a saber, u.

O Teorema anterior responde negativamente à primeira das duas

questões que apresentamos no capítulo anterior (“cada linguagem
enumerável recursivamente também é recursiva?” e “a classe de
linguagens enumeráveis recursivamente é fechada sob
complemento?”).

Mas a mesma prova fornece a resposta para a outra questão. É

fácil ver que !H1, como H, é enumerável recursivamente, e
mostramos que !H1, não é enumerável recursivamente. Portanto,
também provamos o seguinte resultado:

Teorema: A classe de linguagens enumeráveis recursivamente não

é fechada sob complemento.

Problemas indecidíveis sobre máquinas de Turing

Provamos um resultado momentâneo. Vamos voltar um pouco e ver

o que ele diz no nível intuitivo, à luz da tese de Church-Turing.

Uma vez que a prova estabelece que H não é recursiva e aceitamos

o princípio de que qualquer algoritmo pode ser convertido em uma
máquina de Turing que pára em todas as entradas, devemos
concluir que não há algoritmo que decida, para uma dada arbitrária
máquina de Turing M e a string de entrada w, se M aceita w ou não.

Os problemas para os quais não existem algoritmos são chamados

de indecidíveis ou insolúveis. O problema indecidível mais
famoso e fundamental é o de dizer se uma dada máquina de Turing
pára em uma dada entrada – cuja indecidibilidade acabamos de
estabelecer.

Esse problema é geralmente chamado de problema de parada

para máquinas de Turing.

Note que a indecidibilidade do problema de parada não implica de

modo algum que não possam haver algumas circunstâncias em que
seja possível prever se uma máquina de Turing irá parar em uma
string de entrada.
 42

No capítulo anterior, fomos capazes de concluir que uma certa

máquina simples está limitada a nunca parar em uma determinada
entrada.

Ou podemos examinar a transição da tabela da máquina de Turing,

por exemplo, para verificar se um estado de parada é representado
em qualquer lugar; em caso negativo, a máquina não pode parar
em nenhuma string de entrada.

Essa e outras análises mais complexas podem ter algum resultado

– uma informação útil para certos casos; mas nosso teorema afirma
que qualquer análise desse tipo deve, em última instância, ser
inconclusiva ou produzir um resultado incorreto: não há um método
completamente geral que decida corretamente todos os casos.

Uma vez que estabelecemos, por diagonalização, que os problemas

de parada são indecidíveis, segue-se a indecidibilidade de uma
grande variedade de problemas. Esses resultados são provados
não por outras diagonalizações, mas por reduções: mostramos em
cada caso que se alguma linguagem L2 fosse recursiva, então
também seria assim alguma linguagem L1, já conhecida como não
sendo recursiva.

Definição: Supondo que L1, L2 ⊆ Σ * sejam linguagens. Uma

redução de L1 para L2 é a função recursiva τ : Σ * → Σ *, tal que
x ∈ L1 se, e somente se, τ (x) ∈ L2.

Deve-se ter cuidado para entender a “direção” em que uma redução

será aplicada. Para mostrar que uma linguagem L2 não é recursiva,
devemos identificar uma linguagem L1, que é conhecida por não ser
recursiva e, então, reduzir L1 para L2.

Reduzir L2 para L1 não levaria a nada: simplesmente mostraria que

L2 pode ser decidido, se podemos decidir L1 – o que sabemos ser
impossível.

Formalmente, o uso correto de reduções em provas de

indecidibilidade é o seguinte:

Teorema: Se L1 não é recursiva e há uma redução de L1 para L2,

então L2 também não é recursiva.
 43

Prova: Suponha que L2 seja recursiva, digamos, decidida pela

máquina de Turing M2, e que T seja a máquina de Turing que
computa a redução τ . Então, a máquina de Turing TM2 iria decidir
L1. Mas L1 é indecidível – uma contradição.

A seguir, usaremos reduções para mostrar que vários problemas

sobre máquinas de Turing são indecidíveis.

Teorema: Os seguintes problemas sobre máquinas de Turing são

indecidíveis:

(a) Dada uma máquina de Turing M e uma string de entrada w,

como fazemos M parar na entrada w?
(b)Dada uma máquina de Turing M, como fazer M parar na fita
vazia?
(c) Dada uma máquina de Turing M, há alguma string em que M
pára?
(d) Dada uma máquina de Turing M, como fazemos M parar em
cada string de entrada?
(e) Dadas duas máquinas de Turinq M1 e M2; elas param na
mesma string de entrada?
(f) Dada uma máquina de Turing M, a linguagem que M
semidecide é regular? É Livre de contexto? É recursiva?
(g) Há uma certa máquina fixa M, para a qual o seguinte
problema é indecidível: dado w, como fazer M parar em w?

Prova: A parte (a) foi provada na seção anterior.

(b) Descrever uma redução de H para a linguagem

L = {“M”: M pára em ε }.

Dada a descrição de uma máquina de Turing M e uma entrada x,

nossa redução simplesmente constrói a descrição de uma máquina
de Turing Mw, que opera como segue: Mw. quando começada na fita
vazia (isto é. na configuração (s, ¬)), grava w em sua fita e, então,
inicia para simular M. Em outras palavras, se w = a,..., a n, então Mw
é simplesmente a máquina

Ra1Ra2R... RanL¬M.
 44

E é fácil ver que a função τ que mapeia “M” “w” para “Mw” é de fato
recursiva.

(c) Podemos reduzir a linguagem L, mostrada como não recursiva

na Parte (b), para a linguagem L' = {“M”: M pára em alguma
entrada}, como segue. Dada a representação de qualquer máquina
de Turing M, nossa redução constrói a representação de uma
máquina de Turing M' que apaga qualquer entrada que lhe é dada e
então simula M na string vazia.

Claramente, M' pára em alguma string se, e somente se, ele pára
em todas as strings e se, e somente se, M pára na string vazia.

(d) O argumento para a Parte (c) funciona bem aqui, uma vez que
M’ é construído para aceitar alguma entrada se, e somente se,
aceitar cada entrada.

(e) Devemos reduzir o problema na Parte (d) a este. Dada a

descrição de uma máquina M, nossa redução constrói a string

τ (“M”) = "M” “y",

onde “y” é a descrição da máquina que imediatamente aceita

qualquer entrada. Claramente, as duas máquinas, M e y, aceitam as
mesmas entradas se, e somente se, M aceita todas as entradas.

(f) Reduzimos o problema na Parte (b) acima para apresentar outro.

Mostramos como modificar qualquer máquina de Turing M para
obtermos uma máquina de Turing M’, tal que M' pára nas strings em
H, ou em nenhuma string, dependendo de M parar na string vazia
ou não.

Uma vez que não há algoritmo para dizer se M pára na string vazia,
pode não haver algum para dizer se L(M) é ∅ (que é regular, livre
de contexto e recursivo) ou H (que não é nenhum das três).

Primeiro, M' salva sua string de entrada e inicia qualquer coisa que
M faria na entrada ε . Quando e se M parar, M’ restaura sua
entrada e realiza sobre ela a operação da máquina de Turing
universal U.
 45

Portanto, M' não pára na entrada, porque nunca termina de imitar M

na entrada ε , ou pára precisamente nas strings em H.

(g) A máquina fixa M0, a que aludimos na instrução do teorema, é

precisamente a de Turing universal U.

Problemas insolúveis de gramática

Problemas insolúveis não ocorrem somente no domínio das

máquinas de Turing, mas em virtualmente todos os campos da
matemática. Por exemplo, há vários problemas indecidíveis
relacionados com gramáticas, resumidos abaixo.

Teorema: Cada um dos seguintes problemas é indecidível.

(a) Para uma dada gramática G e string w, determinar se w ∈

L(G).
(b) Para uma dada gramática G, determinar se ε ∈ L(G).
(c) Para duas dadas gramáticas G1 e G2, determinar se L(G1) =
L(G2).
(d) Para uma gramática arbitrária G, determinar se L(G) = ∅.
(e) Além disso, há uma certa gramática fixa G0, tal que ela é
indecidível para determinar se qualquer dada string w está em
L(G0).

Teorema: Uma linguagem é gerada por uma gramática se e

somente se ela é enumerável recursivamente.

O teorema anterior estabelece que as gramáticas têm o mesmo

poder que as máquinas de Turing, a indecidibilidade resultante
acima provavelmente não aparece como uma surpresa.

O que é mais surpreendente, entretanto, é que questões similares

sobre gramática livre de contexto e sistemas relacionados – um
domínio relativamente simples e limitado – são indecidíveis.

Naturalmente, os problemas indecidíveis não incluem dizer se w ∈

L(G) ou se L(G) = ∅ – esses problemas podem ser resolvidos por
algoritmos e de fato são eficientes. Vários outros problemas, porém,
não são solúveis.
 46

COMPLEXIDADE COMPUTACIONAL

Problemas intratáveis ou difíceis são comuns na natureza e nas

áreas do conhecimento. Problemas “fáceis” são resolvidos por
algoritmos polinomiais. Problemas “difíceis” somente possuem
algoritmos exponenciais para resolvê-los.

A complexidade de tempo da maioria dos problemas é polinomial ou

exponencial.

Polinomial: função de complexidade é O(p(n)), onde p(n) é um

polinômio.

Exemplo: algoritmos com pesquisa binária (O(log n)), pesquisa

seqüencial (O(n)), ordenação por inserção (O(n2)) e multiplicação de
matrizes (O(n3)).

Exponencial: função de complexidade é O(cn), c > 1.

Exemplo: problema do caixeiro viajante (PCV) que é (O(n!)).

Mesmo problemas de tamanho pequeno a moderado não podem

ser resolvidos por algoritmos não polinomiais.

Problemas NP-Completo

A teoria de complexidade a ser apresentada não mostra como obter

algoritmos polinomiais para problemas que demandam algoritmos
exponenciais, nem afirma que não existem. É possível mostrar que
 47

os problemas para os quais não há algoritmo polinomial conhecido

são computacionalmente relacionados.

Formam a classe conhecida como NP.

Um problema da classe NP poderá ser resolvido em tempo

polinomial se e somente se todos os outros problemas em NP
também puderem.

Este fato é um indício forte de que dificilmente alguém será capaz

de encontrar um algoritmo eficiente para um problema da classe
NP.

Classe NP - Problemas “Sim/Não”

Para o estudo teórico da complexidade de algoritmos considera-se

problemas cujo resultado da computação seja “sim” ou “não”.

Versão do Problema do Caixeiro Viajante (PCV) cujo resultado é do

tipo “sim/não”:

Dados: uma constante k, um conjunto de cidades C = {c1, c2, ..., cn}

e uma distância d(ci, cj) para cada par de cidades ci, cj ∈ C.
Questão: Existe um “roteiro” para todas as cidades em C cujo
comprimento total seja menor ou igual a k?

Característica da classe NP: problemas “sim/não” para os quais

uma dada solução pode ser verificada facilmente. A solução pode
ser muito difícil ou impossível de ser obtida, mas uma vez
conhecida ela pode ser verificada em tempo polinomial.

Algoritmos Não Determinísticos

Nos algoritmos determinísticos o resultado de cada operação é

definido de forma única. Em um arcabouço teórico, é possível
remover essa restrição.
 48

Apesar de parecer irreal, este é um conceito importante e

geralmente utilizado para definir a classe NP. Neste caso, os
algoritmos podem conter operações cujo resultado não é definido
de forma única.
Um algoritmo não determinístico é capaz de escolher uma dentre as
várias alternativas possíveis a cada passo. Algoritmos não
determinísticos contêm operações cujo resultado não é unicamente
definido, ainda que limitado a um conjunto especificado de
possibilidades.

Função escolhe (C)

Algoritmos não determinísticos utilizam uma função escolhe (C),

que escolhe um dos elementos do conjunto C de forma arbitrária. O
comando de atribuição X ← escolhe (1:n) pode resultar na atribuição
a X de qualquer dos inteiros no intervalo [1, n].

A complexidade de tempo para cada chamada da função escolhe é

O(1). Neste caso, não existe nenhuma regra especificando como a
escolha é realizada.

Se um conjunto de possibilidades leva a uma resposta, este

conjunto é escolhido sempre e o algoritmo terminará com sucesso.
Por outro lado, um algoritmo não determinístico termina sem
sucesso se e somente se não há um conjunto de escolhas que
indica sucesso.

Comandos sucesso e insucesso

Algoritmos não determinísticos utilizam também dois comandos, a

saber:

• insucesso: indica término sem sucesso.

• sucesso: indica término com sucesso.
 49

Os comandos insucesso e sucesso são usados para definir uma

execução do algoritmo. Esses comandos são equivalentes a um
comando de parada de um algoritmo determinístico.

Os comandos insucesso e sucesso também têm complexidade de

tempo O(1).

Máquina Não Determinística

Uma máquina capaz de executar a função escolhe admite a

capacidade de computação não determinística. Uma máquina não
determinística é capaz de produzir cópias de si mesma quando
diante de duas ou mais alternativas e continuar a computação
independentemente para cada alternativa.

A máquina não determinística que acabamos de definir não existe

na prática, mas ainda assim fornece fortes evidências de que certos
problemas não podem ser resolvidos por algoritmos determinísticos
em tempo polinomial, conforme mostrado na definição da classe
NP-completo à frente.

Pesquisa Não Determinística

Pesquisar o elemento x em um conjunto de elementos A[1 : n],

n ≥ 1.

procedure PesquisaND (A, 1 , n) ;

begin
j ← escolhe(A,1 ,n)
if A[ j ] = x then sucesso else insucesso;
end;

Determina um índice j tal que A[j] = x para um término com sucesso

ou então insucesso quando x não está presente em A. O algoritmo
 50

tem complexidade não determinística O(1). Para um algoritmo

determinístico a complexidade é Ω (n).

Ordenação Não Determinística

Ordenar um conjunto A[1 : n] contendo n inteiros positivos, n ≥ 1.

procedure OrdenaND (A, 1 , n) ;

begin
for i := 1 to n do B[i] := 0;
for i := 1 to n do
begin
j ← escolhe(A,1 ,n) ;
if B[j] = 0 then B[j] := A[i] else
insucesso;
end;
end;

Um vetor auxiliar B[1:n] é utilizado. Ao final, contém o conjunto em

ordem crescente. A posição correta em B de cada inteiro de A é
obtida de forma não determinística pela função escolhe. Em
seguida, o comando de decisão verifica se a posição B[j] ainda não
foi utilizada.

A complexidade é O(n). Para um algoritmo determinístico a

complexidade é Ω (n log n).

Problema da Satisfabilidade

Considere um conjunto de variáveis booleanas x1, x2, ··· , xn , que

podem assumir valores lógicos verdadeiro ou falso. A negação de
xi é representada por !xi.
 51

Uma expressão booleana é composta de variáveis booleanas e

operações ou (v) e e (^). Também chamadas respectivamente de
adição e multiplicação.

Uma expressão booleana E contendo um produto de adições de

variáveis booleanas é dita estar na forma normal conjuntiva. Dada
E na forma normal conjuntiva, com variáveis xi, 1 ≤ i ≤ n, existe
uma atribuição de valores verdadeiro ou falso às variáveis que torne
E verdadeira (“satisfaça”)?

Exemplo:
E1 = (x1 v x2) ^ (x1 v !x3 v x2) ^ (x3) é satisfatível para (x1 = F, x2 = V,
x3 = V). A expressão E2 = x1 ^ !x1 não é satisfatível.

O algoritmo AvalND (E, n) verifica se uma expressão E na forma

normal conjuntiva, com variáveis xi, 1 ≤ i ≤ n, é satisfatível.

procedure AvalND (E, n) ;

begin
for i := 1 to n do
begin
xi ← escolhe (true, false);
if E(x1, x2, ···, xn) = true then sucesso
else insucesso;
end;
end;

O algoritmo obtém uma das 2n atribuições possíveis de forma não

determinista em O(n). Melhor algoritmo determinístico: O(2n).
Aplicação em definição de circuitos elétricos combinatórios que
produzam valores lógicos como saída e sejam constituídos de
portas lógicas e, ou e não.
 52

Neste caso, o mapeamento é direto, pois o circuito pode ser

descrito por uma expressão lógica na forma normal conjuntiva.

Caracterização das Classes P e NP

P: conjunto de todos os problemas que podem ser resolvidos por

algoritmos determinísticos em tempo polinomial.

NP: conjunto de todos os problemas que podem ser resolvidos por

algoritmos não determinísticos em tempo polinomial.

Para mostrar que um determinado problema está em NP, basta

apresentar um algoritmo não determinístico que execute em tempo
polinomial para resolver o problema. Outra maneira é encontrar um
algoritmo determinístico polinomial para verificar que uma dada
solução é válida.

Existe Diferença entre P e NP?

P ⊆ NP, pois algoritmos determinísticos são um caso especial dos

não determinísticos. A questão é se P = NP ou P ≠ NP. Esse é o
problema não resolvido mais famoso que existe na área da ciência
da computação.

Se existem algoritmos polinomiais determinísticos para todos os

problemas em NP, então P = NP. Por outro lado, a prova de que
P = NP parece exigir técnicas ainda desconhecidas.

Descrição tentativa do mundo NP, em que a classe P está contida

na classe NP.
 53

Acredita-se que NP >> P, pois para muitos problemas em NP, não

existem algoritmos polinomiais conhecidos, nem um limite inferior
não polinomial provado.

NP ⊃ P ou NP = P? – Conseqüências

Muitos problemas práticos em NP podem ou não pertencer a P (não

conhecemos nenhum algoritmo determinístico eficiente para eles).
Se conseguirmos provar que um problema não pertence a P, então
não precisamos procurar por uma solução eficiente para ele.

Como não existe tal prova, sempre há esperança de que alguém

descubra um algoritmo eficiente. Quase ninguém acredita que
NP = P. Existe um esforço considerável para provar o contrário,
mas a questão continua em aberto.

Transformação Polinomial

Sejam Π 1 e Π 2 dois problemas “sim/não”. Suponha que um

algoritmo A2 resolva Π 2. Se for possível transformar Π 1 em Π 2 e a
solução de Π 2 em solução de Π 1, então A2 pode ser utilizado para
resolver Π 1.

Se pudermos realizar as transformações nos dois sentidos em

tempo polinomial, então Π 1 é polinomialmente transformável em
Π 2.
 54

Esse conceito é importante para definir a classe NP-completo.

Para mostrar um exemplo de transformação polinomial, definiremos
clique de um grafo e conjunto independente de vértices de um
grafo.

Conjunto Independente de Vértices de um Grafo

O conjunto independente de vértices de um grafo G = (V, E) é

constituído do subconjunto V’ ⊆ V, tal que v, w ∈ V’ ⇒ (v, w) ∉ E.
Todo par de vértices de V’ é não adjacente (V’ é um subgrafo
totalmente desconectado).

Exemplo: cardinalidade 4: V’ = {0, 2, 1, 6}.

Para mostrar um exemplo de transformação polinomial, definiremos

clique de um grafo e conjunto independente de vértices de um
grafo.
 55

Em problemas de dispersão é necessário encontrar grandes

conjuntos independentes de vértices. Procura-se um conjunto de
pontos mutuamente separados.

Como exemplo de aplicação, pode-se citar a identificação de

localizações para instalação de franquias. Duas localizações não
podem estar perto o suficiente para competirem entre si.

A solução seria construir um grafo em que possíveis localizações

são representadas por vértices e arestas são criadas entre duas
localizações que estão próximas o suficiente para interferir. O maior
conjunto independente fornece o maior número de franquias que
podem ser concedidas sem prejudicar as vendas. Em geral,
conjuntos independentes evitam conflitos entre elementos.

Clique de um grafo

Clique de um grafo G = (V, E) é constituído do subconjunto V’ ⊆ V,

tal que v, w ∈ V’ ⇒ (v, w) ∈ E. Todo par de vértices de V’ é
adjacente (V’ é um subgrafo completo).

Exemplo: cardinalidade 3: V’ = {3, 1, 4}.

O problema de identificar agrupamentos de objetos relacionados

freqüentemente se reduz a encontrar grandes cliques em grafos.
Como exemplo pode-se citar uma empresa de fabricação de peças
 56

por meio de injeção plástica que fornece para diversas outras

empresas montadoras.

Para reduzir o custo relativo ao tempo de preparação das máquinas

injetoras, pode-se aumentar o tamanho dos lotes produzidos para
cada peça encomendada. É preciso identificar os clientes que
adquirem os mesmos produtos, para negociar prazos de entrega
comuns e assim aumentar o tamanho dos lotes produzidos.
Uma solução seria construir um grafo com cada vértice
representando um cliente e ligar com uma aresta os que adquirem
os mesmos produtos. Um clique no grafo representa o conjunto de
clientes que adquirem os mesmos produtos.

Considere Π 1 o problema clique e Π 2 o problema conjunto

independente de vértices. A instância I de clique consiste de um
grafo G = (V, E) e um inteiro k > 0. A instância f(I) de conjunto
independente pode ser obtida considerando-se o grafo
complementar !G de G e o mesmo inteiro k. f(I) é uma
transformação polinomial:

1. !G pode ser obtido a partir de G em tempo polinomial.

2. G possui clique de tamanho ≥ k se e somente se !G possui
conjunto independente de vértices de tamanho ≥ k.

Se existe um algoritmo que resolve o conjunto independente em

tempo polinomial, ele pode ser utilizado para resolver clique
também em tempo polinomial. Diz-se que clique ∝ conjunto
independente.

Denota-se Π 1 ∝ Π 2 para indicar que Π 1 é polinomialmente

transformável em Π 2. A relação ∝ é transitiva (Π 1 ∝ Π 2 e Π 2 ∝ Π 3
⇒ Π 1 ∝ Π 3).

Problemas NP-Completo e NP-Difícil

Dois problemas Π 1 e Π 2 são polinomialmente equivalentes se e

somente se Π 1 ∝ Π 2 e Π 2 ∝ Π 1.
 57

Exemplo: Problema da satisfabilidade. Se SAT ∝ Π 1 e Π 1 ∝ Π 2,

então SAT ∝ Π 2.

Um problema Π é NP-difícil se e somente se SAT ∝ Π

(satisfabilidade é redutível a Π ).
Um problema de decisão Π é denominado NP-completo quando:

1. Π ∈ NP;
2. Todo problema de decisão Π ’ ∈ NP-completo satisfaz
Π’∝Π.

Um problema de decisão Π que seja NP-difícil pode ser mostrado

ser NP-completo exibindo um algoritmo não determinístico
polinomial para Π . Apenas problemas de decisão (“sim/não”)
podem ser NP-completo.

Problemas de otimização podem ser NP-difícil, mas geralmente, se

Π 1 é um problema de decisão e Π 2 um problema de otimização, é
bem possível que Π 1 ∝ Π 2. A dificuldade de um problema NP-difícil
não é menor do que a dificuldade de um problema NP-completo.

Exemplo: Problema da Parada é um problema NP-difícil que não é

NP-completo. Consiste em determinar, para um algoritmo
determinístico qualquer A com entrada de dados E, se o algoritmo A
termina (ou entra em um loop infinito).

Mostrando que SAT ∝ problema da parada:

• Considere o algoritmo A cuja entrada é uma expressão

booleana na forma normal conjuntiva com n variáveis.
• Basta tentar 2n possibilidades e verificar se E é satisfatível.
• Se for, A pára; senão, entra em loop.
• Logo, o problema da parada é NP-difícil, mas não é NP-
completo.
 58

Teorema de Cook

Existe algum problema em NP tal que se ele for mostrado estar

em P, implicaria P = NP?
Teorema de Cook: Satisfabilidade (SAT) está em P se e somente
se P = NP, ou seja, se existisse um algoritmo polinomial
determinístico para satisfabilidade, então todos os problemas em
NP poderiam ser resolvidos em tempo polinomial.

A prova considera os dois sentidos:

1. SAT está em NP (basta apresentar um algoritmo não

determinístico que execute em tempo polinomial). Logo, se
P = NP, então SAT está em P.

2. Se SAT está em P, então P = NP. A prova descreve como

obter de qualquer algoritmo polinomial não determinístico de
decisão A, com entrada E, uma fórmula Q (A, E) de modo que
Q é satisfatível se e somente se A termina com sucesso para
E. O comprimento e tempo para construir Q é O(p3(n) log(n)),
onde n é o tamanho de E e p(n) é a complexidade de A.

Prova de que um Problema é NP-Completo

São necessários os seguintes passos:

1. Mostre que o problema está em NP.

2. Mostre que um problema NP-completo conhecido pode ser

polinomialmente transformado para ele.

É possível porque Cook apresentou uma prova direta de que SAT é

NP-completo, além do fato de a redução polinomial ser transitiva
(SAT ∝ Π 1 e Π 1 ∝ Π 2 ⇒ SAT ∝ Π 2).
 59

Para ilustrar como um problema Π pode ser provado ser

NP-completo, basta considerar um problema já provado ser
NP-completo e apresentar uma redução polinomial desse problema
para Π .