Aula 8
Por:
Tarcisio Coutinho da Silva
{tcs5}@cin.ufpe.br
David Barros Hulak
{dbh}@cin.ufpe.br

Teorema
 Uma linguagem é Turing-decidível se e somente
se ela é Turing-reconhecível e co-Turingreconhecível.

AMT é irreconhecível
 Como AMT é reconhecível se seu complemento
fosse reconhecível, AMT seria decidível, como não
é então AMT é irreconhecível.

Uma redução de A para B é usar uma solução de B
para resolver A.

Problema da orientação na cidade: reduz-se a achar
um mapa.

Problema da área do retângulo: reduz-se a medir o
comprimento e a largura.
A é redutível a B
B é decidível
-------------------A é decidível

A é redutível a B
A não é decidível
--------------------B não é decidível
Repare que B é no mínimo tão difícil de resolver
quanto A

Se queremos provar que um problema A é
indecidível
- Encontre um problema B já comprovadamente indecidível
- Mostre que decidindo A, decidiríamos B.
- Ou seja, fazemos uma redução de B para A
- Isso é uma contradição, pois B é indecidível.

PARAMT = {⟨M, w⟩| M é uma MT e para sobre a w}

VMT = {⟨M⟩| M é uma MT e L(M) = ∅}

REGULARMT = {⟨M⟩| M é uma MT e L(M) é regular}

EQMT = {⟨M1, M2⟩| M1 e M2 são MTs e L(M1) = L(M2)}
PARAMT = {⟨M, w⟩| M é uma MT e para sobre a w}
VMT = {⟨M⟩| M é uma MT e L(M) = ∅}
(!!!) A melhor dica para compreender essa prova é entender L(M1).

Outra técnica de redutibilidade

História de computação
 Conjunto de configurações para a qual a cadeia é aceita ou
rejeitada
 Sequências finitas

Usada na prova do 10º problema de Hilbert

Máquina de Turing com memória finita

AALL = {⟨M, w⟩| M é um ALL que aceita a cadeia w}

Há ALL decisores para AALL, AAFD, AGLC, VAFD e VGL

Não há decisores para VALL, TODGLC

Seja M um ALL com q estados e f símbolos no
alfabeto da fita e comprimento de fita n. Há
exatamente n * q * fn configurações distintas.
 <> A cabeça pode estar em qualquer uma das n posições
 <> M pode estar em q estados
 <> Cada símbolo da fita pode estar em n posições:
▪ f f f (...) f
----------n vezes
(princípio da contagem)
AALL = {⟨M, w⟩| M é um ALL que aceita a cadeia w} é decidível

O objetivo é construir dominós a partir da cadeia de
entrada e emparelharmos simulando a história de
computação

PCP é indecidível

Precisamos evitar que não ocorra movimento além da
extremidade esquerda

Se w = ε, utilizamos ⊔ no lugar de w

Precisamos determinar o estado inicial (primeiro
dominó)

PCPM = { ⟨P⟩ | P é uma instância do PCP com um
emparelhamento que começa com o primeiro dominó }

PCPM é indecidível

Construção dos dominós de MT (Q, ∑, Γ, δ, qo,
qaceita, qrejeita)
 Passo 1
▪ Ponha
como primeiro dominó
 Passo 2
▪ Para toda função δ(q, a) =(r, b, D), que move para direita,
crie o dominó
 Passo 3
▪ Para toda função δ(q, a) =(r, b, E), que move para
esquerda, crie o dominó
 Passo 4
▪ Para todo a ∈ Γ, crie o dominó
 Passo 5
▪ Crie os dominós
configuração
e
, para emparelhar o fim da
 Passo 6
▪ Crie os dominós
e
, para eliminar os
símbolos a fim de emparelhar as configurações
 Passo 7
▪ Crie o dominó
para fechar o emparelhamento.

Seja a MT M = ({q0, q1, qr, qa}, {a, b}, {a, b, ⊔}, δ, q0,
qr, qa) com δ definida da seguinte forma:
δ(q0, a) = (q0, ⊔, D)
δ(q0, b) = (q1, ⊔, D)
δ(q1, a) = (qr, ⊔, D)
δ(q1, b) = (q1, ⊔, D)
δ(q1, ⊔) = (qa, ⊔, D),
Mostre o emparelhamento para a palavra aabb.

Seja uma função f: ∑* → ∑*

Se alguma M para sobre toda entrada w com
somente f(w) na fita, dizemos que f é computável

Exemplos:
 Todas as operações aritméticas são computáveis, pois podemos
construir uma máquina que recebe a entrada <m, n> e retorna m + n.
 Podemos construir uma função que receba uma MT M como entrada e
retorne essa máquina modificada M’

A linguagem A é redutível por mapeamento à linguagem B
(A ≤m B) se existe uma função computável f: ∑* → ∑* tal
que
w ∈ A ⟺ f(w) ∈ B
 A função f é chamada redução de A para B.

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 é reconhecível então A é reconhecível.

Se A ≤m B e A é irreconhecíve então B é irreconhecível.
Se A ≤m B e B é decidível então A é decidível.
Se A ≤m B e A não é reconhecível, B também não é.
A ≤m B é o mesmo que A’ ≤m B’
Sabemos que A’AMT não reconhecível.
Para provar que uma linguagem B não é reconhecível,
utilizamos:
A’AMT ≤m B
AAMT ≤m B’
EQMT não é Turing-reconhecível nem co-Turing reconhecível

Dê o esboço da prova de que PCP é indecidível

Dê o esboço da prova que VMT é indecidível

Explique por que se A ≤m B e B é reconhecível, A é
reconhecível

Michael Sipser: Introduction to the Theory of
Computation (2nd edition)
Aula 8
Arthur Ramos - [email protected]
David Hulak - [email protected]
Filipe Martins - [email protected]
Hugo Azevedo - [email protected]
Paulo Orlando - [email protected]
Ricardo Salomão - [email protected]
Tarcisio Coutinho - [email protected]
Tiago Ferreira - [email protected]
Thyago Machado - [email protected]
Vinícius Henrique - [email protected]