Notas de Aula: Teoria da Computação - Reduções

UNIVERSIDADE PRESBITERIANA MACKENZIE TEORIA DA COMPUTAÇÃO Notas de Aula Distribuição restrita para uso próprio dos alunos Material em desenvolvimento Pedro Paulo Balbi de Oliveira pedrobmackenziebr 17 de abril de 2023 2 UNIDADE 5 REDUÇÕES 51 CONCEITUAÇÃO Sistemas que são equivalentes entre si admitem a possibilidade de um poder ser reduzido a qualquer outro Reduções são úteis para provar alguma propriedade de um sistema reduzindoo a um outro em que a propriedade já é comprovadamente conhecida Exemplos 1 O problema de se deslocar em uma cidade desconhecida pode ser reduzido ao problema de se obter um mapa da cidade 2 O problema de viajar de São Paulo a Londres se reduz ao problema de comprar um bilhete aéreo de São Paulo a Londres que se reduz ao problema de obter dinheiro suficiente para comprar o bilhete que por sua vez se reduz ao problema de por exemplo arrumar um emprego para ganhar o dinheiro 3 O problema de se medir a área de um retângulo se reduz ao problema de se medir o comprimento de seus 2 lados 4 Pela Tese de ChurchTuring qualquer sistema que possua computabilidade universal é equivalente a qualquer outro Dessa forma podese dizer que qualquer um pode ser reduzido aos demais Normalmente indicamos por A B quando um problema A pode ser reduzido a um problema B ou A se reduz a B ou ainda A é redutível a B Assim se um algoritmo resolve B então este algoritmo pode ser usado para resolver A Todos os problemas parcialmente decidíveis ie indecidíveis que apresentam 1 certificado finito são equivalentes entre si no sentido que um pode ser transformado no outro Reduções desse tipo são úteis para provar a indecidibilidade de um novo problema reduzindo a ele um outro já comprovadamente indecidível 3 Seja o problema TPtop12 t Dado um conjunto finito T de ladrilhos eles podem ladrilhar a metade de cima do plano infinito discretizado sendo que a linha de baixo tem de conter o ladrilho específico t Prova informal da indecidibilidade do TPtop12 t por redução do Problema da Parada a ele ou seja HALTTM TPtop12 t É possível codificar qualquer Máquina de Turing em um sistema de ladrilhos associado ao TPtop12 t Exemplo Codificação da MT que reconhece palíndromes de as e bs descrição nas páginas 242243 do livro Harel Feldman 2004 5 OBS N NTxy Þ STxy1 W E ETxy Þ WTx1y S Cada nova linha ladrilhada Uma transição da MT Ladrilhamento da metade do plano Computação infinita 6 Prova por absurdo através de uma redução do Problema da Parada ao TPtop12 t ou seja HALTTM TPtop12 t Ideia da prova ¾ Supor que TPtop12 t é decidível ¾ Construir um certo programa S usando o programa que resolve o TPtop12 t ¾ Perceber que se S pode ladrilhar o semiplano infinito por construção isso corresponde à realização de uma computação infinita e ¾ Concluir que S não pode existir pois implicaria no Problema da Parada ser decidível que é um absurdo Programa S 7 Exemplos 1 Prove que a linguagem abaixo é indecidível Teorema 54 em Sipser 2013 EQTM áM1 M2ñ M1 e M2 são MTs e LM1 LM2 OBS EQTM corresponde ao Problema da Equivalência de MTs ETM corresponde ao Problema da Vacuidade Emptiness das MTs sendo M uma MT ela rejeita todas as entradas ou seja LM Æ Ideia da prova Por redução de ETM que é indecidível segundo o Teorema 52 de Sipser 2013 ou seja vamos usar ETM EQTM Prova Suponha por absurdo que EQTM seja decidível e seja R a MT que decide EQTM Vamos construir uma nova MT S que decide ETM da seguinte forma S Sobre a entrada áMñ onde M é uma MT 1 Rode R sobre a entrada áM M1ñ onde M1 é uma MT que rejeita todas as entradas ie por construção LM1 Æ 2 Se R aceita S aceita se R rejeita S rejeita Assim se R decide EQTM S decide ETM o que é uma contradição pois ETM é indecidível Sim M º M1 M1 LM1 Æ M R decide EQTM Não N Y S 8 2 Prove que a linguagem abaixo é indecidível Teorema 53 em Sipser 2013 REGULARTM áM ñ M é uma MT e LM é uma linguagem regular Ideia da prova 1 Por redução de ATM ie MT M aceita a entrada w que é indecidível 2 Supõese por absurdo que REGULARTM é decidível e com ela constroise uma MT S que decide ATM S é construída tomando a MT M de sua entrada áMwñ e modificandoa agora denominada M2 para reconhecer uma linguagem regular Û M aceita w 3 O truque é construir M2 de forma que ela reconheça a linguagem regular 0 1 se M aceita w e reconheça a linguagem não regular 0n1n n ³ 0 se M não aceita w Prova Seja R a MT que decide REGULARTM Vamos construir uma nova MT S que decide ATM da seguinte forma S Sobre a entrada áMwñ onde M é uma MT e w é uma cadeia 1 Construa a seguinte MT M2 M2 Sobre a entrada x Se x tem a forma 0n1n n³0 aceite Caso contrário rode M sobre a entrada w e se M aceitar w aceite 2 Rode R sobre a entrada áM2ñ 3 Se R aceita S aceita se R rejeita S rejeita Assim se R decide REGULARTM S decide ATM o que é uma contradição pois ATM é indecidível 9 52 MAIS FORMALMENTE REDUTIBILIDADE POR MAPEAMENTO Formalizar a noção de redução permite seu uso de maneira mais refinada como provar que certas linguagens não são Turing reconhecíveis e para aplicações em teoria da complexidade Uma função f S S é uma função computável se existe alguma Máquina de Turing M que sobre a entrada w para com somente fw sobre sua fita Assim para mostrar que uma função f é computável basta exibir uma Máquina de Turing que consiga computar o mesmo que a função f Exemplos as operações aritméticas usuais de soma subtração etc sobre os números inteiros Uma linguagem A é redutível por mapeamento à linguagem B denotado por A m B se existe uma função computável f S S tal que para toda palavra w w Î A Û fw Î B A função f é denominada a redução de A para B A redução permite resolver instâncias de A primeiro transformandoas em instâncias de B através da função f e em seguida usando o solucionador de B Como a função f não precisa ser nem injetora nem sobrejetora vem daí a notação A m B ou seja B pode ter uma quantidade maior ou igual de pontos que A OBS A redução por mapeamento também é conhecida como redução de muitos para um manyone reduction 10 Exemplo de uma função de redução f No exemplo 2 anterior em que provamos a indecidibilidade de EQTM através da redução ETM EQTM a função de redução f mapeia cada entrada áMñ à saída correspondente áM M1ñ onde M1 é a máquina que rejeita todas as entrada ETM EQTM áMñ áM M1ñ Ou seja a função de redução f mapeia a codificação de uma MT na codificação de duas MTs 11 53 RESULTADOS DE INDECIDIBILIDADE VIA REDUÇÃO POR MAPEAMENTO TEOREMA 522 de Sipser 2013 A m B e B é decidível então A é decidível COROLÁRIO A m B e A é indecidível então B é indecidível TEOREMA 528 de Sipser 2013 A m B e B é Turingreconhecível RE então A é Turingreconhecível RE COROLÁRIO A m B e A não é Turingreconhecível então B não é Turingreconhecível OBS Notar que redução tem direção ¾ De um problema indecidível para um outro com decidibilidade ainda desconhecida ou ¾ De um problema com decidibilidade ainda desconhecida para um outro decidível 12 Exercícios 1 Sabendose que A m B e que ATM m A o que se pode dizer a respeito da decidibilidade das linguagems A e B 2 Sendo A B P e Q linguagens e sabendose que Se A m B e B é decidível então A é decidível Se A m B e A é indecidível então B é indecidível Se A m B e B é Turingreconhecível então A é Turingreconhecível Se A m B e A não é Turingreconhecível então B não é Turingreconhecível A linguagem ATM áMwñ M é uma MT que aceita w é indecidível ATM m P e Q m P o que se pode afirmar a respeito da decidibilidade das linguagems P e Q 13 54 REDUTIBILIDADE VIA HISTÓRIA DE COMPUTAÇÕES Uma história de computação de aceitação para uma entrada w em uma Máquina de Turing M é uma sequência de configurações C1Ck iniciando com a configuração inicial C1 de M e terminando com a configuração Ck em que M aceita a entrada w Uma história de computação de rejeição para uma entrada w em uma Máquina de Turing M é uma sequência de configurações C1Ck iniciando com a configuração inicial C1 de M e terminando com a configuração Ck em que M rejeita a entrada w Muitos resultados sobre decidibilidade de linguagens podem ser provados usando se propriedades sobre as configurações das histórias de computação Exercício Provar que a linguagem ALBA áMwñ M é um ALL que aceita w é decidível Esta linguagem corresponde ao Problema da Aceitação para Autômatos Linearmente Limitados ALLs Linear Bounded Automata LBAs os quais podem ser considerados como Máquinas de Turing com fita limitada Dica a Primeiro observe que sendo M um ALL com q estados g símbolos no alfabeto e uma fita de comprimento n existem exatamente qngn configurações distintas de M para uma fita lembrese de que uma configuração de M se define a partir da posição da cabeça na fita do estado do controle finito e da configuração da fita b Com base nisso sempre é possível saber se a máquina para ou está em loop detalhes no Teorema 59 de Sipser 2013 14 Outros exemplos 1 O Problema da Vacuidade Emptiness Problem para ALLs é indecidível o qual corresponde à linguagem ELBA áMñ M é um ALL e LM Æ Ideia da prova Teorema 510 de Sipser 2013 Redução da linguagem ATM de forma que se ELBA for decidível então ATM também o é Mais especificamente construir um ALL B tal que a linguagem aceita por ele corresponde a todas as histórias de computação de aceitação de uma TM M sobre uma cadeia w Dessa forma testar se LB Æ equivale a testar se M aceita a entrada w o que não é possível pois ATM é indecidível 2 A prova de que o PCP é indecidível também envolve uma redução via história de computações da linguagem ATM Ideia da prova Teorema 515 em Sipser 2013 Mostrase que a partir de uma MT M qualquer e uma entrada w podese construir uma instância P onde um casamento match do PCP corresponde a um histórico de computação de aceitação de M na entrada w Dessa forma testar se uma instância do PCP possui um casamento equivale a testar se M aceita a entrada w o que não é possível pois ATM é indecidível