Redutibilidade e Teoria da Computação

•

PUC-GOIÁS

0

Vinicius Nascimento

03/04/2022

E aí, curtiu este material?

Ajude a incentivar outros estudantes a melhorar o conteúdo

Gostou desse material? Compartilhe! 🧡

Projeto e Analise de Algoritmos

331 Materiais compartilhados

Baixe o app para aproveitar ainda mais

Leia os materiais offline, sem usar a internet. Além de vários outros recursos!

Prévia do material em texto

PUC GOIÁS
ESCOLA DE CIÊNCIAS EXATAS E DA
COMPUTAÇÃO
CMP1067 Projeto e Análise de Algoritmos II
Marco A. F. Menezes
AULA 8
Referências: esta aula está baseada nos seguintes livros,
1. Walter A. Carnielli e Richard L. Epstein. Computabilidade, funções
computáveis, lógica e os fundamentos da Matemática. 2a. edição re-
vista - São Paulo: Editora UNESP, 2009.
2. Michael Sipser. Introdução à Teoria da Computação. Tradução: Ruy
José Guerra Barretto de Queiroz. São Paulo: Thomson Learning, 2007.
Aula anterior
Unidade 3 - Redutibilidade
Ideia
3.1 Redutibilidade por mapeamento
Definição 3.1 Uma função f : Σ∗ → Σ∗ é uma função computável se
alguma máquina de Turing M , sobre toda entrada w, pára com exatamente
f(w) sobre sua fita.
Exemplo Todas as operações aritméticas usuais sobre os inteiros são
funções computáveis. Em particular, definimos uma máquina de Turing que,
1
começando de 1n+1 ⊔ 1m+1, escreve 1 no espaço em branco entre os dois
blocos, vai para a esquerda e apaga os três primeiros uns e então pára (em
uma configuração padrão). Portanto, a função adição sobre os inteiros é
computável.
Definição 3.2 A linguagem A é redut́ıvel por mapeamento à linguagem
B, denotado A ≤m B, se existe uma função computável f : Σ
∗ → Σ∗, em
que para todo w,
w ∈ A ↔ f(w) ∈ B.
A função f é denominada a redução de A para B.
Teorema 3.1 Se A ≤m B e B é decid́ıvel, então A é decid́ıvel.
Demonstração
Corolário Se A ≤m B e A é indecid́ıvel, então B é indecid́ıvel.
Demonstração
Teorema 3.2 Se A ≤m B e B é recursivamente enumerável (Turing-
reconhećıvel), então A é recursivamente enumerável.
Demonstração
Observação Usamos o termo problema da parada para a linguagem AMT ,
muito embora PARAMT seja o real problema da parada. Daqui em diante,
distinguiremos entre os dois chamando AMT de problema da aceitação. As-
sim, o problema da aceitação é o problema de se determinar se uma máquina
de Turing aceita uma dada entrada, isto é,
AMT = {< M,w >; M aceita w}.
Por outro lado, o problema da parada é o problema de se determinar se uma
máquina de Turing pára (aceitando ou rejeitando) sobre uma dada entrada,
isto é,
PARAMT = {< M,w >; M para sobre w}.
Teorema 3.3 PARAMT é indecid́ıvel.
Demonstração
2
Exerćıcios para casa Fazer a Lista 3.
Próxima aula Unidade 3 - Redutibilidade: o problema da correspondên-
cia de Post.
3