Problema de Problema de Correspondência de Post Correspondência de Post

(PCP)(PCP)

Teoria da ComputaçãoTeoria da Computação

O problema PCPO problema PCP

…abc b c dg

f g eg ef

e f

c d e

b c d

b

1 2 3 4 n

Input

Pergunta : É possivel encontrar uma sequência de peças tal que o string formado na parte de cima eidêntico ao string formado na parte de baixo ?

b c d

b

e f

c d e

g

f g

b c d e f g

b c d e f g

Sequência : 3 n 1

a b c a a a b c

Exemplos Exemplos

a b cb

c a

a

a b c

c a

a

1 2 3 4

a

a b

a

a b

b

c a

c a

a

a b c

c

Sequência de peças= 2 1 3 2 4

a b c a a a b c

Exemplo Exemplo

a c c

b a

c a

a

1 2 3

a b c

a b

Input

Resposta ?? Não

Justificativa : a parte de cima das peças é sempre maior que a parte de baixo !

Formalização do Problema Formalização do Problema Input genérico do Problema PCP

C = { t1

b1,

t2

b2,

t3

b3, … ,

tn

bn}

t1, t2, …, tn são strings sobre um alfabeto S

b1, b2, …, bn são strings sobre um alfabeto S

Um pareamento (match) = uma sequência <i1, i2, …, ik> de números em {1,…,n}

tal que ti1 ti2 … tik = bi1 bi2 … bik= string do pareamento

Formalização do ProblemaFormalização do Problema

• Pergunta do problema PCP : Pergunta do problema PCP :

Existe um Existe um pareamento pareamento para o input para o input C ?C ?

Configurações de uma MT Configurações de uma MT

0 0 0 2 1 0 2 B B B B

q 0 0 0 2 q 1 0 2

q0 0 0 0 2 1 0 2 Configuração Inicial = Cin Configuração Inicial = Cin

0 0 0 2 qa 1 0 2Configuração de Aceitação = Ca Configuração de Aceitação = Ca

0 0 0 2 qr 1 0 2 Configuração de Rejeição = Cr Configuração de Rejeição = Cr

M = Máquina de Turingw = string (por exemplo w = (0002102)

Um passo de cálculoUm passo de cálculo

Configuração 1 Configuração 1 Configuração 2 Configuração 2

q

0 0 0 2 q 1 0 2 0 0 0 q 2 4 0 2

0 0 0 2 1 0 2 B B B B4

Um passo de cálculoUm passo de cálculo

q

0 0 0 2 q 1 0 2 0 0 0 2 4 q 0 2

0 0 0 2 1 0 2 B B B B4

Configuração 1 Configuração 1 Configuração 2 Configuração 2

Histórico de configuraçõesHistórico de configurações

• M : máquina de TuringM : máquina de Turing

• w = string sobre o alfabeto de Mw = string sobre o alfabeto de M

• Histórico de configurações de M em wHistórico de configurações de M em w

Cin # C1 # C2 # …. # CaCin # C1 # C2 # …. # Ca

Cin # C1 # C2 # …. # CrCin # C1 # C2 # …. # Cr

Cin # C1 # C2 # …. # Cn ….. Cin # C1 # C2 # …. # Cn …..

Problema PCP é indecidívelProblema PCP é indecidível Técnica = redução de ATM para PCP

ATM PCP

<M,w> Um conjunto de peças, onde os strings correspondem aos possiveispassos de M ao ser executada em w

String pareado = corresponderá ao histórico de aceitação de w por M

Pareamento = corresponderá aos passos executados pela máquina, partindo da configuração inicial até chegar numa configuração de aceitação.

Assim : M aceita w se e somente se existir este pareamento

Idéia de Emil Post Idéia de Emil Post

#

#Cin

Primeira peça

Cin #

C2 #

C2 #

C3 #

Cn #

Ca #

Ca #

String pareado = # Cin # C2 # C3 … # Ca #

Pareamento = sequência de peças correspondendo aos passos realizados pela máquina até chegar no estado de aceitação qa

Peças = correspondem aos passos (transições) da máquina de Turing

Exemplo Exemplo • d(qo,0) = (q1,2,R)d(qo,0) = (q1,2,R)• d(q1,1) = (q2,0,R)d(q1,1) = (q2,0,R)• d(q2,0) = (q3,2,L)d(q2,0) = (q3,2,L)• d(q2,1) = (qr,1,R)d(q2,1) = (qr,1,R)• d(q3,0) = (q3,0,R)d(q3,0) = (q3,0,R)• d(q3,2) = (q3,2,R)d(q3,2) = (q3,2,R)• d(q3,2) = (q3,2,R)d(q3,2) = (q3,2,R)• d(q3,B) = (qa,B,R)d(q3,B) = (qa,B,R)

• w = 0 1 0 0 w = 0 1 0 0

Máquina de Turing M

q0 0 1 0 0 2 q3 0 2 0 2 q1 1 0 0 2 0 q2 0 0

2 0 q3 2 0 2 0 2 q3 0 2 0 2 0 q3 2 0 2 0 B qa

IdéiaIdéia

#

# Cin #

Primeira peça

Cin #

C2 #

C2 #

C3 #

q1 1g

f g 0 q2

b c d

b

0 q2 0

q3 0 2

q0 0

2 q1

q0 0 1 0 0 # 2 q1 1 0 0 #

2 0 q2 0 0 #

1

1

2 q1 1 0 0 #

2

2

0

0

#

#

2 0 q2 0 0 #

2 q3 0 2 0 #

C3 #

C4 #

PEÇAS

#

#q0 0 1 0 0 #

#

#q0 0 1 0 0 #

ProblemaProblema

# q0 0 1 0 0 # 2 q3 0 2 0 # 2 q1 1 0 0 # 2 0 q2 0 0 # 2 0 q3 2 0 #

2 0 2 q3 0 #2 0 2 0 q3 #2 0 2 0 B qa #

Definir um conjunto fixo de peças tal que seja possivel encadearalgumas dessas peças (no caso de M aceitar w) de modo a construir o string de pareamento (em baixo e em cima da sequência das peças) :

A DESCRIÇÃO DAS PEÇAS FAZ USO DO CÓDIGO DA MÁQUINA E O STRING w