Post Correspondence Problemi

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Post Corrorespondence 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. Diger 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.

Problemin Tanımı[değiştir | kaynağı değiştir]

Post Correspondence 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ümasine 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 Correspondence Problemi domino kümelerinin bir kabul durumu olup olmadığına karar vermeye çalışır. Bu problem algoritmalar tarafından çözülemez.


Post Correspondence 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[değiştir | kaynağı değiştir]

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

PCP problemini kararlaştırmak için bir Tuning Makinamız 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[değiştir | kaynağı değiştir]

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ıar[değiştir | kaynağı değiştir]