View
216
Download
1
Category
Preview:
Citation preview
Computabilidade eComplexidade(ENG10014)
Profa. Juliana Pinheiro Campos
E-mail: jupcampos@gmail.com
Sistemas de Informação
TEORIA DA COMPUTAÇÃO
Decidibilidade
O estudo da decidibilidade objetiva determinar a solucionabilidade de problemas, ou seja, investigar a existência ou não de algoritmos que solucionem determinada classe de problemas.
Definimos a noção de algoritmo em termos de MT por meio da tese de Church-Turing. Essa tese afirma que “todo algoritmo pode ser expresso mediante uma MT”.
Vamos estudar alguns problemas solúveis (decidíveis) e não solúveis (indecidíveis).
TEORIA DA COMPUTAÇÃO
Decidibilidade
Infelizmente, muitos problemas interessantes e importantes para a CC são não solucionáveis. Exemplos:
• Detector universal de loops (problema da parada): Dados um programa e uma entrada qualquer, não existe algoritmo genérico capaz de verificar se o programa vai parar ou não para a entrada.
• Equivalência de compiladores: Não existe algoritmo genérico que sempre pare capaz de comparar quaisquer dois compiladores de LLC, e verificar se são equivalentes.
TEORIA DA COMPUTAÇÃO
Decidibilidade
Porque estudar a insolubilidade?
• Para saber que o problema terá que ser simplificado ou alterado antes que possa se encontrar uma solução algorítmica.
• Para evitar a pesquisa de soluções inexistentes.
• Para conhecer as capacidades e limitações dos computadores.
• Para verificar que outros problemas também são insolúveis(utilizando redução).
TEORIA DA COMPUTAÇÃO
Decidibilidade
A classe das linguagens recursivas está ligada ao conceito de decidibilidade.
Um problema de decisão P é decidível se, e somente se, certa linguagem associada a P for recursiva.
Logo, determinar se certo problema é decidível é basicamente, estabelecer se determinada linguagem é recursiva.
Se um PD tem solução, então existe uma MT que o decide.
A classe das Lrec está ligada ao conceito de decidibilidade. Um problema de decisão P é decidível se, e somente se, certa linguagem associada a P for recursiva. Logo, determinar se certo problema Para problemas de decisão temos que: Se um PD tem solução, então existe uma MT que o decide.
TEORIA DA COMPUTAÇÃO
Linguagens decidíveis
1) Problema da aceitação: testar se um AFD específico aceita uma dada cadeia. Linguagem que traduz esse problema:
AAFD = { <B, w> | B é um AFD que aceita a cadeia de entrada w}
Essa linguagem contém as codificações de todos os AFDs juntamente com cadeias que os AFDs aceitam. O problema de se testar se um AFD B aceita uma cadeia w é o mesmo que o problema de se testar se <B, w> ∈ AAFD .
TEORIA DA COMPUTAÇÃO
Linguagens decidíveis
Mostrar que essa linguagem é decidível é o mesmo que mostrar que o PD é decidível.
AAFD é uma linguagem decidível. Prova: apresentamos uma MT M que decide AAFD .
M = “Sobre a entrada <B, w>, onde B é um AFD e w
uma cadeia:
1. Simule B sobre a entrada w.
2. Se a simulação termina em um estado de
aceitação, aceite. Se ela termina em um estado de
não-aceitação, rejeite.”
TEORIA DA COMPUTAÇÃO
Linguagens decidíveis
Representação de MT para PD:
M<B,w>
w ∈ L(B)
w ∉ L(B)
SIM
NÃO
TEORIA DA COMPUTAÇÃO
Linguagens decidíveis
2) Problema da aceitação: testar se um AFN específico aceita uma dada cadeia. Linguagem que traduz esse problema:
AAFN = { <B, w> | B é um AFN que aceita a cadeia de entrada w}
AAFN é uma linguagem decidível. Prova: Apresentamos uma MT N que decide AAFN . Poderíamos projetar N para operar como M, simulando um AFN em vez de um AFD. Ao invés disso, fazemos N usar M como uma sub-rotina.
TEORIA DA COMPUTAÇÃO
Linguagens decidíveis
Como M foi projetada para funcionar com AFDs, N primeiro converte o AFN que ela recebe como entrada para um AFD antes de passá-lo para M.
N = “Sobre a entrada <B, w>, onde B é um AFN e w
uma cadeia:
1. Converta o AFN B em um AFD equivalente C,
usando o procedimento estudado em sala.
2. Rode a MT M (apresentada anteriormente) sobre
a entrada <C, w>.
3. Se M aceita, aceite. Caso contrário, rejeite.”
TEORIA DA COMPUTAÇÃO
Problema da parada
Um dos mais importantes problemas não solucionáveis é conhecido como problema da parada.
Ele pode ser usado como base na demonstração de que outros problemas também são não solucionáveis.
Problema da parada: o problema de se determinar se uma MT aceita uma cadeia de entrada.
AMT = {<M, w> | M é uma MT e aceita a cadeia w}
AMT é indecidível.
TEORIA DA COMPUTAÇÃO
Problema da parada
AMT é indecidível, mas é Turing-reconhecível. A MT U a seguir reconhece AMT.
U = “ Sobre a entrada <M, w>, onde M é uma MT e w
uma cadeia:
1. Simule M sobre a entrada w.
2. Se M em algum momento entra no seu estado de
aceitação, aceite; se M em algum momento entra
em seu estado de rejeição, rejeite.”
Essa máquina entra em loop sobre a entrada <M, w> se M entra em loop sobre w e é por isso que essa máquina não decide AMT.
TEORIA DA COMPUTAÇÃO
Problema da parada
Prova: O problema da parada é indecidível.Supomos que AMT é decidível e encontramos uma contradição. Se AMT é decidível então existe H que é um decisorpara AMT. Para a entrada <M, w>, H pára e aceita se M aceita w e H pára e rejeita se M falha em aceitar w.
H(<M,w>) =
Aceite, se M aceita w
Rejeite, se M não aceita w (rejeita ou
entra em loop)
TEORIA DA COMPUTAÇÃO
Problema da parada
Construímos uma nova MT D com H como uma sub-rotina. D chama H para determinar o que M faz quando a entrada para M é sua própria descrição <M>. Uma vez que D tenha determinado essa informação, ela faz o oposto. Ou seja, ela rejeita se M aceita e aceita se M não aceita. O que segue é uma descrição de D:
D = “Sobre a entrada <M>, onde M é uma MT:
1. Rode H sobre a entrada <M, <M>>.
2. Se H aceita, rejeite e se H rejeita, aceite.”
TEORIA DA COMPUTAÇÃO
Problema da parada
Em resumo,
O que acontece quando rodamos D sobre <D>?
D(<M>) =
Aceite, se M não aceita <M>
Rejeite, se M aceita <M>
D(<D>) =
Aceite, se D não aceita <D>
Rejeite, se D aceita <D>
TEORIA DA COMPUTAÇÃO
Problema da parada
Independentemente do que D faz, ela é forçada a fazer o oposto, o que é obviamente uma contradição. Consequentemente, nem a MT D nem a MT H podem existir. Logo, AMT é indecidivel.
Resumindo,
• H aceita <M, w> exatamente quando M aceita w
• D rejeita <M> exatamente quando M aceita <M>
• D rejeita <D> exatamente quando D aceita <D>. Essa é a contradição!
TEORIA DA COMPUTAÇÃO
Uma linguagem Turing-irreconhecível
Vimos que AMT é indecidível, mas é Turing-reconhecível. Algumas linguagens não são nem Turing-reconhecíveis.
Teorema: Uma linguagem é decidível se e somente se ela e o seu complemento são Turing-reconhecíveis.
(⇾) Se uma linguagem A é decidível, ela é Turing-reconhecível (pois toda Lrec é LRE), e o complemento de uma Lrec também é uma Lrec.
TEORIA DA COMPUTAÇÃO
Uma linguagem Turing-irreconhecível
( ⇽) Se A e A são Turing-reconhecíveis, então existem os reconhecedores M1 e M2 para A e A respectivamente. É possível construir uma MT M que é um decisor para A:
M = “sobre a entrada w:
• Rode M1 e M2 sobre a entrada w em paralelo.
• Se M1 aceita, aceite. Se M2 aceita, rejeite.”
Rodar as duas máquinas em paralelo significa que M tem duas fitas, uma para simular M1 e a outra para simular M2. Nesse caso, M alternativamente simula um passo de cada máquina, o que continua até que uma delas aceite.
TEORIA DA COMPUTAÇÃO
Uma linguagem Turing-irreconhecível
M decide A pois toda cadeia ou está em A ou está em A .
Consequentemente, ou M1 ou M2 tem que aceitar w. Uma
vez que M para sempre que M1 ou M2 aceita, M sempre
pára, e portanto, é um decisor.
Corolário: AMT não é Turing-reconhecível.
Sabemos que AMT é Turing-reconhecível. Se AMT também
fosse Turing-reconhecível, AMT seria decidível. Como
sabemos que AMT não é decidível, portanto AMT não pode
ser Turing-reconhecível.
TEORIA DA COMPUTAÇÃO
Redutibilidade
O estudo da solucionabilidade de um problema pode ser feito usando o princípio da redução.
Esse principio consiste em investigar a solucionabilidade de um problema a partir de outro, cuja classe de solucionabilidade é conhecida.
Uma redução é uma maneira de converter um problema em outro.
Método principal de provar que problemas são computacionalmente insolúveis.
TEORIA DA COMPUTAÇÃO
Redutibilidade
A redutibilidade sempre envolve 2 problemas de decisão A e B. Suponha que é possível modificar o problema A de tal forma que ele se porte como um caso do problema B. Nesse caso, dizemos que A é redutível a B e:
• Se B é decidível então A também é decidível
• Se A é indecidível então conclui-se que B também é indecidível.
TEORIA DA COMPUTAÇÃO
Redutibilidade
Problema A
Problema B
Redução de A
Decidível Indecidível
TEORIA DA COMPUTAÇÃO
Redução de um problema a outro
Um PD A é redutível a um PD B, se existe um algoritmo R que, recebendo x como entrada, produz um resultado y tal que a resposta a A para x é idêntica ou complementar (a resposta complementar a sim é não, e a não é sim) à resposta a B para a entrada y, qualquer que seja a entrada x. Dizemos que o algoritmo R pode ser usado para reduzir o problema A ao problema B.
TEORIA DA COMPUTAÇÃO
Redução de um problema a outro
Assim, o problema de decisão A pode ser solucionado mediante o algoritmo R e um algoritmo para o PD B.
Chamamos R de máquina redutora
MT para B
x SIM
NÃO
Ry
MT para A
TEORIA DA COMPUTAÇÃO
Linguagens indecidíveis
Mostramos que PD são indecidíveis por contradição: Supomos que o PD é decidível e mostra que um PD indecidível conhecido é redutível a ele. Logo ele não pode ser decidível, pois se fosse o que se reduz a ele também seria (pelo princípio da redução).
1) Real problema da parada: o problema de determinar se uma MT pára (aceitando ou rejeitando) sobre uma dada entrada.
TEORIA DA COMPUTAÇÃO
Linguagens indecidíveis
PARAMT = {<M,w> | M é uma MT e M para sobre a entrada w} é indecidível.
Supomos que PARAMT é decidível. Se PARAMT é decidível, então existe uma MT R que a decide. Mostramos que AMT é redutível a PARAMT. Assim, é possível construir uma MT S que decide AMT. Com R, você pode testar se M pára sobre w. Se R indicar que M não pára sobre w, rejeite. Se R indica que M pára sobre w, você pode fazer a simulação sem qualquer perigo de entrar em loop.
TEORIA DA COMPUTAÇÃO
Linguagens indecidíveis
Prova: Supomos que a MT R decida PARAMT. Construímos a MT S para decidir AMT:
S = “Sobre a entrada <M, w>, uma codificação de
uma MT M e uma cadeia w:
1. Rode a MT R sobre a entrada <M,w>.
2. Se R rejeitar, rejeite.
3. Se R aceitar, simule a máquina M com a entrada w
até que ela pare.
4. Se M aceitou, aceite; se M rejeitou, rejeite.”
S = “Sobre a entrada <M, w>, uma codificação de uma MT M e uma cadeia w:•Rode a MT R sobre a entrada <M,w>.•Se R rejeitar, rejeite.•Se R aceitar, simule a máquina M com a entrada w até que ela pare.•Se M aceitou, aceite; se M rejeitou, rejeite.”
TEORIA DA COMPUTAÇÃO
Linguagens indecidíveis
Se a MT R existe, podemos decidir AMT; mas sabemos que AMT é indecidível. Em virtude dessa contradição, podemos concluir que R não existe. Logo, PARAMT é indecidível.
2) Testar vacuidade: determinar se a MT M não aceita nenhuma cadeia.
VMT = {<M> | M é uma MT e L(M) = ∅} é indecidível.
S = “Sobre a entrada <M, w>, uma codificação de uma MT M e uma cadeia w:•Rode a MT R sobre a entrada <M,w>.•Se R rejeitar, rejeite.•Se R aceitar, simule a máquina M com a entrada w até que ela pare.•Se M aceitou, aceite; se M rejeitou, rejeite.”
TEORIA DA COMPUTAÇÃO
Linguagens indecidíveis
Supomos que VMT é decidível. Assim, existe uma MT R que decide VMT. Mostramos que AMT se reduz a VMT, usando R para construir a MT S que decide AMT.
Modificamos <M> para garantir que M rejeite todas as cadeias exceto w, e que sobre a entrada w ela funcione normalmente. Usamos R para determinar se a máquina modificada reconhece a linguagem vazia. A única cadeia que a máquina agora aceita é w, e, portanto, sua linguagem será não vazia se e somente se ela aceita w. Se R aceita quando é alimentada com uma descrição de máquina modificada, sabemos que a máquina modificada não aceita nada e que M não aceita w.
S = “Sobre a entrada <M, w>, uma codificação de uma MT M e uma cadeia w:•Rode a MT R sobre a entrada <M,w>.•Se R rejeitar, rejeite.•Se R aceitar, simule a máquina M com a entrada w até que ela pare.•Se M aceitou, aceite; se M rejeitou, rejeite.”
TEORIA DA COMPUTAÇÃO
Linguagens indecidíveis
Prova: Supomos que a MT R decida VMT e construímos S que decide AMT da seguinte forma.
S = “Sobre a entrada <M, w>, uma codificação de uma MT e
uma cadeia w:
1. Construa a seguinte MT M1.
M1 = “Sobre a entrada x:
Se x ≠ w, rejeite.
Se x = w, rode M sobre a entrada w e aceite se M
aceita.”
2. Rode R sobre a entrada <M1>.
3. Se R aceita, rejeite. Se R rejeita, aceite.”
Se R existisse, S seria um decisor para AMT. Um decisor para AMT não pode existir, portanto sabemos que VMT é indecidível.
S = “Sobre a entrada <M, w>, uma codificação de uma MT M e uma cadeia w:•Rode a MT R sobre a entrada <M,w>.•Se R rejeitar, rejeite.•Se R aceitar, simule a máquina M com a entrada w até que ela pare.•Se M aceitou, aceite; se M rejeitou, rejeite.”
TEORIA DA COMPUTAÇÃO
Referências
Sipser, M.; Introdução à Teoria da Computação. Ed. Thomson, 2007. ISBN: 9878522104994.
Diverio, T. A.; Menezes, P. B.. Teoria da Computação: Máquinas Universais e Computabilidade. Porto Alegre: Sagra Luzzato, 2000.
Recommended