Decidibilidade em Teoria da Computação

Prévia do material em texto

Teoria da Computação 
Decidibilidade 
 
Versão dos Slides: 0.7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Decidibilidade 
 Objetivos 
• Investigar mais a fundo o poder de algoritmos em 
resolver problemas 
• Baseando-se na tese de Church-Turing, 
demonstrar que certos problemas podem ser 
resolvidos por algoritmos ao passo que outros não 
2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Preliminares 
 Problema da Aceitação de Palavras: 
• Testa se um modelo computacional (MC) em 
particular (AFD, AFND, MT, etc) aceita uma 
determinada palavra 
 Este problema pode ser expressado através de 
uma linguagem denotada por 𝐿𝑀𝐶 
• 𝐿𝑀𝐶 contém as codificações de todas máquinas 
possíveis de um determinado MC juntamente com 
as palavras que são aceitas por estas máquinas 
3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Preliminares (2) 
 𝐿𝑀𝐶 =
𝐵, 𝑝 | 𝐵 é 𝑢𝑚 𝑀𝐶 𝑞𝑢𝑒 𝑎𝑐𝑒𝑖𝑡𝑎 𝑎 𝑝𝑎𝑙𝑎𝑣𝑟𝑎 𝑝 
 O problema de testar se um 𝑀𝐶 𝐵 aceita uma 
entrada 𝑝 se reduz a testar se 𝐵, 𝑝 é um elemento 
de 𝐿𝑀𝐶 
 De maneira similar, nós podemos formular outros 
problemas computacionais: testar se uma 
determinada solução pertence a linguagem que 
expressa as soluções válidas para este problema 
 Desta maneira, mostrar que uma linguagem é 
decidível é equivalente a mostrar que o problema 
computacional é decidível 
 4 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Regulares 
 𝐿𝐴𝐹𝐷 =
𝐵, 𝑝 | 𝐵 é 𝑢𝑚 𝐴𝐹𝐷 𝑞𝑢𝑒 𝑎𝑐𝑒𝑖𝑡𝑎 𝑎 𝑝𝑎𝑙𝑎𝑣𝑟𝑎 𝑝 
 Teorema 1: 
 𝐿𝐴𝐹𝐷 é uma linguagem decidível 
 Este teorema mostra que o problema de 
testar se uma determinado autômato aceita 
uma determinada palavra é decidível 
 
5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 1: Prova 
 Idéia: apresentar uma MT M que decide 𝐿𝐴𝐹𝐷 
• M = “Na entrada 𝐵, 𝑝 , onde 𝐵 é um AFD e 𝑝 é 
uma palavra: 
1. Simule 𝐵 na entrada 𝑝 
2. Se a simulação termina em um estado de 
aceitação, Aceite. Caso contrário, Rejeite” 
6 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 1: Prova (2) 
 𝐵, 𝑝 é a representação de um DFA 𝐵 e de 
uma palavra 𝑝. 
• B pode ser repesentado pela quintupla (Q, ∑, , 
q0, F) 
 Quando 𝑀 recebe a entrada, é realizada uma 
checagem se o AFD 𝐵 e a palavra 𝑝 estão 
representados de maneira correta. Caso não 
estejam, M rejeita a entrada 
7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 1: Prova (3) 
 𝑀 simula 𝐵 da seguinte maneira: 
• Informações sobre o estado atual de 𝐵 é mantido 
através de escritas na fita 
• Inicialmente, o estado de B é 𝑞0 e a posição da 
entrada é o primeiro símbolo de 𝑝 
• Estados e transições são atualizados de acordo 
com a função de transição 
• Quando 𝑀 termina o processamento de 𝑝, 
𝑀 aceita se o estado de 𝐵 é um estado de 
aceitação, caso contrário Rejeita 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 2 
 𝐿𝐴𝐹𝑁𝐷 =
𝐵, 𝑝 | 𝐵 é 𝑢𝑚 𝐴𝐹𝑁𝐷 𝑞𝑢𝑒 𝑎𝑐𝑒𝑖𝑡𝑎 𝑎 𝑝𝑎𝑙𝑎𝑣𝑟𝑎 𝑝 
 Teorema 2: 
 𝐿𝐴𝐹𝑁𝐷 é uma linguagem decidível 
 
9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 2: Prova 
 Vamos apresentar um MT 𝑁 que decide 𝐿𝐴𝐹𝑁𝐷 
 N usará 𝑀 (a MT anterior, que decide 𝐿𝐴𝐹𝐷) 
como uma macro 
 Conversão do AFND de entrada em um AFD 
equivalente 
 
 
10 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 2: Prova 
 N = “Na entrada 𝐵, 𝑝 , onde 𝐵 é um AFND e 𝑝 
é uma palavra: 
1. Converta o AFND 𝐵 em um AFD equivalente 𝐶 
2. Execute 𝑀 na entrada 𝐶, 𝑝 
3. Se 𝑀 aceita, também aceite. Caso contrário, 
rejeite 
 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 3 
 𝐸𝐴𝐹𝐷 = 𝐴 | 𝐴 é 𝑢𝑚 𝐴𝐹𝐷 𝑒 𝐿 𝐴 =⊘ 
• A é um automâto que não aceita nenhuma palavra 
 Teorema 3: 
• 𝐸𝐴𝐹𝐷 é uma linguagem decidível 
 
 Exercício: Prove 
• Lembrem-se: Um AFD aceita uma palavra se e 
somente se um estado de aceitação é alcançado a 
partir do estado inicial atravessando um conjunto de 
transições 
12 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 3: Prova 
 T = “Na entrada 𝐴 , onde 𝐵 é um AFND e 𝑝 é 
uma palavra: 
1. Marque o estado inicial 
2. Repita até que nenhum estado possa ser 
marcado 
Marque todos estados que possuem uma transição 
chegando de algum estado já marcado 
3. Se nenhum estado de aceitação está marcado, 
Aceite. Caso contrário, Rejeite 
 
 
13 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Outras Linguagens 
 De maneira similar, podemos provar que 
linguagens livres de contexto (e também 
linguagens sensitivas ao contexto) também 
são decidíveis 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Relacionamento entre Linguagens 
15 
regular 
livres de 
contexto 
decidíveis 
Turing 
reconhecíveis 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
O Problema da Parada 
 Nenhuma máquina pode dizer de maneira 
geral se um programa irá aceitar ou não uma 
determinada entrada 
16 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquina de Turing Universal 
 U = “Na entrada 𝑀, 𝑝 , onde 𝑀 é uma MT e 𝑝 é 
uma palavra: 
1. Simule 𝑀 na entrada p 
2. Se M entra no estado de aceitação, Aceite. Se M 
entra no estado de rejeição, Rejeite” 
 A máquina U é chamada é chamada Máquina 
de Turing Universal porque a mesma é capaz de 
simular qualquer outra MT usando a descrição 
desta MT 
 𝐿𝑀𝑇 é Turing-reconhecível: é reconhecida por 𝑈 
 𝑈 é um decididor? 
17 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquina de Turing Universal 
 Se a máquina 𝑀 entra em loop infinito na entrada 
𝑝, então 𝑈 também entra em loop 
 Se 𝑈 pudesse determinar quando 𝑀 entra em 
loop infinito, então 𝑈 poderia rejeitar e, portanto, 
ser um decididor 
 Mas não é possível determinar quando 𝑀 entra 
em loop infinito 
• Podemos provar que U não é um decididor sem 
considerar diretamente o caso do loop infinito, como 
faremos a seguir... 
18 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5 
 𝐿𝑀𝑇 =
𝑀, 𝑝 | 𝑀 é 𝑢𝑚𝑎 𝑀𝑇 𝑞𝑢𝑒 𝑎𝑐𝑒𝑖𝑡𝑎 𝑎 𝑝𝑎𝑙𝑎𝑣𝑟𝑎 𝑝 
 Teorema 5: 
• 𝐿𝑀𝑇 não é decidível 
19 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Problema da Parada: Prova (1) 
 Vamos assumir que 𝐿𝑀𝑇 é decidível e obter 
uma contradição. 
 Suponha que 𝐻 é um decididor para 𝐿𝑀𝑇 
• Na entrada 𝑀,𝑝 , onde 𝑀 é uma MT e 𝑝 uma 
palavra, 𝐻 pára e Aceita se 𝑀 aceita 𝑝. Além disso, 
𝐻 Rejeita se 𝑀 falha em aceitar 𝑝 (seja porque 
entrou no estado de rejeição ou porque entrou 
em loop infinito) 
20 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Problema da Parada:Prova (2) 
 𝐻 é uma MT onde: 
𝐻 𝑀, 𝑝 = 
𝐴𝑐𝑒𝑖𝑡𝑎 𝑠𝑒 𝑀 𝑎𝑐𝑒𝑖𝑡𝑎 𝑝 
𝑅𝑒𝑗𝑒𝑖𝑡𝑎 𝑠𝑒 𝑀 𝑛ã𝑜 𝑎𝑐𝑒𝑖𝑡𝑎 𝑝
 
21 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Problema da Parada:Prova (3) 
 Agora, nós construímos uma nova MT 𝐷 que 
usa 𝐻 como macro para determinar o que 
ocorre quando a entrada de 𝑀 é sua própria 
descrição 
 Após H produzir o resultado, D faz o oposto, 
isto é, D rejeita se H aceita e aceita se H 
rejeita 
22 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Problema da Parada:Prova (4) 
 D=“Na entrada 𝑀 onde 𝑀 é uma MT: 
1. Execute H na entrada 𝑀, 𝑀 
2. Retorne o oposto do que H retornar; se H Aceita, 
Rejeita; se H Rejeita, Aceita” 
 𝐷 é uma MT onde: 
D 𝑀 = 
𝐴𝑐𝑒𝑖𝑡𝑎 𝑠𝑒 𝑀 𝑛ã𝑜 𝑎𝑐𝑒𝑖𝑡𝑎 𝑀 
𝑅𝑒𝑗𝑒𝑖𝑡𝑎 𝑠𝑒 𝑀 𝑎𝑐𝑒𝑖𝑡𝑎 𝑀 
 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Problema da Parada:Prova (5) 
 O que acontece quando nós executamos D 
com sua própria descrição 𝐷 como entrada? 
24 
D H M 
𝐷 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Problema da Parada:Prova (6) 
 D 𝑀 =
 
𝐴𝑐𝑒𝑖𝑡𝑎 𝑠𝑒 𝐷 𝑛ã𝑜 𝑎𝑐𝑒𝑖𝑡𝑎 𝐷 
𝑅𝑒𝑗𝑒𝑖𝑡𝑎 𝑠𝑒 𝐷 𝑎𝑐𝑒𝑖𝑡𝑎 𝐷 
 
 D é forçado a retornar o oposto de seu próprio 
resultado, o que é uma contradição. Portanto, 
D e H não podem existir 
 
25Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Problema da Parada: 
Formulação Original 
26 
 𝐿𝐻𝐿𝑇 =
𝑀, 𝑝 | 𝑀 é 𝑢𝑚𝑎 𝑀𝑇 𝑞𝑢𝑒 𝑝á𝑟𝑎 𝑞𝑢𝑎𝑛𝑑𝑜 𝑎 𝑒𝑛𝑡𝑟𝑎𝑑𝑎 é 𝑝 
 Teorema 5a: 
• 𝐿𝐻𝐿𝑇 não é decidível 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5a: Prova 
 Vamos assumir que 𝐿𝐻𝐿𝑇 é decidível (e obter 
uma contradição). Então podemos construir o 
seguinte decididor para 𝐿𝐻𝐿𝑇: 
 𝐻 = “Na entrada 𝑀, 𝑝 onde M é a descrição 
de uma MT e p é uma palavra: 
1. Execute M na entrada p 
2. Aceite se M parar 
3. Rejeite se M entrar em loop” 
 
27 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5a: Prova (2) 
 Agora vamos construir uma MT D que receba 
uma descrição de uma MT M como entrada e 
execute H como uma macro na entrada 
𝑀,𝑀 . 
 D = “Na entrada 𝑀 onde M é a descrição de 
uma MT: 
1. Execute H na entrada 𝑀,𝑀 . 
2. Pare se H rejeitar 
3. Entre em loop se H aceitar” 
 
28 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5a: Prova (3) 
 A entrada 𝑀,𝑀 é passada para H, isto é, H 
irá aceitar se M pára quando a palavra de 
entrada é a própria descrição de M. D irá 
então parar (pode ser Aceitar ou Rejeitar) se 
H rejeita 𝑀,𝑀 e entrar em loop caso 
contrário. 
 Notem que D não é um decididor. Em outras 
palavras temos que: 
 D 𝑀 = 
𝑃á𝑟𝑎 𝑠𝑒 𝑀 𝑛ã𝑜 𝑝á𝑟𝑎 𝑒𝑚 𝑀 
𝐸𝑛𝑡𝑟𝑎 𝑒𝑚 𝑙𝑜𝑜𝑝 𝑠𝑒 𝑀 𝑝á𝑟𝑎 𝑒𝑚 𝑀 
 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5a: Prova (4) 
 Executando D com entrada 𝐷 , temos o 
seguinte resultado: 
1. D pára se D entrar em loop 
2. D entra em loop se D parar 
 Portanto, temos uma contradição e 𝐷 e H não 
podem existir. 
 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5a: Observação 
 Considere se D fosse construído da seguinte 
maneira: 
 D = “Na entrada 𝑀 onde M é a descrição de 
uma MT: 
1. Execute H na entrada 𝑀,𝑀 . 
2. Aceite se H rejeitar 
3. Rejeite se H aceitar” 
 Teríamos uma contradição neste caso? 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5a: Observação 
 Não! Para termos uma contradição devemos 
excluir qualquer possibilidade de D existir e como 
consequencia H. Considere o caso onde D é uma 
MT que Rejeita quando a entrada é a sua propria 
descrição: 
1. H é executado na entrada 𝐷,𝐷 . 
2. Como D rejeita 𝐷 e pára, então H aceita 
3. D então rejeita porque H aceita. 
4. Em qualquer caso D rejeita a entrada. Não 
temos uma contradição. 
 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova do Problema da Parada 
 Formulação como problema de aceitação de 
palavras: prova usa a dicotomia Aceita/Rejeita 
 Formulação original: prova usa dicotomia 
Pára/Loop 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Problema da Parada: Analogia 
 Analogia com o paradoxo de Russel: Em uma 
cidade, um barbeiro é responsável por fazer 
(apenas) a barba de todos aqueles que não 
fazem a própria barba. Quem faz a barba 
deste barbeiro? 
 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Não Reconhecíveis 
 Teorema 7: Algumas linguagens não são 
Turing-reconhecíveis 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Lemma 1 
 O conjunto de todas MTs é enumerável 
 Prova: 
• Observe que ∑* é enumerável, para qualquer 
alfabeto ∑. Nós podemos listar ∑* escrevendo 
todas palavras de tamanho 0, 1, 2, e assim por 
diante. 
• Toda MT 𝑀 pode ser codificada em uma palavra 
𝑀 . Podemos listar todas MTs usando a listagem 
de ∑*. Para isso precisamos apenas omitir as 
palavras que não representem codificações válidas 
de uma MT 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 7: Idéia da Prova 
 Sabemos pelo Lemma 1 que o conjunto de 
todas MTs é enumerável 
 Temos que provar que o conjunto de todas 
linguagens ℒ não é enumerável 
 Como uma MT reconhece apenas uma 
linguagem, então temos que existem 
linguagens que não são reconhecidas por 
qualquer MT 
 
37 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 7: Idéia da Prova (2) 
 Mostramos que o conjunto de todas sequências 
binárias infinitas ℬ não é enumerável (uma sequência 
binária é formada por 0s e 1s). Usamos a prova por 
diagonalização bastante similar a estratégia usada para 
provar que o conjunto dos números reais não é 
enumerável 
 Mostramos que é possível estabelecer uma 
correspondência 1-1 entre ℬ e ℒ (Prova omitida). Com 
isso demonstramos que ℒ também não é enumerável 
• Se é possível estabelecer uma correspondência 1-1 entre 
um conjunto não-enumerável A e um conjunto B, então B 
também é não-enumerável 
 
 38 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagem 
Turing-Não-Reconhecível 
 O complemento de uma linguagem é a 
linguagem contendo todas palavras que não 
estão nesta linguagem 
 Uma linguagem é co-Turing-Reconhecível se o 
seu complemento é Turing-Reconhecível 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Turing-Reconhecível 
e Turing Decidível 
 Teorema 8: Uma linguagem é decidível se e 
somente se ela é Turing-reconhecível e seu 
complemento também é Turing-reconhecível 
40 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 8: Prova 
 Primeira direção: Uma linguagem é decidível se 
ela é Turing-reconhecível e seu complemento 
também é Turing-reconhecível 
 Se uma linguagem A é decidível, então a 
linguagem também é Turing-reconhecível 
 O complemento de uma linguagem decidível 
também é decidível. Se temos uma MT 𝑀1 que 
decide uma linguagem 𝐿, podemos facilmente 
contruir uma MT 𝑀2 que decida 𝐿 : use M 1 como 
macro, aceite as palavras que M 1rejeita e rejeite 
as palavras que M 1 aceita 
 
41 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 8: Prova (2) 
 Considere a outra direção da prova: nós temos 
duas linguagens Turing-reconhecíveis A e 𝐴 . 
Seja M1 a MT que reconhece A e M2 a MT que 
reconhece 𝐴 
 A seguinte máquina é um decididor para A: 
𝑀=“Na entrada p: 
1. Execute M1 e M2 na entrada 𝑝 em paralelo 
2. Se M1 aceita, Aceita; se M2 aceita, Rejeita” 
 
42 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 8: Prova (3) 
 Executando M1 e M2 em paralelo significa que M 
possui duas fitas, uma para simular M1 e outra 
para simular M2 
 Toda palavra p está necessariamente em A ou 
𝐴 . Portanto, M1 ou M2 tem que aceitar uma 
palavra p 
 Como M pára se M1 ou M2 páram, então M é um 
decididor 
 M aceita todas palavras em A e rejeita todas 
palavras que não estão em A. Portanto, M é um 
decididor para A e A é decidível 
43 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Corolário 1 
 𝐿𝑀𝑇 não é Turing-reconhecível 
 Prova: Nós sabemos que 𝐿𝑀𝑇 é Turing-
reconhecível. Se 𝐿𝑀𝑇 também é Turing-
reconhecível, então, de acordo com Teorema 
8, 𝐿𝑀𝑇 é decidível. Entretanto sabemos pelo 
Teorema 5 que 𝐿𝑀𝑇 não é decidível. Portanto, 
𝐿𝑀𝑇 só pode ser Turing-não-reconhecível 
44