Redutibilidade-0.51
51 pág.

Redutibilidade-0.51


DisciplinaTeoria da Computação543 materiais16.664 seguidores
Pré-visualização3 páginas
(4) 
24 
Problema A Problema B reduzível a 
Indecidível 
Problema A Problema B reduzível a 
Indecidível Indecidível 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take-Home (5) 
25 
Problema A Problema B reduzível a 
Indecidível 
Problema A Problema B reduzível a 
Indecidível Indecidível 
X A pode ser decidível! 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take Home (6) 
26 
Estratégias para demonstrar 
redutibilidade e provar indecidibilidade 
Problema A 
Indecidível 
Problema B 
Sabemos que Problema A é indecidível. 
Queremos reduzir o Problema A ao Problema B 
para demonstrar que B também é indecidível 
reduzível a 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take Home (7) 
27 
Estratégia 1: Assuma que um decididor DB para 
B existe. Mostre que usando DB podemos 
contruir um decididor DA para A (contradição) 
Decididor DA 
Decididor DB 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take-Home (8) 
28 
\uf0a7 Estratégia 2: Assuma que um decididor DB 
para B existe. Mostre que este decididor 
deverá necessariamente conter um decididor 
DA (contradição) para tratar um caso especial 
do problema B 
Decididor DB 
Decididor DA 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Funções Computáveis Totais 
\uf0a7 Definição: Uma função \ud835\udc53: \u3a3\u2217 \u27f6 \u3a3\u2217 é uma 
função computável total se existe alguma 
MTN que termina sua computação com 
sucesso (configuração de aceitação) para 
qualquer \ud835\udc5d \u2208 \u3a3, e o conteúdo final da fita é 
dado por \u2fd\ud835\udc53 \ud835\udc5d \u2fd 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Intuição de Redutibilidade 
\uf0a7 A redução de um problema \ud835\udc34 para um 
problema \ud835\udc35 significa que existe uma função 
computável total que converte instâncias do 
problema \ud835\udc34 em instâncias do problema \ud835\udc35 
\u2022 Desta maneira, qualquer instância do problema \ud835\udc34 
pode ser resolvida usando a redução para 
converte-la em uma instância do problema \ud835\udc35 e, 
então, usar uma MT que resolve o problema \ud835\udc35 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Funções Computáveis e MTs 
\uf0a7 Funções computáveis podem ser 
transformações de descrições de MTs 
\uf0a7 Por exemplo, uma função computável total \ud835\udc53 
recebe com entrada \ud835\udc5d e retorna a descrição de 
uma MT \ud835\udc40\u2032 se \ud835\udc5d = \ud835\udc40 é a codificação de 
uma MT 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definição Formal de Redutibilidade 
\uf0a7 A definição formal de redutibilidade em 
termos de linguagens é dada da seguinte 
forma: 
\uf0a7 Definição: Linguagem \ud835\udc34 é reduzível para a 
linguagem \ud835\udc35, denotado por A \u2264\ud835\udc5f \ud835\udc35, se existe 
uma função computável total \ud835\udc53: \u3a3\u2217 \u27f6 \u3a3\u2217, 
onde para qualquer \ud835\udc5d temos que: 
\ud835\udc5d \u2208 \ud835\udc34 \u2194 \ud835\udc53 \ud835\udc5d \u2208 \ud835\udc35 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Redutibilidade de Linguagens 
\uf0a7 A redução de \ud835\udc34 para \ud835\udc35 provê uma maneira de 
converter questões a respeito dos elementos de 
A em questões a respeito dos elementos de B 
\u2022 Para testar se \ud835\udc5d \u2208 \ud835\udc34, a redução \ud835\udc53 é primeiramente 
usada para mapear \ud835\udc5d para \ud835\udc53(\ud835\udc5d); então é testado se 
\ud835\udc53(\ud835\udc5d) \u2208 \ud835\udc35 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 4 
\uf0a7 Se \ud835\udc34 \u2264\ud835\udc5f \ud835\udc35 e B é decidível, então A é decidível 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 4 - Prova 
\uf0a7 Seja \ud835\udc40 o decididor para \ud835\udc35 e \ud835\udc53 a redução de \ud835\udc34 
para \ud835\udc35. Um decidior para \ud835\udc41 para \ud835\udc34 pode ser 
descrito da seguinte maneira: 
\uf0a7 N=\u201cNa entra p: 
1. Compute \ud835\udc53(\ud835\udc5d) 
2. Execute \ud835\udc40 na entrada \ud835\udc53(\ud835\udc5d) e retorne como 
resultado o que \ud835\udc40 retornar\u201d 
\uf0a7 Claramente, se \ud835\udc5d \u2208 \ud835\udc34, então \ud835\udc53 \ud835\udc5d \u2208 \ud835\udc35 porque \ud835\udc53 
é uma redução de \ud835\udc34 para \ud835\udc35. Assim \ud835\udc40 aceita \ud835\udc53(\ud835\udc5d) 
sempre que \ud835\udc5d \u2208 \ud835\udc34 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Corolário 1 
\uf0a7 Se \ud835\udc34 \u2264\ud835\udc5f \ud835\udc35 e \ud835\udc34 é indecidível, então \ud835\udc35 é 
indecidível 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5 
\uf0a7 Se Se \ud835\udc34 \u2264\ud835\udc5f \ud835\udc35 e B é Turing-reconhecível, então 
A é Turing-reconhecível 
37 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Históricos da Computação 
\uf0a7 O histórico da computação de uma Máquina de Turing para 
uma determinada entrada é simplesmente a sequência de 
configurações que a máquina percorre durante o 
processamento da entrada 
\u2022 Registro completo da computação da máquina 
\uf0a7 O histórico de computação pode ser usado para provar que 
\ud835\udc3f\ud835\udc40\ud835\udc47 é reduzível a certas linguagens 
\u2022 Útil quando a prova de indecidibilidade envolve testar a 
existência de alguma coisa (e.g., encontrar a raiz integral de 
polinômios) 
\uf0a7 Além disso, históricos de computação também podem ser 
usado para provar decididibilidade 
\uf0a7 A seguir, vamos mostrar uma prova de decidibilidade 
usando históricos 
38 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definições 
\uf0a7 Seja \ud835\udc40 uma MT e \ud835\udc5d a palavra de entrada 
\uf0a7 Histórico de computação de aceitação para \ud835\udc40 
em \ud835\udc5d: uma sequência de configurações 
\ud835\udc361, \ud835\udc362, \u2026 , \ud835\udc36\ud835\udc59, onde \ud835\udc361 é o estado de configuração 
de M na entrada p, \ud835\udc36\ud835\udc59 é uma configuração de 
aceitação de M, e cada \ud835\udc36\ud835\udc56 produz a configuração 
\ud835\udc36\ud835\udc56+1 
\uf0a7 Histórico de computação de rejeição para \ud835\udc40 em 
\ud835\udc5d: definido de maneira análoga, com diferença 
que \ud835\udc36\ud835\udc59 agora é um estado de rejeição 
 
 
 
 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definições 
\uf0a7 Note que os históricos de computação de 
aceitação e rejeição são sequências finitas 
\uf0a7 Para máquinas determinísticas existe apenas 
um histórico de computação para dada 
entrada 
\uf0a7 Para máquinas não-determinísticas podem 
existir muitos históricos de computação para 
uma mesma entrada 
40 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Autômato 
Limitado Linearmente (ALL) 
\uf0a7 Um tipo de MT restrito onde a cabeça l/e não 
pode mover uma determinada distância além 
da porção da fita que contém a entrada 
\uf0a7 Necessariamente, um ALL é uma MT com uma 
quantidade limitada de memória 
\u2022 Para uma entrada de tamanho \ud835\udc5b, a quantidade de 
memória necessária é linear em \ud835\udc5b 
41 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens e Máquinas 
42 
Linguagens Máquinas 
Recursivamente 
Enumeráveis 
Máquina de Turing, 
Máquina de Turing 
Não-Determinística 
Sensitivas ao 
Contexto 
Autômato Limitado 
Linearmente 
Livres de 
Contexto Autômato de Pilha 
Regulares 
Autômato Finito 
Determinístico, Automato 
Finito Não-Determinístico 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5 
\uf0a7 \ud835\udc3f\ud835\udc34\ud835\udc3f\ud835\udc3f = \ud835\udc401, \ud835\udc5d | \ud835\udc401 é \ud835\udc62\ud835\udc5a \ud835\udc34\ud835\udc3f\ud835\udc3f \ud835\udc5e\ud835\udc62\ud835\udc52 \ud835\udc4e\ud835\udc50\ud835\udc52\ud835\udc56\ud835\udc61\ud835\udc4e \ud835\udc5d 
\uf0a7 \ud835\udc3f\ud835\udc34\ud835\udc3f\ud835\udc3f é decidível 
43 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5: Prova 
\uf0a7 Para decidir se um \ud835\udc34\ud835\udc3f\ud835\udc3f \ud835\udc40 aceita uma entrada 
\ud835\udc5d, temos que construir uma MT \ud835\udc46 para simular 
\ud835\udc40 em \ud835\udc5d. Durante a simulação, se \ud835\udc40 pára e 
aceita, \ud835\udc46 aceita; se \ud835\udc40 pára e rejeita, \ud835\udc46 rejeita 
\uf0a7 O problema é se M entrar em loop 
\uf0a7 Como poderiámos detectar se M entrou em 
loop 
\u2022 O fato da memória de M ser limitada pode ajudar 
nesta tarefa? 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Décimo Problema de Hilbert 
\uf0a7 Por simplicidade, considere uma versão mais 
simples do polinômio contendo apenas uma 
variável, como 4\ud835\udc653 \u2212 2\ud835\udc652 + x \u2212 7 
\uf0a7 Seja D1 = {\ud835\udc5d|\ud835\udc5d é um polinômio sobre x com uma 
raiz integral} 
\uf0a7 A MT \ud835\udc401 reconhece \ud835\udc371 
\uf0a7 \ud835\udc401= A entrada é um polinômio p sobre a variável 
x 
1. Avalia p com a variável x atribuída sucessivamente 
os valores 0, 1, -1, 2, -2, 3, -3, \u2026 Se a qualquer ponto 
o resultado do polinômio é 0, aceite 
 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Décimo Problema de Hilbert 
\uf0a7 Para o problema específico de encontar uma raiz 
integral de polinômios contendo apenas uma 
variável, é possível projetar uma MT decididora 
\u2022 É conhecido que a raiz do polinômio, se existir estar 
no intevalo ±\ud835\udc58
\ud835\udc50\ud835\udc5a\ud835\udc4e\ud835\udc65
\ud835\udc501
, onde \ud835\udc58 é o número de termos do 
polinômio, \ud835\udc50\ud835\udc5a\ud835\udc4e\ud835\udc65 é o coeficiente com o maior valor 
absoluto, e \ud835\udc501 é o coeficiente do termo de maior 
ordem 
\uf0a7 Se uma raiz não é encontrada dentro destes 
limites, então a máquina rejeita 
 
46 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Lemma 1 
\uf0a7 Seja \ud835\udc40 um \ud835\udc34\ud835\udc3f\ud835\udc3f com \ud835\udc5e estados e \ud835\udc54 símbolos 
no alfabeto da fita. Então, existem exatas 
\ud835\udc5e\ud835\udc5b\ud835\udc54\ud835\udc5b configurações distintas para uma fita de 
tamanho \ud835\udc5b 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Lemma 1: Prova 
\uf0a7 Uma configuração consiste do estado de controle,