Informática Teórica
Engenharia da Computação
REDUTIBILIDADE

Uma redução é uma maneira de converter um
problema em outro
FORMA 1 - REDUTIBILIDADE

A  B ( A se reduz a B)

Resolver A não pode ser mais difícil que resolver B

Se B for decidível A tb será.

Se A for indecidível, B tb será.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO

O método da história de computação é uma técnica
importante para provar que AMT é redutível a certas
linguagens.
 Esse método é muito útil quando o problema a ser
mostrado como indecidível envolve testar a existência
de algo.
 Por exemplo, a indecidibilidade do 10º problema de
Hilbert: testar a existência de raízes inteiras em um
polinômio.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO


A história de computação para uma MT sobre uma
entrada é a seqüência de configurações pelas
quais MT passa a medida em que ela processa a
entrada.
Registro completo da computação de MT.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO
DEFINIÇÃO:
 Seja M uma MT e w uma cadeia de entrada.
 Uma história de computação de aceitação para M
sobre w é uma seqüência de configurações, C1,
C2,...,Cl, onde:
– C1 é a configuração inicial de M sobre w,
– Cl é uma configuração de aceitação de M, e
– Cada Ci segue de Ci-1 conforme as regras de M.

Uma história de computação de rejeição para M
sobre w é definida similarmente, exceto que Cl é de
rejeição.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO



Histórias de computação são seqüências finitas.
Se M não para sobre w, nenhuma história de
computação de aceitação ou de rejeição existe para M
sobre w.
MTs determinísticas têm no máximo uma história de
computação sobre qualquer entrada.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO
DEFINIÇÃO:
 Um autômato linearmente limitado (ALL) é um tipo
restrito de MT na qual a cabeça de leitura-escrita não
pode se mover para fora da parte da fita contendo a
entrada.
 Se a máquina tentar mover sua cabeça para além de
qualquer das extremidades da entrada, a cabeça
permanece onde está.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO

Um autômato linearmente limitado (ALL) é uma MT
com uma quantidade limitada de memória.
 Ele só pode resolver problemas que requerem
memória que possa caber dentro da fita usada para a
entrada. Usar um alfabeto de fita maior que o alfabeto
de entrada permite que a memória disponível seja
incrementada de no máximo um fator constante.
 Logo, dizemos que para uma entrada de comprimento
n, a quantidade de memória disponível é linear em n.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO





ALLs são poderosos.
AAFD, AGLC, VAFD e VGLC são ALLs.
Toda LLC pode ser decidida por um ALL
AALL é o problema de se determinar se um ALL aceita
sua entrada. Muito embora AALL seja o mesmo que o
problema indecidível AMT onde a MT é um ALL,
podemos mostrar que AALL é decidível.
AALL = {<M,w> | M é um AALL que aceita a cadeia w}
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO
LEMA:
 Seja M um ALL com q estados e g símbolos no
alfabeto da fita. Existem exatamente 𝑞𝑛𝑔𝑛
configurações distintas de M para uma fita de
comprimento n, já que:
– M tem q estados.
– O comprimento de sua fita é n,
 então a cabeça pode estar em uma das n posições,
– e 𝑔𝑛 cadeias posíveis de símbolos de fita aparecem
sobre a fita.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO
TEOREMA:
 AALL é decidível.
 IDÉIA DA PROVA: Para decidir se a ALL M aceita a
entrada w, simulamos M sobre w.
 Durante a simulação, se M para e aceita ou rejeita,
 aceitamos ou rejeitamos.
 A dificuldade ocorre se M entra em loop sobre w.
Precisamos ser capazes de detectar a entrada em
loop de modo que possamos parar e rejeitar.
 A idéia de detectar quando M está em loop é que, à
medida em que M computa sobre w, ela vai de
configuração em configuração.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO
TEOREMA:
 IDÉIA DA PROVA: Se M repetir uma configuração ela
continuaria a repeti-la e estaria em loop.
 Em razão de M ser um ALL, a quantidade de fita
disponível para ela é limitada. Pelo Lema mostrado, M
pode estar em apenas um número limitado de
configurações sobre essa quantidade de fita.
 Consequentemente, apenas uma quantidade limitada
de tempo está disponível para M antes que ela entre
em alguma configuração previamente visitada.
 Detectar que M está em loop é possível simulando M
pelo número de passos dado pelo Lema.
 Se M não parou então, ela tem que estar em loop.
REDUTIBILIDADE
TEOREMA 5.9: AALL é decidível.


1.
2.
L é um decisor para AALL :
L = Sobre a entrada <M,w> onde M é um ALL, e w é
uma cadeia:
Simule m sobre w por 𝑞𝑛𝑔𝑛 passos ou até parar;
Se M parou :
1. aceite se aceitou, e
2. rejeite se rejeitou.
3.
Se não parou, rejeite.
REDUTIBILIDADE
TEOREMA 5.9: AALL é decidível.
L
M
M,w
w
qaceita
qrejeita
Se o no. de config.
de M > q.n.gn
Aceita
Rejeita
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO

O Teorema 5.9 mostra que ALLs e MTs diferem de
uma maneira essencial: Para ALLs o problema da
aceitação é decidível, mas para MTs não.
 Entretanto, certos outros problemas envolvendo ALLs
permanecem indecidíveis.
 Um deles é o problema da vacuidade:
 VALL = {<M> | M é um ALL onde L(M) =∅}.

Para provar que VALL é indecidível, damos uma
redução que usa o método da história de computação.
REDUTIBILIDADE
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO
TEOREMA:
 VALL é indecidível.
 IDÉIA DA PROVA: Essa prova é por redução a partir
de AMT. Mostraremos que se VALL fosse decidível, AMT
também seria.
 Suponha que VALL seja decidível.
 Para uma MT M e uma entrada w podemos determinar
se M aceita w construindo um certo ALL B e então
testar se L(B) é vazia.
 A linguagem que B reconhece compreende todas as
histórias de computação de aceitação para M sobre w.
REDUÇÕES VIA HISTÓRIAS DE COMPUTAÇÃO
VALL é indecidível.

Se M não aceita w, essa linguagem é vazia. Se
pudermos determinar se a linguagem de B é vazia,
podemos determinar se M aceita w.
 Agora descrevemos como construir B a partir de M e w.
 Note que precisamos mostrar mais que a mera
existência de B.
 Temos que mostrar como uma MT pode obter uma
descrição de B, dadas descrições de M e w.
 Construímos B para aceitar sua entrada x se x é uma
história de computação de aceitação para M sobre w.
 Uma HC de aceitação é a sequência de configurações,
C1, C2,...,Ci pela qual M passa quando aceita w.
REDUTIBILIDADE
TEOREMA 5.10: VALL é indecidível.

Esta HC pode ser vista como uma só cadeia:

Funcionamento: quando ALL B recebe uma entrada x,
espera-se que B aceite se x for uma computação de
aceitação para M sobre w.
Primeiro, B quebra x, conforme os delimitadores, em
cadeias C1, C2,...,Ci.

REDUTIBILIDADE
TEOREMA 5.10: VALL é indecidível.

Então B determina se Ci satisfaz às 3 condições de
uma HC de aceitação:
 1. C1 é a configuração inicial para M sobre w.
 2. Cada Ci+1 legitimamente segue de Ci.
 3. Ci é uma configuração de aceitação para M.
 A configuração inicial C1 para M sobre w é a cadeia
q0w1w2... wn.
 B tem essa cadeia diretamente embutida, de modo
que ela é capaz de verificar a primeira condição.
 Uma configuração de aceitação é aquela que contem
o estado de aceitação qaceita, portanto B pode verificar
a 3ª condição procurando por qaceita em Ci.
REDUTIBILIDADE
TEOREMA 5.10: VALL é indecidível.

A 2ª condição é a mais difícil de verificar.
 Para cada par de configurações adjacentes, B verifica
se Ci+1 segue de Ci. Esse passo envolve verificar que
Ci e Ci+1 são idênticas exceto pelas posições sob e
adjacentes à cabeça em Ci. Essas posições têm que
ser atualizadas conforme a função de transição de M.
 Então B verifica se a atualização foi feita
apropriadamente zigue-zagueando entre posições
correspondentes de Ci e Ci+1. Para manter o registro
das posições correntes durante o zigue-zague, B
marca a posição corrente com pontos sobre a fita.
REDUTIBILIDADE
TEOREMA 5.10: VALL é indecidível.

Finalmente, se as condições 1, 2 e 3 são satisfeitas, B
aceita sua entrada.
 Note que o ALL B não é construído para rodar sobre
alguma entrada. Construimos B apenas para alimentar
uma descrição de B no decisor para VALL .
 Uma vez que esse decisor retorne sua resposta
podemos invertê-la para obter a resposta a se M
aceita w.
 Portanto, poderíamos decidir AMT, uma contradição!
REDUTIBILIDADE
B é um ALL que aceita a HC de aceitação de w por M
B
x
Q. C1C2...Cl
x
C1 =
q0w1...wn
Não
Sim
Cl contem
qaceita
Não
Sim
Ci+1 segue
de Ci
Sim
qA
Não
qR
REDUTIBILIDADE
TEOREMA 5.10: VALL é indecidível.

PROVA: Agora estamos prontos para enunciar a
redução de AMT para VALL .
 Suponha que MT R decide VALL . Construa MT S que
decide AMT da seguinte forma.
 S = “Sobre a entrada <M,w>, com M MT e w cadeia:
 1. Construa o ALL B a partir de M e w conforme
descrito na ideia da prova.
 2. Rode R sobre a entrada <B>.
 3. Se R rejeita, aceite; se R aceita, rejeite.
REDUTIBILIDADE
TEOREMA 5.10: VALL é indecidível.

Se R aceita <B>, então L(B) =∅.

Portanto, M não tem nenhuma HC de aceitação sobre
w e M não aceita w.
Consequentemente, S rejeita <M,w>.




Similarmente, se R rejeita <B>, a linguagem de B é
não-vazia. A única cadeia que B pode aceitar é uma
HC de aceitação para M sobre w.
Portanto, M deve aceitar w.
Consequentemente, S aceita <M,w>.
REDUTIBILIDADE
TEOREMA 5.10: VALL é indecidível.
S
Aceita
M,w
M,w Construção
do ALL B
B
R
qrejeita
Rejeita
qaceita
Rejeita
Aceita
REDUTIBILIDADE
TEOREMA 5.10: VALL é indecidível.