Decidibilidade-Parte1

Prévia do material em texto

Decibilidade e Computabilidade
Problema de Decisão (PD)
É uma questão que faz referência a um conjunto finito de 
parâmetro e que, para valores específicos dos parâmetros, 
tem como resposta ou sim ou não.
Exemplos:
– Determinar se o número 123456789017 é primo
– Determinar se um número natural n é primo
– Determinar se existe um ciclo em um grafo G
– Determinar se uma palavra w é gerada por uma gramática G
– Problema de Decisão × Instância
Decibilidade e Computabilidade
Procedimento de Decisão
É uma solução para um PD (isto é, algoritmo) que, para 
qualquer instância do PD, determina a resposta correta.
Conceito Informal de Algoritmo
É uma sequência finita de instruções, cada uma delas 
executável por uma máquina em um tempo finito, e que 
produzem sempre os mesmos resultados para o mesmo 
conjunto de dados.
Como formalizar o conceito de ALGORITMO ?
Decibilidade e Computabilidade
Noção de Computação Efetiva
• Possibilidade de execução mecânica
• Produção da mesma saída para as mesmas entradas
• Execução em tempo finito
• . . . .
Alguns Formalismos Propostos
• Máquinas de Turing
• Sistemas de Post
• Funções µ-Recursivas
• λ-Cálculo
Decibilidade e Computabilidade
Tese de Church-Turing
Se uma função é efetivamente computável, então ela é
computável por meio de uma máquina de Turing.
Tese de Church-Turing para PD
Se existe solução para um PD P, então existe uma MT M 
que o soluciona, isto é, que 
– pára em estado final se a resposta é sim; ou
– pára em estado não final se a resposta é não.
Conclusão : MT M deve reconhecer a Ling. Recursiva formada 
por todas as instâncias do PD P
Decibilidade e Computabilidade
Representação de uma instância do PD P
Cada instância de um PD P por ser identificada um uma 
sequência de valores de seus parâmetros: v1, v2, v3, . . ., vn
Uma representação de um instância associa cada sequência
possível a uma palavra de uma linguagem.
Requisitos de uma Representação
• Para cada instância deve haver pelo menos uma palavra que 
a represente
• Cada palavra deve representar no máximo uma instância
• Para qualquer palavra deve ser possível determinar se ela 
representa ou não uma instância
Decibilidade e Computabilidade
Notação para Representação de uma instância do PD P
A representação da sequência de valores: v1, v2, v3, . . ., vn
será dada por R 〈 v1, v2, v3, . . ., vn 〉
ATENÇÃO: Importância da Auto-referência !!!
MT MR 〈 v1, v2, v3, . . ., vn 〉
SIM
NÃO
Decibilidade e Computabilidade
Máquina de Turing Universal
• Auto-referência ⇒ Uma MT pode simular outra MT
• É necessário construir uma representação para uma MT
Exemplo:
M1 = ({0, 1}, {a, b}, {〈, □, a, b}, 〈, □, δ, 0, {0, 1}), em que a 
função de transição δ é dada por : 
t1 : δ(0, a) = [1, a, D] t2 : δ(1, b) = [0, b, E]
a / a D
b / b E
0 1
Decibilidade e Computabilidade
Representação para Estados: R〈0〉 = 1, R〈1〉 = 12
Representação para Símbolos: R〈<〉 = 1, R〈□〉 = 12, R〈a〉 = 13, R〈b〉 = 14
Representação para Direção: R〈D〉 = 1, R〈E〉 = 12
Representação para Transição δ(e, x) = [e’, y, d] :
R〈δ(e, x)〉 = R〈e〉0R〈x〉0R〈e’〉0R〈y〉0R〈d〉
R〈t1〉 = R〈0〉0R〈a〉0R〈1〉0R〈a〉0R〈D〉 = 101301201301
R〈t2〉 = R〈1〉0R〈b〉0R〈0〉0R〈b〉0R〈E〉 = 1201401014012
R〈δ〉 = R〈t1〉00R〈t2〉 = 101301201301001201401014012
Representação para Est. Finais: R〈F〉 = R〈f1〉0R〈f2〉0 . . . 0R〈fk〉, fi∈ F
R〈F〉 = 1012
a / a D
b / b E
0 1
Decibilidade e Computabilidade
Representação para MT M = (Q, Σ, Γ, 〈, □, δ, qi, F):
R〈M〉 = 1|Q|01|Γ|00R〈qi〉00R〈F〉00R〈δ〉
R〈M1〉 = 1201400100101200101301201301001201401014012
Representação para w ∈ Σ* | w = w1w2...wt: R〈w〉 = R〈w1〉0R〈w2〉0...0R〈wt〉
R〈w〉 = 13014013013 para w = abaa
Representação para (M, w):
R〈M, w〉 = R〈M〉000R〈w〉
R〈M1, abaa〉 = 
1201400100101200101301201301001201401014012000 13014013013
a / a D
b / b E
0 1
Decibilidade e Computabilidade
Máquina de Turing Universal
Seja uma MTN de 3 Fitas em que R〈M, w〉 está na Fita 1:
1. Se a entrada não é da forma R〈M, w〉, pare em estado não final
2. Copie R〈w〉 para a Fita 2 e posicione no início
3. Copie R〈qi〉 para a Fita 3
〈 Fita 1
R〈M, w〉
〈 Fita 2
R〈w〉
〈 Fita 3
R〈qi〉
Controle
+
δδδδ
e
Registrador 
de Estado Atual
〈Fita 1
R〈M, w〉
〈 Fita 2
R〈w〉
〈 Fita 3
R〈qi〉
Controle
+
δδδδ
e
Registrador 
de Estado Atual
12 0 14 0 0 1 0 0 120 01 0 120 13 0 01 013 1
0 0 120 14 0 01 01412
. . .
. . . 0 0 0 14 0 0 13130 13 . . .
0 14 0 0 1313 13
1
. . .
. . .
Fita 1
Fita 2
R〈a’ 〉
Fita 3
R〈e’〉
Controle
+
δδδδ
e
Registrador 
de Estado Atual
Fita 1
R〈e〉0R〈a〉0R〈e’〉0R〈a’〉0R〈d〉
Fita 2
R〈a〉
Fita 3
R〈e〉
Controle
+
δδδδ
e
Registrador 
de Estado Atual
R〈e〉0R〈a〉0R〈e’〉0R〈a’〉0R〈d〉
Decibilidade e Computabilidade
4. repita
4.1 Seja R〈a〉 a representação atual (símbolo atual) na Fita 2 e 
R〈e〉 a representação atual (estado atual) na Fita 3 
4.2 Procure uma transição na Fita 1 iniciada por R〈e〉0R〈a〉. 
Seja R〈e〉0R〈a〉0R〈e’〉0R〈a’〉0R〈d〉
4.3 Se encontrou então
- Substitui R〈e〉 por R〈e’〉 na Fita 3 e voltar para o início
- Substitui R〈a〉 por R〈a’〉 na Fita 2
- Move cabeça L/E da Fita 2 na direção representada por R〈d〉
Se não encontrou então
- Testa se R〈e〉 ⊂ R〈F〉→
SIM → Pare em estado final
NÃO → Pare em estado não final
Decibilidade e Computabilidade
Máquina de Turing Universal
L(U) = {R〈M, w〉 | w ∈ L(M)}
Para reconhecimento apenas por parada (Up)
– não existem estados finais na representação R〈M, w〉
– se não há transição possível, Up pára aceitando a entrada
MT Up aceita R〈M, w〉 ⇔MT M pára se a entrada for w
MT UR 〈M, w 〉
SIM
NÃO
w ∈∈∈∈ L (M)
w ∉∉∉∉ L (M)
Decibilidade e Computabilidade
Problema da Parada
Dadas uma MT M arbitrária e uma palavra w arbitrária, 
determinar se a computação de M pára com a entrada w 
Como existe MT Up então L(Up) é LRE.
O que se deseja mostrar : L(Up) não é ling. recursiva.
Teorema: O Problema da Parada para MTs é indecidível.
Prova por Contradição
Suponha que o Problema da Parada seja decidível e que 
a MT P seja capaz de solucioná-lo.
Decibilidade e Computabilidade
Então pode-se representar MT P da seguinte forma:
Construa MT P’, a partir de P, com um loop infinito 
PR 〈M, w 〉
SIM
NÃO
M pára se a entrada for w
M não pára se a entrada for w
P’R 〈M, w 〉
LOOP
NÃO
M pára se a entrada for w
M não pára se a entrada for w
Decibilidade e Computabilidade
Construa MT P’’, adicionando uma MT de cópia antes de P’:
⇒ O que ocorre se a entrada de P’’ for R〈P’’〉 ?
P’’ pára com entrada R〈〈〈〈P’’〉〉〉〉⇔⇔⇔⇔ P’’ não pára com entrada R〈〈〈〈P’’〉〉〉〉
Seja Lp = {R〈M, w〉 | M pára se a entrada é w }, logo:
• Lp não é recursiva (ou Problema da Parada é indecidível)
• Lp é LRE, mas Lp não é LRE
P’
R 〈M, M 〉 LOOP
NÃO
M pára se a entrada for R 〈M〉〉〉〉
M não pára se a entrada for R 〈M〉〉〉〉DuplicaR 〈M 〉
P’’
Decibilidade e Computabilidade
Redução de Problema de Decisão para Outro
Se PD P é redutível a um PD Q decidível então P é decidível
Se PD P indecidível é redutível a um PD Q então Q é indecidível
SIM
NÃO
MT 
para PD 
Q
YRedução 
R
X
MT para PD P
Decibilidade e Computabilidade
Problema da Fita em Branco
Dada uma MT M arbitrária, determinar se a computação de M 
pára com a entrada λ (ou seja, com a fita em branco)
Teorema: O Problema da Fita em Branco é indecidível.
Prova: Redução a partir do Problema da Parada
RR 〈M, w 〉 R 〈M’ 〉
Decibilidade e Computabilidade
Problema da Pertinência à Linguagem de uma G.I.
Dadas uma G.I. G arbitrária e uma palavra w arbitrária, 
determinar se a gramática G gera a palavra w (w ∈ L(G))
Teorema: O Problema da Ling. de uma GI é indecidível.
Prova: Redução a partirdo Problema da Parada
RR 〈M, w 〉 R 〈 G, w 〉