Redução
1
Problema
A é redutível ao problema B
Se, quando podemos resolver o problema B ,
então podemos também resolver o problema A
B
A
2
Problema
A é redutível ao problema B
Se B é decidível então
Se
A é decidível
A é não decidível então B é não decidível
3
Exemplo:
o problema da parada
é redutível ao
problema de entrada em um estado
4
Problema de entrada em um estado
Entradas: Máquina de Turing
Questão:
Estado
q
String
w
M
M entra no estado q
quando executa sobre
w?
5
Teorema:
O problema de entrada em um estado
não é decidível
Prova:
Reduza o problema da parada ao
problema de entrada em um estado
6
Suponha que temos um algoritmo (MT)
que resolve
o problema de entrada em um estado
Vamos construir um algoritmo
que resolve o problema da parada
7
Suponha que temos um algoritmo que resolve
o problema de entrada em um estado:
M
w
q
SIM
Algoritmo para
o problema de
entrada em
NÃO
um dado estado
M entra
q
não
entra
q
M
8
Queremos projetar um algoritmo:
M
w
Algoritmo para
o problema
da parada
SIM
M pára sobre w
NÃO
não
pára sobre
M
w
9
Modifique a máquina de entrada
•Adicione um novo estado
M :
q
•A partir de qualquer estado de parada
adicione transições para q
M
M
estados de parada
q
estado de parada
único
10
M pára
se e
somente
se
M  entra no estado q
11
Algoritmo para o problema da parada:
Entradas: máquina
1. Construa a máquina
M e string w
M  com estado q
2. Execute o algoritmo para o problema de
,
entrada em um estado,
com as entradas:
M , q , w
12
Algoritmo para o problema da parada
M
Gera
M
M
q algorimo p/
entrada em
w
estado
SIM
SIM
NÃO
NÃO
w
13
Reduzimos o problema da parada ao
problema de entrada em um estado
Como o problema da parada é não decidível,
então o problema de entrada em estado
é também não decidível
Fim da Prova
14
Outro exemplo:
o problema da parada
é redutível ao
problema da parada com a fita em branco
15
O problema da parada com a fita em branco
Entrada: Máquina de Turing
Questão:
M
M pára quando executada
tendo como entrada a fita em branco?
16
Teorema:
O problema da parada com a fita em branco
não é decidível
Prova: Reduza o problema da parada ao
problema da parada com a fita em branco
17
Suponha que temos um algoritmo para
o problema da parada com a fita em branco
Vamos construir um algoritmo
para o problema da parada
18
Suponha que temos um algoritmo para
o problema da parada com a fita em branco:
SIM
M
M pára sobre
a fita em branco
Algoritmo para
parada com
M não pára sobre
a fita em branco NÃO a fita em branco
19
Queremos projetar um algoritmo para
resolver o problema da parada:
M
w
Algoritmo para
o problema
da parada
SIM
M pára sobre w
NÃO
não pára
sobre
M
w
20
Construa uma nova máquina
• Sobre a fita escreva
Mw
w
• Então continue a execução como
M
Mw
passo 1
se fita em branco
passo 2
execute M
então escreva
com entrada w
w
21
M pára sobre a entrada w
se
e somente
se
M w pára quando executada
com a fita em branco
22
Algoritmo para o problema da parada:
Entradas: máquina
1. Construa
M e string w
Mw
2. Execute o algoritmo para o problema
da parada com a fita em branco
com entrada M w
23
M
w
Algoritmo para o problema da parada
Gera
Mw
algoritmo p/
Mw
parada com
fita em branco
SIM
SIM
NÃO
NÃO
24
Reduzimos o problema da parada
ao problema da parada com fita em branco
Como o problema da parada não é decidível,
o problema da parada com a fita em branco
também não é decidível
Fim da Prova
25
Resumo de Problemas Não Decidíveis
Problema da Parada:
Máquina
M pára sobre a entrada w ?
Problema de pertinência:
Máquina M aceita o string
w?
Em outras palavras: O string w é elemento de uma linguagem
recursivamente enumerável
L
?
26
Problema da parada com a fita em branco:
Máquina M pára quando executada
sobre a fita em branco?
Em outras palavras: O string vazio é elemento de uma linguagem
recursivamente enumerável
L
?
Problema de entrada em um dado estado:
Máquina M entra em um estado q
quando executada sobre a entrada w ?
27
Funções Não Computáveis
28
Funções Não Computáveis
Domínio
f
Contradomínio
Uma função é não computável se ela não
pode ser computada para todo o seu domínio
29
Uma função não computável:
f (n) 
número máximo de passos até que
uma máquina de Turing com n estados
páre quando executada sobre
a fita em branco
30
Teorema: A função
Prova:
f (n) é não computável
Suponha, por contradição, que
f (n) seja computável
Então o problema da parada para
a fita em branco é decidível
31
Algoritmo para a parada com fita em branco:
Entrada: máquina
M
1. Conte os estados de
2. Compute
M:
m
f (m)
3. Simule M por f (m) passos
começando com a fita em branco
Se
M pára enão retorne SIM
caso contrário retorne NÃO32
Portanto, o problema da parada com fita
em branco é decidível
Entretanto, já provamos que o problema
da parada com fita em branco é
não decidível
Contradição!!!
33
Portanto, a função
f (n) é não computável
Fim da Prova
34
Teorema de Rice
35
Definição:
Propriedades não triviais de
linguagens recursivamente enumeráveis:
qualquer propriedade de alguma (não todas)
as linguagens recursivamente enumeráveis
36
Algumas propriedades não triviais de
linguagens recursivamente enumeráveis:
• L é vazia
• L é finita
• L contém dois strings diferentes
com o mesmo comprimento
37
Teorema de Rice:
Qualquer propriedade não trivial de
uma linguagem recursivamente enumerável
é não decidível
38
Vamos provar para algumas propriedades
não triviais, sem usar o teorema de Rice
39
Teorema:
Para qualquer linguagem recursivamente
enumerável L
não é decidível determinar se
L é vazia
Prova:
Vamos reduzir o problema de pertinência
a este problema
40
Seja
M uma máquina que aceita
L( M )  L
L
Suponha que temos um algoritmo para o
problema da linguagem vazia:
M
Algoritmo para
o problema da
linguagem vazia
SIM
L(M ) vazia
NO
L(M ) não vazia
41
Vamos construir um algoritmo para
o problema de pertinência:
M
w
SIM
Algoritmo para
o problema de
NÃO
pertinência
M aceita
w
M rejeita w
42
Primeiro construa a máquina
Mw
:
Quando M entra em um estado final,
compare a entrada original com w
Aceite se a entrada original é
igual ao string w
43
w L
se e
somente se
L( M w )
é não vazia
L( M w )  {w}
44
Algoritmo para o problema de pertinência:
Entradas: máquina
1. Construa
M e string w
Mw
2. Determine se
L( M w )
é vazia
SIM: então w L(M )
NÃO: então w L(M )
45
Algoritmo de pertinência
M
w
construa
Mw
verifique se
Mw
SIM
NÃO
NÃO
SIM
L( M w )
é vazia
Fim da Prova
46