Aula5 Redutibilidade[still]

Prévia do material em texto

Redutibilidade
Ma´rio S. Alvim
(msalvim@dcc.ufmg.br)
Fundamentos de Teoria da Computac¸a˜o (FTC)
DCC-UFMG
(2018/01)
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 1 / 46
Redutibilidade: Introduc¸a˜o
Ate´ agora neste curso ja´:
1. Estabelecemos a ma´quina de Turing como nosso modelo de computac¸a˜o.
E, pela Tese de Church-Turing, aceitamos que este e´ o modelo definitivo de
computac¸a˜o.
2. Mostramos que existe pelo menos um problema (o problema da parada) que
na˜o tem soluc¸a˜o neste modelo de computac¸a˜o.
Portanto, aceitamos que o problema da parada e´ computacionalmente
insolu´vel (ou indecid´ıvel).
Entretanto, ha´ muitos outros problemas indecid´ıveis.
Mas nem sempre queremos mostrar que um problema e´ indecid´ıvel de
maneira direta, como fizemos com o problema da parada.
Aqui vamos introduzir o conceito de redutibilidade, que e´ essencial em cieˆncia
da computac¸a˜o.
Em particular, a redutibilidade pode ser usada para provar que problemas sa˜o
indecid´ıveis (ou decid´ıveis).
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 2 / 46
Redutibilidade
Reduzir um problema A a um problema B significa mostrar que
se temos uma soluc¸a˜o para o problema B,
enta˜o temos uma soluc¸a˜o para o problema A.
Em outras palavras, reduzir o problema A ao problema B significa que uma
soluc¸a˜o para B pode ser utilizada para solucionar tambe´m A.
Usamos naturalmente o conceito de redutibilidade no dia a dia.
1 O problema de matar a nossa fome pode ser reduzido ao problema de
encontrar um restaurante para comer.
2 O problema de encontrar um restaurante para comer pode ser reduzido ao
problema de procurar restaurantes num buscador na Internet.
3 O problema de saber o que foi dado na aula de FTC pode ser reduzido ao
problema de se acessar o programa da disciplina.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 3 / 46
Redutibilidade
O conceito de redutibilidade pode ser usado para mostrar que problemas teˆm
ou na˜o teˆm soluc¸a˜o.
Se um problema A e´ redut´ıvel a um problema B, enta˜o sabemos que:
1. Se B e´ decid´ıvel, enta˜o A tambe´m e´ decid´ıvel.
Isso porque a soluc¸a˜o de B pode ser usada para solucionar A.
2. Se A e´ indecid´ıvel, enta˜o B e´ indecid´ıvel.
Isso porque se houvesse soluc¸a˜o para B, haveria tambe´m soluc¸a˜o para A, o
que e´ uma contradic¸a˜o.
Assim, para mostrar que um problema P e´ indecid´ıvel, basta mostrar que um
problema Q que sabemos ser indecid´ıvel e´ redut´ıvel a P.
Por exemplo, para mostrar que o problema da correspondeˆncia de Post e´
indecid´ıvel, basta reduzir o problema da parada a ele.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 4 / 46
Redutibilidade
Mas atenc¸a˜o! A redutibilidade tem que ser usada com cuidado!
Se um problema A e´ redut´ıvel a um problema B, note o seguinte.
3. Se A e´ decid´ıvel, isso na˜o significa que B e´ decid´ıvel!
Isso porque a soluc¸a˜o de B pode ser usada para solucionar A, mas B pode ser
muito mais dif´ıcil que A (i.e., B ainda pode ser indecid´ıvel).
4. Se B e´ indecid´ıvel, isso na˜o significa que A e´ indecid´ıvel!
De novo, isso acontece porque a soluc¸a˜o de B pode ser usada para solucionar
A, mas B pode ser muito mais dif´ıcil que A (i.e., B ainda pode ser indecid´ıvel).
Assim, para mostrar que um problema P e´ indecid´ıvel, na˜o adianta mostrar
que P se reduz a um problema indecid´ıvel Q!
Por exemplo, para mostrar que o problema da correspondeˆncia de Post e´
indecid´ıvel, na˜o adianta reduzi-lo ao problema da parada!
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 5 / 46
Problemas Indecid´ıveis e
Teoria de Linguagens
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 6 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
Agora vamos dar exemplos de prova de indecidibilidade usando o conceito de
redutibilidade.
Nas nossas provas vamos poder usar o fato de que ja´ determinamos que
algum problema em espec´ıfico e´ indecid´ıvel.
Em particular, vamos comec¸ar usando o fato que ja´ determinamos que o
problema de aceitac¸a˜o para MTs
AMT = {〈M,w〉 | M e´ uma MT e M aceita w}.
e´ indecid´ıvel.
Vamos enta˜o provar que va´rios problemas de linguagens sa˜o indecid´ıveis.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 7 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
Algumas vezes nos referimos a AMT como o “problema da parada”, pore´m,
estritamente falando, o problema da parada e´ a linguagem
PARAMT = {〈M,w〉 | M e´ uma MT e M pa´ra sobre a entrada w}.
Teorema PARAMT e´ indecid´ıvel.
Prova.
Por contradic¸a˜o.
Suponha que PARAMT seja decid´ıvel.
Enta˜o existe uma MT R que decide PARAMT, e poder´ıamos usar R para
construir uma MT S que decide a linguagem AMT da seguinte forma.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 8 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
Prova. (Continuac¸a˜o)
S = “Sobre a entrada 〈M,w〉, uma codificac¸a˜o de uma MT M e de uma
cadeia w :
1. Rode a MT R sobre a entrada 〈M,w〉.
2. Se R rejeita, rejeite.
3. Se R aceita, simule M sobre w ate´ que ela pare.
4. Se M aceitou, aceite; se M rejeitou, rejeite.”
Mas note que se R e´ capaz de decidir PARAMT, enta˜o claramente S e´ um
decisor para AMT.
Mas isto e´ uma contradic¸a˜o, pois ja´ determinamos que AMT e´ indecid´ıvel.
Logo conclu´ımos que PARAMT e´ indecid´ıvel.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 9 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
O problema da vacuidade para MTs concerne a seguinte linguagem:
VMT = {〈M〉 | M e´ uma MT e L(M) = ∅}.
Este e´ o problema de se decidir se a linguagem reconhecida por uma MT e´
vazia.
Teorema VMT e´ indecid´ıvel.
Prova.
Por contradic¸a˜o.
Suponha que VMT seja decid´ıvel.
Enta˜o existe uma MT R que decide VMT, e podemos usar R para construir
uma MT S para decidir a linguagem AMT da seguinte forma.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 10 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
Prova. (Continuac¸a˜o)
Primeiro vamos mostrar como, dada uma MT arbitra´ria M e uma cadeia
arbitra´ria w , podemos sempre construir uma MT auxiliar Mw tal que:
L(Mw ) =
{
{w}, se M aceita w ,
∅, se M na˜o aceita w .
Mais precisamente, dados MT M e cadeia w , a MT auxiliar Mw e´:
Mw = “Sobre a entrada x :
1. Se x 6= w , rejeite.
2. Se x = w , rode M sobre a entrada w e aceite se M aceita w .”
Note que Mw e´ constru´ıda de tal forma que
L(Mw ) 6= ∅ se, e somente se, M aceita w ,
portanto, se tivermos um decisor para VMT, teremos um decisor para AMT.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 11 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
Prova. (Continuac¸a˜o)
Agora, sabendo que podemos construir a MT Mw sempre que necessa´rio,
provemos um decisor S para AMT.
S = “Sobre a entrada 〈M,w〉, consistindo na codificac¸a˜o de uma MT M e de
uma cadeia w :
1. Use a descric¸a˜o de M e w para construir a MT auxiliar Mw que se comporta
como M sobre w , e rejeita toda cadeia x 6= w .
2. Rode R sobre a entrada Mw .
3. Se R aceita, rejeite; se R rejeita, aceite.”
Se R fosse um decisor para VMT, enta˜o S seria um decisor para AMT.
Como ja´ determinamos que um decisor para AMT na˜o pode existir, VMT deve
tambe´m ser indecid´ıvel.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 12 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
O problema da regularidade para MTs concerne a seguinte linguagem:
REGULARMT = {〈M〉 | M e´ uma MT e L(M) e´ uma linguagem regular}.
Este e´ o problema de se decidir se dada uma MT, existeum AF equivalente a
ela.
Teorema REGULARMT e´ indecid´ıvel.
Prova.
Por contradic¸a˜o.
Suponha que REGULARMT seja decid´ıvel.
Enta˜o existe uma MT R que decide REGULARMT, e podemos usar R para
construir uma MT S para decidir a linguagem AMT da seguinte forma.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 13 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
Prova. (Continuac¸a˜o)
Primeiro vamos mostrar como, dada uma MT arbitra´ria M e uma cadeia
arbitra´ria w , podemos sempre construir uma MT auxiliar M ′w tal que:
L(M ′w ) =
{
Σ∗, se M aceita w ,
{0n1n | n ≥ 0}, se M na˜o aceita w .
Note que como {0n1n | n ≥ 0} na˜o e´ regular mas Σ∗ e´, sabemos que
L(M ′w ) sera´ regular se, e somente se, M aceita w .
Portanto, reduzimos o problema de decidir se M aceita w ao problema de
decidir se L(M ′w ) e´ regular.
Usando esta observac¸a˜o acima, usar o decisor R de REGULARMT para
construir a seguinte MT S decisora para AMT.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 14 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
Prova. (Continuac¸a˜o)
S = “Sobre a entrada 〈M,w〉, uma codificac¸a˜o de uma MT M e de uma
cadeia w :
1. Construa a seguinte MT M ′w :
M ′w = “Sobre a entrada x :
1. Se x tem a forma 0n1n, aceite.
2. Se x na˜o tem a forma 0n1n, rode M sobre a entrada w e aceite se M aceita w .”
2. Rode a MT R sobre a entrada M ′w .
3. Se R aceita, aceite; se R rejeita, rejeite.”
Claramente, se R e´ capaz de decidir REGULARMT, enta˜o S e´ um decisor
para AMT.
Mas isto e´ uma contradic¸a˜o, pois AMT e´ indecid´ıvel.
Logo conclu´ımos que REGULARMT tambe´m deve ser indecid´ıvel.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 15 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
O problema da equivaleˆncia de MTs concerne a seguinte linguagem:
EQMT = {〈M1,M2〉 | M1 e M2 sa˜o uma MTs e L(M1) = L(M2)}.
Este e´ o problema de se decidir se duas MTs reconhecem a mesma linguagem.
Teorema EQMT e´ indecid´ıvel.
Prova.
Por contradic¸a˜o.
Suponha que EQMT seja decid´ıvel.
Enta˜o existe uma MT R que decide EQMT, e podemos usar R para construir
uma MT S para decidir a linguagem VMT da seguinte forma.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 16 / 46
Problemas Indecid´ıveis e Teoria de Linguagens
Prova. (Continuac¸a˜o)
S = “Sobre a entrada 〈M〉, onde M e´ uma MT:
1. Rode a MT R sobre a entrada 〈M,MV 〉, onde MV e´ uma MT que rejeita
todas as entradas.
2. Se R aceita, aceite; se R rejeita, rejeite.”
Note que L(MV ) = ∅.
Logo, ao decidir se uma MT M de entrada e´ equivalente a MV , a ma´quina S
esta´ decidindo VMT.
Mas isto e´ uma contradic¸a˜o, pois VMT e´ indecid´ıvel.
Como S so´ e´ capaz de decidir VMT porque usa o decisor R para EQMT,
conclu´ımos que tal decisor R na˜o pode existir, e EQMT tambe´m deve ser
indecid´ıvel.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 17 / 46
Redutibilidade por
Mapeamento
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 18 / 46
Redutibilidade por Mapeamento
Ate´ agora mostramos como usar a te´cnica de redutibilidade para demonstrar
que va´rios problemas sa˜o indecid´ıveis.
Pore´m, ainda formalizamos o conceito de “redutibilidade”.
Faremos isso agora, o que nos permitira´ fazer demonstrac¸o˜es mais refinadas,
incluindo:
Mostrar que linguagens na˜o sa˜o Turing-reconhec´ıveis.
(Isto e´ uma aplicac¸a˜o de reduc¸a˜o a` Teoria de Linguagens.)
Mostrar resultados relativos a` complexidade de algoritmos.
(Isto e´ uma aplicac¸a˜o de reduc¸a˜o a` Teoria de Complexidade.)
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 19 / 46
Redutibilidade por Mapeamento
O conceito de redutibilidade pode ser formalizado de va´rias formas
equivalentes.
Aqui adotamos a de “redutibilidade por mapeamento” (ou “redutibilidade
muitos-para-um”).
A ideia central e´ que ser capaz de reduzir um problema A a um problema B
usando reduc¸a˜o por mapeamento significa que existe uma “func¸a˜o
computa´vel” que converte instaˆncias do problema A em instaˆncias do
problema B.
Se tivermos a func¸a˜o de conversa˜o, que e´ denominada “reduc¸a˜o”, podemos
resolver A usando um solucionador para B: basta converter a instaˆncia
desejada de A em uma instaˆncia de B e enta˜o resolver a instaˆncia de B.
Para tornar a ideia acima precisa, vamos primeiro definir o conceito de
“func¸a˜o computa´vel”.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 20 / 46
Func¸o˜es computa´veis
Uma func¸a˜o f : Σ∗ → Σ∗ e´ uma func¸a˜o computa´vel se alguma ma´quina de
Turing M, sobre toda entrada w , pa´ra com exatamente f (w) sobre sua fita.
Exemplo 1 As operac¸o˜es usuais sobre inteiros (+, −, ×, /, etc.) sa˜o todas
computa´veis.
Por exemplo, e´ fa´cil ver que podemos construir uma MT que recebe a
entrada 〈m, n〉 e retorna m + n, a soma de m e n.
�
Exemplo 2 Func¸o˜es computa´veis podem ser transformac¸o˜es de descric¸o˜es
de ma´quinas. Por exemplo, uma func¸a˜o computa´vel f pode tomar uma
cadeia w e retornar a descric¸a˜o 〈M ′〉 de uma MT tal que, se w = 〈M〉 for a
codificac¸a˜o de uma MT M, enta˜o M ′ e´ uma MT equivalente a M mas que
nunca tenta mover sua cabec¸a para ale´m da extremidade esquerda da fita. A
func¸a˜o retorna � se w na˜o for a codificac¸a˜o de uma MT va´lida. �
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 21 / 46
Redutibilidade por mapeamento: definic¸a˜o formal
A linguagem A e´ redut´ıvel por mapeamento a` linguagem B, escrito
A ≤m B,
se existe uma func¸a˜o computa´vel f : Σ∗ → Σ∗, onde para toda cadeia w ,
w ∈ A ⇔ f (w) ∈ B.
A func¸a˜o f e´ denominada a reduc¸a˜o de A para B.
Uma reduc¸a˜o por mapeamento de A para
B proveˆ uma maneira de converter questo˜es
do tipo
“w ∈ A?′′
em questo˜es do tipo
“f (w) ∈ B?′′
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 22 / 46
Redutibilidade por mapeamento: definic¸a˜o formal
O seguinte teorema diz que se um problema for redut´ıvel por mapeamento a
outro problema previamente resolvido, enta˜o temos uma soluc¸a˜o para o
problema original.
Teorema Se A ≤m B e B e´ decid´ıvel, enta˜o A e´ decid´ıvel.
Prova.
Seja M ser um decisor para B e f a func¸a˜o de reduc¸a˜o de A para B. Enta˜o a
MT N abaixo e´ um decisor para A:
N = “Sobre a entrada w :
1. Compute f (w).
2. Rode M sobre a entrada f (w) e deˆ como sa´ıda o que M der como sa´ıda.”
Note que w ∈ A sse f (w) ∈ B, ja´ que f e´ uma reduc¸a˜o de A para B. Logo
M aceita f (w) sse w ∈ A, e portanto N e´ um decisor para A.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 23 / 46
Redutibilidade por mapeamento: definic¸a˜o formal
O seguinte corola´rio do teorema anterior tem sido nossa principal ferramenta
provar indecidibilidade de problemas.
Corola´rio Se A ≤m B e A e´ indecid´ıvel, enta˜o B e´ indecid´ıvel.
Prova.
Este resultado e´ apenas o contrapositivo do resultado anterior.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 24 / 46
Redutibilidade por mapeamento: Exemplo
Exemplo 3 Em um resultado anterior usamos uma reduc¸a˜o de AMT para
mostrar que PARAMT e´ indecid´ıvel.
Aqui vamos revisitar este problema evidenciando a reduc¸a˜o por mapeamento
implicitamente utilizada.
A reduc¸a˜o mostrou como um decisor para PARAMT pode ser usado para dar
um decisor para AMT.
Podemos exibir uma reduc¸a˜o por mapeamento de AMT para PARAMT dando
uma func¸a˜o computa´vel f que toma qualquer entrada da forma 〈M,w〉 e
retorna uma entrada da forma 〈M ′,w〉 onde
〈M,w〉 ∈ AMT se, e somente se, 〈M ′,w〉 ∈ PARAMT.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) RedutibilidadeDCC-UFMG (2018/01) 25 / 46
Redutibilidade por mapeamento: Exemplo
Prova. (Continuac¸a˜o)
A seguinte ma´quina F computa a func¸a˜o f .
F = “Sobre a entrada 〈M,w〉:
1. Construa a seguinte MT M ′.
M ′ = “Sobre a entrada x :
1. Rode M sobre x .
2. Se M aceita, aceite.
3. Se M rejeita, entre em loop.”
2. Deˆ como sa´ıda 〈M ′,w〉.”
Note que quando a cadeia de entrada 〈M,w〉 na˜o esta´ bem formada (e,
portanto, na˜o pertence a AMT), a MT F produz uma cadeia 〈M ′,w〉 que na˜o
pertence a PARAMT.
Logo, F computa um mapeamento correto de AMT para PARAMT.
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 26 / 46
Redutibilidade por mapeamento
A redutibilidade por mapeamento e´ sens´ıvel ao complemento, i.e.,
w ∈ A⇒ f (w) ∈ B e w /∈ A⇒ f (w) /∈ B.
Isto pode ser usado para provar na˜o-reconhecibilidade de linguagens.
Teorema Se A ≤m B e B e´ Turing-reconhec´ıvel, enta˜o A e´
Turing-reconhec´ıvel.
Prova. Seja M um reconhecedor para B, e f a func¸a˜o de reduc¸a˜o de A para
B. Enta˜o a MT N abaixo e´ um reconhecedor para A:
N = “Sobre a entrada w :
1. Compute f (w).
2. Rode M sobre a entrada f (w) e deˆ como sa´ıda o que M der como sa´ıda (se M
parar).”
Note que w ∈ A se f (w) ∈ B, ja´ que f e´ uma reduc¸a˜o de A para B. Logo M
aceita f (w) se w ∈ A, e portanto N e´ um reconhecedor para A.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 27 / 46
Redutibilidade por mapeamento
Corola´rio Se A ≤m B e A na˜o e´ Turing-reconhec´ıvel, enta˜o B na˜o e´
Turing-reconhec´ıvel.
Prova.
Este resultado e´ apenas o contrapositivo do resultado anterior.
Note que pela definic¸a˜o de redutibilidade por mapeamento,
A ≤m B significa o mesmo que A ≤m B.
Isto ocorre porque
w ∈ A⇔ f (w) ∈ B significa o mesmo que w ∈ A⇔ f (w) ∈ B.
Logo, o corola´rio acima implica que para mostrar que B na˜o e´ reconhec´ıvel,
podemos mostrar que AMT ≤m B, uma vez que:
1. AMT ≤m B e´ o mesmo que AMT ≤m B; e
2. sabemos que AMT na˜o e´ Turing-reconhec´ıvel.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 28 / 46
Redutibilidade por mapeamento
O pro´ximo resultado ilustra que podemos tambe´m usar a redutibilidade por
mapeamento para mostrar que certos problemas na˜o sa˜o
Turing-reconhec´ıveis, nem co-Turing reconhec´ıveis.
Teorema EQMT na˜o e´ Turing-reconhec´ıvel, nem co-Turing-reconhec´ıvel.
Prova. A prova tem duas partes.
Primeiro mostramos que EQMT na˜o e´ Turing-reconhec´ıvel.
Para tal, mostramos que AMT e´ redut´ıvel a EQMT.
(O que o mesmo que mostrar que AMT e´ redut´ıvel a EQMT.)
A seguinte MT F computa a func¸a˜o redutora f de AMT para EQMT.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 29 / 46
Redutibilidade por mapeamento
Prova. (Continuac¸a˜o)
F = “ Sobre a entrada 〈M,w〉, onde M e´ uma MT e w e´ uma cadeia:
1. Construa as seguintes ma´quinas M1 e M2:
M1 = “Sobre qualquer entrada:
1. Rejeite.”
M2 = “Sobre qualquer entrada:
1. Rode M sobre w . Se ela aceita, aceite.”
2. Deˆ como sa´ıda 〈M1,M2〉.”
Note que na func¸a˜o F :
L(M1) = ∅, e L(M2) =
{
Σ∗, se M aceita w ,
∅, se M na˜o aceita w
portanto 〈M,w〉 ∈ AMT se, e somente se, 〈M1,M2〉 ∈ EQMT, e conclu´ımos
que f reduz AMT a EQMT.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 30 / 46
Redutibilidade por mapeamento
Prova. (Continuac¸a˜o)
Na segunda parte da prova mostramos que EQMT na˜o e´ Turing-reconhec´ıvel.
Para tal, mostramos que AMT e´ redut´ıvel ao complemento de EQMT, ou seja,
que AMT e´ redut´ıvel a EQMT.
A seguinte MT G computa a func¸a˜o redutora g de AMT para EQMT.
G = “Sobre a entrada 〈M,w〉, onde M e´ uma MT e w e´ uma cadeia:
1. Construa as seguintes ma´quinas M1 e M2:
M1 = “Sobre qualquer entrada:
1. Aceite.”
M2 = “Sobre qualquer entrada:
1. Rode M sobre w . Se ela aceita, aceite.”
2. Deˆ como sa´ıda 〈M1,M2〉.”
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 31 / 46
Redutibilidade por mapeamento
Prova. (Continuac¸a˜o)
Note que na MT G :
L(M1) = Σ
∗, e L(M2) =
{
Σ∗, se M aceita w ,
∅, se M na˜o aceita w ,
portanto 〈M,w〉 ∈ AMT se, e somente se, 〈M1,M2〉 ∈ EQMT, e conclu´ımos
que f reduz AMT a EQMT.
Para finalizar, note que a u´nica diferenc¸a entre G e F e´ a ma´quina M1: em F
ela sempre rejeita, enquanto em G ela sempre aceita.
Em ambas f e g , M aceita w se, e somente se, Mw sempre aceita.
Em g , M aceita w se, somente se, M1 e M2 sa˜o equivalentes.
Portanto, g reduz AMT a EQMT.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 32 / 46
O Teorema de Rice
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 33 / 46
O Teorema de Rice: Introduc¸a˜o
Ate´ agora demonstramos va´rios resultados importantes sobre as limitac¸o˜es da
computac¸a˜o:
1. Va´rios problemas interessantes sa˜o indecid´ıveis.
Um exemplo de problema indecid´ıvel e´ o problema da aceitac¸a˜o para MTs.
(Mas pelo menos ele era Turing-reconhec´ıvel.)
2. Va´rios problemas interessantes na˜o sa˜o Turing-reconhec´ıveis.
Um exemplo era o problema de decidir se um programa entra em loop. (Mas
pelo menos ele era co-Turing-reconhec´ıvel, isto e´, apesar de na˜o ser poss´ıvel
reconhecer quando um programa entra em loop, e´ poss´ıvel reconhecer quando
ele na˜o entra em loop.)
3. Existem problemas que na˜o sa˜o Turing-reconhec´ıveis, nem
co-Turing-reconhec´ıveis.
Por exemplo, o problema de equivaleˆncia de MTs. (Na˜o e´ poss´ıvel reconhecer
quando duas MTs sa˜o equivalentes, e na˜o e´ poss´ıvel reconhecer quando duas
MTs na˜o sa˜o equivalentes.)
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 34 / 46
O Teorema de Rice: Introduc¸a˜o
Ja´ vimos que a maioria dos problemas e´ indecid´ıvel (e, ale´m disso,
Turing-irreconhec´ıvel).
Entretanto, existem muitos problemas interessantes que sa˜o indecid´ıveis?
O Teorema de Rice responde a essa pergunta, afirmando que
a maioria absoluta dos problemas interessantes e´ indecid´ıvel!
Essencialmente, o teorema diz que toda “propriedade na˜o-trivial” de uma
linguagem reconhecida por uma MT e´ indecid´ıvel.
Dado um conjunto S , uma propriedade P e´ um subconjunto P ⊆ S .
1 Dado o conjunto H de seres humanos, a propriedade de “ser mulher” pode ser
representada pelo subconjunto F ⊆ H de todas as mulheres.
Checar se uma pessoa h ∈ H satisfaz a propriedade de ser mulher e´
equivalente a checar se h ∈ F .
Aqui vamos tratar sobre propriedades do conjunto de todas as descric¸o˜es de
ma´quinas de Turing.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 35 / 46
O Teorema de Rice: Propriedades de linguagens
Formalmente, uma propriedade P de linguagens e´ uma colec¸a˜o de
descric¸o˜es de ma´quinas de Turing satisfazendo que
Se L(M1) = L(M2) enta˜o 〈M1〉 ∈ P ⇔ 〈M2〉 ∈ P.
Note que uma propriedade e´, ela mesma, uma linguagem que conte´m cadeias
descrevendo MTs.
Exemplos de propriedades de linguagens incluem:
1 A linguagem reconhecida pela MT e´ regular?
2 A cadeia 00 pertence a` linguagem reconhecida pela MT?
Ja´ os exemplos abaixo na˜o sa˜o propriedades de linguagens, mas apenas
propriedades de MTs (ja´ que podem existir MTs equivalentes para a mesma
linguagem tais que uma satisfaz a propriedade, e a outra na˜o.)
1 A cadeia 00 e´ aceita em menos do que 10 passos de computac¸a˜o?
2 Nunca se usam mais que 100 posic¸o˜es da fita para aceitar qualquer cadeia?
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 36 / 46
O Teorema de Rice: Propriedades na˜o-triviais de
linguagens
Uma propriedade na˜o-trivial de linguagens e´ uma propriedade P tal que:
1. P inclui pelo menos uma descric¸a˜o de MT, e
2. P na˜o inclui todas as descric¸o˜es de MTs.Sa˜o exemplos propriedades na˜o-triviais de linguagens:
1 A cadeia 00 pertence a` linguagem reconhecida pela MT?
2 A linguagem reconhecida pela MT e´ regular?
Uma propriedade trivial de linguagens e´ uma propriedade P que ou inclui
todas as descric¸o˜es de MTs, ou na˜o inclui nenhuma descric¸a˜o de MT.
Sa˜o exemplos de propriedades triviais de linguagens:
1 A MT aceita um nu´mero inteiro de cadeias? (Toda MT satisfaz essa
propriedade.)
2 A MT aceita e rejeita toda cadeia? (Nenhuma MT satisfaz essa propriedade.)
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 37 / 46
O Teorema de Rice
Teorema (Teorema de Rice) Para qualquer propriedade na˜o-trivial P de
linguagens reconhecidas por ma´quinas de Turing, o problema de determinar
se a linguagem de uma MT M satisfaz a propriedade P e´ indecid´ıvel.
Prova. Por contradic¸a˜o.
Assuma que a propriedade na˜o-trivial P seja decid´ıvel e que, portanto, haja
um decisor RP para P.
Seja T∅ uma MT que sempre rejeite (i.e., L(T∅) = ∅).
Podemos assumir, sem perda de generalidade, que 〈T∅〉 /∈ P (pois caso
〈T∅〉 ∈ P podemos trocar a propriedade P por P no restante desta prova).
Como P e´ na˜o-trivial, existe uma MT T tal que 〈T 〉 ∈ P.
Vamos construir um decisor S para AMT usando a capacidade de RP de
distinguir entre T∅ e T .
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 38 / 46
O Teorema de Rice
Prova. (Continuac¸a˜o)
S = “Sobre a entrada 〈M,w〉:
1. Use M e w para construir a seguinte MT M ′′w .
M ′′w = “Sobre a entrada x :
1. Simule M sobre w . Se ela pa´ra e rejeita, rejeite.
2. Simule T sobre x . Se ela aceita, aceite; se na˜o, rejeite.”
2. Use a MT RP para determinar se 〈M ′′w 〉 ∈ P. Se sim, aceite; se na˜o, rejeite.”
Note que
L(M ′′w ) =
{
L(T ), se M aceita w ,
L(T∅), se M na˜o aceita w ,
e, portanto,
〈M ′′w 〉 ∈ P se, e somente se, M aceita w .
Isto significaria que AMT e´ decid´ıvel, o que e´ uma contradic¸a˜o. Logo,
conclu´ımos que P na˜o pode ser decid´ıvel.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 39 / 46
O Teorema de Rice - Exemplo
Exemplo 4 Use o Teorema de Rice para mostrar que a linguagem
P42 = {〈M〉 | M e´ uma MT e L(M) tem exatamente 42 palavras}
e´ indecid´ıvel.
Prova. Note que a linguagem P42 e´ uma linguagem que consiste em
descric¸o˜es de MTs, portanto e´ uma propriedade.
Ale´m disso, note que P42 satisfaz as condic¸o˜es do Teorema de Rice:
1. P42 e´ uma propriedade na˜o-trivial: algumas linguagens reconhecidas por MTs
conteˆm exatamente 42 palavras, enquanto outras teˆm um nu´mero diferente de
palavras.
2. A propriedade descrita por P42 e´ uma propriedade da linguagem, e na˜o da MT
que reconhece a linguagem. (Mais precisamente, sempre que L(M1) = L(M2),
temos que 〈M1〉 ∈ P42 se, e somente se, 〈M2〉 ∈ P42).
Logo o Teorema de Rice se aplica a P42, e ela e´ uma linguagem indecid´ıvel.
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 40 / 46
O Teorema de Rice - Exemplo
Exemplo 5 O Teorema de Rice pode ser aplicado a` linguagem abaixo?
P10 = {〈M〉 | M reconhece a cadeia abc em
menos de 10 passos de computac¸a˜o}
Soluc¸a˜o. Note que a linguagem P10 e´ uma linguagem que consiste em
descric¸o˜es de MTs, e portanto P10 e´ uma propriedade.
Entretanto, note que P10 na˜o satisfaz as condic¸o˜es do Teorema de Rice.
Apesar de P10 ser uma propriedade na˜o-trivial (algumas linguagens
reconhecidas por MTs pertencem a P10 e outras na˜o), a propriedade descrita
por P10 na˜o e´ uma propriedade da linguagem, mas apenas uma
propriedade da MT que reconhece a linguagem.
Mais precisamente, e´ poss´ıvel ter duas MTs M1 e M2 tais que
L(M1) = L(M2), mas 〈M1〉 ∈ P10 e 〈M2〉 /∈ P10.
Como suas condic¸o˜es na˜o sa˜o satisfeitas para P10, na˜o podemos aplicar o
Teorema de Rice para concluir que P10 e´ uma propriedade indecid´ıvel.
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 41 / 46
Apeˆndice -
Implicac¸o˜es da
indecidibilidade do Problema
da Parada
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 42 / 46
Implicac¸o˜es da indecidibilidade do Problema da Parada
O Problema da Parada ser indecid´ıvel tem algumas implicac¸o˜es profundas.
A primeira delas tem a ver com a prova de teoremas matema´ticos.
Vamos exemplifica´-la com a conjectura de Goldbach.
Conjectura de Goldbach: Todo inteiro par maior que 3 pode ser expresso
como a soma de dois primos.
1 4 = 2 + 2
2 6 = 3 + 3
3 8 = 3 + 5
4 . . .
5 100 = 17 + 83
6 . . .
Esta conjectura esta´ em aberto desde 1 742!
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 43 / 46
Implicac¸o˜es da indecidibilidade do Problema da Parada
Teorema Se o Problema da Parada fosse decid´ıvel, ter´ıamos uma soluc¸a˜o
para a Conjectura de Goldbach.
Prova.
Considere a seguinte MT G .
G = “Ignore a entrada.
1. De i = 4 ate´ infinito, fac¸a o seguinte:
1. Teste se i pode ser escrito como a soma de dois primos.
2. Se i na˜o for a soma de dois primos, deˆ i como sa´ıda e pare.”
Note que a MT G pa´ra se, e somente se, a Conjectura de Goldbach e´ falsa.
Logo, se o Problema da Parada fosse decid´ıvel, bastaria aplicar seu decisor a
G para decidir a Conjectura de Goldbach.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 44 / 46
Implicac¸o˜es da indecidibilidade do Problema da Parada
O caso da conjectura de Goldbach e´ um caso particular de um resultado
importante da teoria de linguagens.
Teorema Se o problema da parada fosse decid´ıvel, enta˜o toda linguagem
Turing-reconhec´ıvel seria tambe´m uma Turing-decid´ıvel.
Prova.
Como esta e´ a u´ltima prova de teorema deste curso, eu na˜o vou tirar seu
prazer de fazeˆ-la por conta pro´pria!
(Na verdade, voceˆ ja´ a fez em sala de aula, enta˜o voceˆ pode refazeˆ-la aqui!)
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 45 / 46
Implicac¸o˜es da indecidibilidade do Problema da Parada
Ja´ demonstramos que va´rios problemas interessantes, como o problema da
parada e o da equivaleˆncia de MTs, sa˜o indecid´ıveis.
Entretanto, um aspecto intrigante da demonstrabilidade e´ que existem
problemas para os quais nunca vamos ser capazes de:
1. achar uma soluc¸a˜o;
2. e nem ao menos demonstrar que eles na˜o teˆm soluc¸a˜o!
Considere novamente a Conjectura de Goldbach.
1. Se ela for falsa, podemos demonstrar isso com um contra-exemplo.
2. Logo, se na˜o pudermos demonstrar a conjectura de Goldbach, e´ porque ela
necessariamente e´ verdadeira.
3. Portanto, se pudermos demonstrar que na˜o e´ poss´ıvel demonstrar a conjectura,
estamos demonstrando que ela e´ verdadeira, o que e´ uma contradic¸a˜o.
Logo, conclu´ımos que se a conjectura de Goldbach na˜o for demonstra´vel, na˜o
vamos jamais conseguir demonstrar que ela na˜o e´ demonstra´vel!
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Redutibilidade DCC-UFMG (2018/01) 46 / 46