itc aula8

Prévia do material em texto

26/10/2012
1
COMPUTABILIDADE
DECIDIBILIDADE
REDUTIBILIDADE
INTRODUÇÃO À TEORIA DA 
COMPUTAÇÃO
1
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Introdução
� Após o estudo de diversas linguagens, gramáticas e
máquinas, algumas questões da Teoria da Computação
podem ser levantadas, tais como:
� Quais as capacidades e limitações fundamentais dos
computadores?
� O que pode e o que não pode ser resolvido pelos computadores?
� O que faz alguns problemas serem computacionalmente mais
difíceis que outros?
� Estas questões são respondidas através dos conceitos
de computabilidade, decidibilidade, redutibilidade* e
complexidade*.
2
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
26/10/2012
2
Computabilidade e Decidibilidiade
� Em 1900, em um congresso de
internacional de matemática,
David Hilbert propôs dez
problemas sem solução até
aquele momento
� Mais tarde, outros treze problemas
foram publicados
� Dos vinte e três problemas, seis
estão sem solução e três
parcialmente resolvidos.
� Fonte: Wikipédia
3
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Computabilidade e Decidibilidiade
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
4
� Um dos problemas, o de número 10, é de interesse da 
Teoria da Computação:
� Equação diofantina é uma equação polinomial 
indeterminada em que as incógnitas só podem assumir 
valores inteiros. Exemplo: x2 + y2 = z2
Encontrar um algoritmo que determine se
uma equação diofantina tem solução
26/10/2012
3
Computabilidade e Decidibilidiade
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
5
� Em 1931, o Teorema da Incompleteza de Godel
demonstrou que a mecanização do processo de prova 
de teorema não tinha solução
� Isso provou a incompleteza da Lógia de Primeira Ordem, mas não 
faz referência a computação
� Church e Turing definiram ferramentas/modelo para 
definir algoritmos de uma forma precisa (cálculo 
lambda e Máquina de Turing) para provar a 
indecidibilidade do problema acima
Computabilidade e Decidibilidiade
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
6
� Outros modelos foram construídos, tais como Funções
Recursivas, Algortimos de Markov, Cálculo Lambda,
Máquinas de Registro, Sistemas Post, Máquina de
Turing e etc.
� Para estudar os limites da computação, vamos utilizar a
Máquina de Turing
26/10/2012
4
Computabilidade e Decidibilidiade
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
7
� Tese de Turing
� Hipótese de Church
Qualquer computação que possa ser executada por
meios mecânicos pode ser executada por uma
Máquina de Turing
A capacidade de computação representada pela
Máquina de Turing é o limite máximo que pode ser
atingido por qualquer dispositivo de computação
Computabilidade e Decidibilidiade
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
8
� Vale destacar que:
� Pode existir uma linguagem que não é reconhecida pela Máquina 
de Turing
� Se uma linguagem é reconhecida pela Máquina de Turing então 
ela é uma Linguagem Recursivamente Enumerável
� Se a Máquina de Turing sempre pára (aceitando ou rejeitando) 
para uma dada cadeia então a Linguagem é Recursiva
26/10/2012
5
Computabilidade e Decidibilidiade
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
9
� Assim, de acordo com as definições estudadas a 
respeito de Máquina de Turing, temos:
� Se a Máquina de Turing M sempre pára com a resposta SIM, se a 
cadeia pertence a Linguagem, e NÃO, quando a cadeia não 
pertence a Linguagem, então tem a decidibilidade desse 
domínio, ou seja M é decidível
� Se a Máquina de Turing M sempre pára com a resposta SIM, se a 
cadeia pertence a Linguagem , e nem sempre pára, quando a 
cadeia não pertence a Linguagem, então a linguagem é somente 
aceita e não decidível
� Se a Máquina de Turing M calcula uma função num certo domínio, 
a função é computável;
Classes de Solucionabilidade de Problemas
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
10
� Problema Solucionável: um problema é dito Solucionável ou
Totalmente Solucionável se existe um algoritmo (Máquina
Universal) que solucione o problema tal que sempre termine
para qualquer entrada, com uma resposta afirmativa (aceita)
ou negativa (rejeita).
� Problema Não-solucionável : um problema é dito Não-
Solucionável se não existe um algoritmo (Máquina Universal)
que solucione o problema tal que sempre termine para
qualquer entrada.
Solucionáveis Não Solucionáveis
Universo de Todos os Problemas
26/10/2012
6
Classes de Solucionabilidade de Problemas
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
11
� Problema Parcialmente Solucionável ou Computável: se existe
um algoritmo (Máquina Universal) que solucione o problema
tal que termine quando a resposta é afirmativa (aceita).
Entretanto, quando a resposta esperada for negativa, o
algoritmo pode terminar (rejeita) ou permanecer
processando indefinidamente (loop).
� Problema Completamente Insolúvel ou Não-Computável: se
não existe um algoritmo (Máquina Universal) que solucione o
problema tal que termine quando a resposta é afirmativa
(aceita).
Parcialmente Solucionáveis
(Computáveis)
Completamente Insolúveis
(Não-Computáveis)
Universo de Todos os Problemas
Classes de Solucionabilidade de Problemas
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
12
Solucionáveis Não Solucionáveis
Relação entre as classes de problema
Parcialmente Solucionáveis
(Computáveis)
Completamente Insolúveis
(Não-Computáveis)
Parcialmente Solucionáveis Completamente Insolúveis
26/10/2012
7
Classes de Solucionabilidade de Problemas
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
13
� A união das Classes dos Problemas Solucionáveis e dos Não
Solucionáveis é o Universo de Todos os Problemas
� A união das Classes dos Problemas Parcialmente Solucionáveis e
dos Completamente Insolúveis é o Universo de Todos os Problemas
� A Classe dos Problemas Parcialmente Solucionáveis contém
propriamente a Classe dos Problemas Solucionáveis e parte da
Classe dos Problemas Não-Solucionáveis
� Todo problema solucionável é parcialmente solucionável
� Existem problemas não-solucionáveis que possuem solução parcial
� Os problemas completamente insolúveis não possuem solução total
nem parcial
Considerações Finais
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
14
� Procedimento é uma seqüência finita de instruções, sendo uma 
instrução uma operação claramente descrita, que pode ser 
executada mecanicamente, em tempo finito
� Algoritmo é um procedimento cuja execução termina para 
qualquer dado de entrada
� Uma função é dita computável se existir um procedimento que a 
compute
� A abordagem operacional de Turing permitiu Von Neuman
elaborar o modelo para construção de máquinas digitais
� A abordagem lingüística de Chomsky permitiu o desenvolvimento 
de teorias para concepção das linguagens de programação
26/10/2012
8
Considerações Finais
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
15
� Considerações:
� O principal conceito estudado é o de computabilidade, o qual é 
construído, usando noções de programas, máquinas e 
computações.
� São três conceitos distintos, mas diretamente relacionados, pois 
um programa para uma máquina pode induzir uma computação.
� Se ela for finita, então se define ainda a função computada por 
esse programa nessa máquina:
� Ela descreve o que o programa faz.
Considerações Finais
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
16
� Considerações:
� A distinção entre programa e máquina é importante na Ciência da 
Computação,uma vez que o programa (ou algoritmo) independe 
da máquina e possui uma complexidade estrutural e 
computacional quantidade de trabalho necessário para resolver o 
problema).
� A partir do conceito de função computada, podem-se fazer 
comparações entre programas e entre máquinas e definir-se a 
equivalência dos mesmos.
26/10/2012
9
Considerações Finais
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
17
� Considerações:
� Se dois programas, em uma máquina, possuem a mesma função 
computada, ou seja, computam a mesma função, então eles são 
equivalentes.
� Se esses programas são equivalentes em qualquer máquina, 
então eles são equivalentes fortemente.
� Utiliza-se o conceito de equivalência de programas para eliminar 
instruções desnecessárias e para otimizar o programa.
� Dessa forma, pode-se dizer que um programa otimizado 
representa uma classe de programas que são equivalentes
Considerações Finais
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
18
� Considerações:
� A comparação entre máquinas é feita em função da noção de 
simulação, que, por sua vez, utiliza-se do conceito de equivalência 
de programas:
� Se uma máquina simula outra, é porque, para qualquer programa da 
outra máquina, pode-se encontrar um programa desta que faça a 
mesma coisa.
� Se duas máquinas simulam-se mutuamente, é porque elas são 
equivalentes.
� Nesse caso, ambas têm o mesmo poder computacional
26/10/2012
10
Considerações Finais
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
19
� Considerações:
� Foi observado que nem sempre o fato de acrescentar instruções 
ou recursos a uma máquina aumenta o poder computacional da 
mesma.
� Muitas vezes, ocorre que essa nova instrução ou esse novo 
recurso podem ser simulados pela máquina anterior, mantendo o 
seu poder computacional.
� Neste ponto, pode-se pensar em suas situações limites:
� Qual a máquina mais poderosa?
� Qual o conjunto ou a classe de funções computáveis?
� As respostas dessas perguntas são intuitivas, mas nem sempre 
são fáceis de serem verificadas.
Considerações Finais
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
20
� Considerações:
� Diz-se que uma máquina é universal se toda função computável 
puder ser executada nela.
� E, segundo a Hipótese de Church, diz-se que uma função 
computável é aquela que pode ser processada numa Máquina de 
Turing ou equivalente.
� Assim, não se conseguem demonstrar tais afirmações, devido ao 
fato de a noção de algoritmo ser algo intuitivo.
� Entretanto, diversas evidências fortalecem a Hipótese de Church.
26/10/2012
11
Problemas Indecidíveis
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
21
� Um problema é decidível se sua solução é encontrada 
em um tempo finito, ou seja, se existe uma Máquina de 
Turing que retorna uma resposta. Caso contrário, o 
problema é indecidível
� Com relação a linguagem, se um problema pode ser 
representado por uma linguagem recursiva (onde a 
Máquina de Turing sempre pára) então o problema é 
decidível
Problemas Indecidíveis
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
22
� O conceito de decidibilidade não trata a quantidade de 
tempo gasto, mas se este é finito 
� Complexidade é que trababalha com a quantidade de 
tempo gasto
26/10/2012
12
Problemas Indecidíveis
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
23
� (A) Problema de Parada
� Dada uma Máquina de Turing M genérica e uma entrada Genérica 
w, não existe uma Máquina de Turing M’ capaz de decidir se M 
executa uma computação que aborta (pára), quando começa o 
processamento numa configuração inicial q0w 
� Se o problema de parada fosse decidível então toda Linguagem 
Recursivamente Enumerável deveria ser Linguagem Recursiva. 
Consequentemente o problema de parada é indecidível
Problemas Indecidíveis
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
24
� (B) Problema de Entrada num Estado
� Dada uma Máquina de Turing M = (∑ , Q, δ, q0, F, V, β, ⊛ ) e 
qualquer q ∈ Q e w ∈ ∑+, decidir se o estado q é sempre visitado 
quando a Máquina de Turing é aplicada a w não é possível. Esse 
problema é indecidível.
� Poder-se-ia construir uma Máquina de Turing M’ que sempre 
pára quando entra no estado q. Assim ter-se-ia a garantia de que 
a Máquina de Turing entrava no estado q. Só que o problema de 
parada é indecidível então o problema de estado também é 
indecidível.
26/10/2012
13
Problemas Indecidíveis
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
25
� (C) Problema de Parada numa fita em Branco
� Dada uma Máquina de Turing M, determinar se M pára se 
começar com uma fita em branco é indecidível.
� Poder-se-ia construir uma Máquina de Turing MW que começa 
com fita em branco, escreve w nela e se posiciona na configuração 
q0w. Fica claro que MW pára na fita em branco se e somente se, M 
aceita a cadeia w, ou seja, pára com a entrada w. Só que o 
problema de parada é indecidível, então esse também é.
Problemas Indecidíveis
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
26
� (D) Linguagem gerada por uma Gramática Irrestrita é 
nula
� Seja G uma Gramática Irrestrita. Então o problema de determinar 
se L(G) =∅ é indecidível.
� Se existe uma Máquina de Turing para G então a linguagem aceita 
é uma Linguagem Recursivamente Enumerável. Então L(G) = ∅, 
com G sendo uma Gramática Irrestrita, não é decidível.
26/10/2012
14
Problemas Indecidíveis
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
27
� (E) Linguagem gerada por uma Máquina de Turing é 
finita
� Seja M uma Máquina de Turing, então a questão se L(M) é finita é 
indecidível. 
� Como o problema de parada não é decidível, então saber se o 
conjunto das cadeias geradas pela Máquina de Turing é finito não 
é possível. Então esse problema é indecidível.
Problemas Indecidíveis
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
28
� Teorema de Rice
� Então, sendo M uma Máquina de Turing
� Se L=L(M), decidir se L é uma Linguagem Regular é indecidível
� Se L=L(M), decidir se L é uma Linguagem Livre do Contexto é 
indecidível
� Se L=L(M), decidir se L é uma Linguagem Sensível ao Contexto é 
indecidível
� Se L=L(M), decidir se L é uma Linguagem Recursiva é indecidível
Qualquer propriedade de linguagens reconhecidas
por Máquina de Turing é indecidível
26/10/2012
15
Redutibilidade
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
29
� Converter um problema em outro de tal modo que a 
solução para o segundo pode ser utilizada para 
resolver o primeiro
� Reduzir um problema A para um problema B usando 
uma redução de mapeamento significa que existe uma 
função computável que converte instâncias do 
problema A para instâncias do problema B
Redutibilidade
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
30
� Se uma tal conversão (função de) existir, chamada de 
uma redução, pode-se resolver A como um resolvedor
(solucionador) para B 
� Se A redutivel a B (A ≤ B) e B é decidível então A é decidível
� Se A redutivel a B (A ≤ B) e A é indecidível então B é indecidível
Uma linguagem A é redútivel por mapeamento para
uma linguagem B, A ≤ B, se existe uma função
computável f: ∑* � ∑* onde para todo w,
w ∈ A ⇔ f(w) ∈ B