Post Karşılık Problemi

Post Karşılık Problemi (PCP), 1946 yılında Emil Leon Post tarafından ortaya atılan Automatanın kararlaştırılamazlık problemlerinden birisidir. Güncel matematik ve teorik bilgisayar bilimleri ile bir PCP örneğinin çözümü olup olmadığına karar verecek bir algoritma geliştirilemez. Diğer kararlaştırılamazlık problemlerine göre gösterimi daha kolay olduğu için kararlaştırılamazlık problemlerinin ispatında sıklıkla kullanılır.

Tanımı

Post Karşılık Problemini bir bulmaca çeşidinden yola çıkarak kolaylkla tanımlayabiliriz. Her iki yüzünde karakter dizeleri olan domino taşları kümesi düşünelim.

Tek bir domino taşını

$[a/ab]$

, domino taşları kümesinide

${([b/ca],[a/ab],[ca/a],[abc/c])}$

şeklinde ifade edebiliriz.

Burada amaç karakter dizelerinin alt ve üst sıradan dizilişlerini istenilen sayıda tekrar ile aynı hale getirmektir. Bu şekildeki bir domino kümesıne kabul durumu olan bir domino kümesi denir.

Örnek olarak takip eden domino kümesinin bir kabul durumu vardır.

$([a/ab],[b/ca],[ca/a],[a/ab],[abc/c])$

Domino taşlarının üst karakter dizesi ile alt karakter dizesi dizilişleri abcaaabc şeklindedir.

Bazı domino kümeleri içinse böyle bir kabul durumu söz konusu değildir.
Örnek olarak,

$([abc/ab],[ca/a],[acc/ba])$

domino taşları kümesinin üst satırdaki her bir karakter dizesi alt satırdaki kaakter dzesinden uzun olduğu için bir kabul durumu olamaz.

Post Karşılık Problemi domino kümelerinin bir kabul durumu olup olmadığına karar vermeye çalışır. Bu problem algoritmalar tarafından çözülemez.

Post Karşılık Problemin bir örneği:

$P=([t1/b1],[t2/b2],...,[tk/bk])$

şeklinde ifade edilir ve kabul durumu i1,i2,...,ik sadece t1, t2,..., tk=b1, b2,..., bk olduğu durumda ortaya çıkar.

Problem P'nin bir kabul durumu olup olmadığına karar verebilmektir.

İspat

Post Correpondence Problemin kararlştırlılamaz olduğunun genel ispatı, örnek bir girdi ile Tuning Makinesinin çalıştırılmasına dayanır.Kabul durumu sadece girdi Tuning Makinesi tarafından kabul edilir ise olabilir, yoksa PCP kararlaştırılabilir değildir.

PCP problemini kararlaştırmak için bir Tuning Makinesi olsun.

M = (Q, Ʃ, Ґ, δ, q0, q Kabul, q Red )

Q= Durum Kümesi
Ʃ=Girdi Alfabesi
Ґ=Kaset Alfabesi
δ=Geçiş Fonksiyonu
qKabul=Kabul Durumu
qRed=Kabul Etmeme Durumu

Eğer M'in w girdisini kabul ettiği bir durum var ise S PCP'nin bir örneğini gerçekler. Bu olayı 7 ana aşamada gösterebiliriz.

Aşama1:
İlk domino [t1/b1] olarak P' içerisine

[# / #,q0,w1,w2, ...,wn,#]

yerleştir.

Aşama2:
Kaset Alfabesinin her bir Her bir a, b elemanı için ve Durum Kümesinin her bir q,r elemanı için red durumu olmayan hallerde

eğer δ(q,a)=(r, b,R) ise P' içerisine$[qa/br]$ yerleştir

.

Aşama3:
Kaset Alfabesinin her bir Her bir a, b,c elemanı için ve Durum Kümesinin her bir q,r elemanı için red durumu olmayan hallerde

eğer δ(q,a)=(r, b,L) ise P' içerisine$[cqa/rcb]$ yerleştir.

Aşama4:

P' içerisine [#/#] ve [#/u#] yerleştir.

Aşama5:
Her bir Ґ için;

$[cqa/rcb]$

yerleştir.

Aşama6:
Ґ'nin her bir a elemanı için;

$[aqKabul/qKabul]$ ve [qKabul/qKabula]</math>

yerleştir.

Aşama7:
En son olarak; q Kabul durumu yerleştirilir ve kabul durumu oluşturulur.

Kaynakça

1. E. L. Post (1946). "A variant of a recursively unsolvable problem". Bull. Amer. Math. Soc 52.
2. Michael Sipser: "Introduction to the Theory of Computation" Course Technology Press Second Edition, 2005.

Dış bağlantılar

• 1.Post Karşılık Problemi konu alan bir puzzle
• 1.Post Karşılık Problemi konu alan bir puzzle
• Problèmes de correspondance de Post 3 Eylül 2009 tarihinde Wayback Machine sitesinde arşivlendi.