Post Correspondence Problemi sayfasının kaynağını görüntüle

{{Viki-bağlantısız|tarih=Mart 2018}}
{{Öksüz|tarih=Mart 2018}}

{{Kaynaksız}}

'''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. 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.

== Problemin Tanımı ==

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ı <br /><center><math>[a/ab]</math></center><br />, domino taşları kümesinide<br /><center><math>{([b/ca],[a/ab],[ca/a],[abc/c])}</math></center> <br />ş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.
<center><math>([a/ab],[b/ca],[ca/a],[a/ab],[abc/c])</math></center>

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. 
<br />Örnek olarak,

<center><math>([abc/ab],[ca/a],[acc/ba])</math></center>
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:
<br /><center><math>P=([t1/b1],[t2/b2], ... ,[tk/bk])</math></center>

ş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.

<center>M = (Q , Ʃ , Ґ , δ , q0 , q Kabul , q Red )</center>

Q= Durum Kümesi <br />
Ʃ=Girdi Alfabesi<br />
Ґ=Kaset Alfabesi<br />
δ=Geçiş Fonksiyonu<br />
qKabul=Kabul Durumu<br />
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:'''<br />
İlk domino [t1/b1] olarak P' içerisine 
   <center>[# / #,q0,w1,w2, ... ,wn,#]</center> yerleştir.

'''Aşama2:'''<br />
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 
   <center>eğer δ(q,a)=(r,b,R) ise P' içerisine<math> [qa/br]</math> yerleştir</center>.

'''Aşama3:'''<br />
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 
   <center>eğer δ(q,a)=(r,b,L) ise P' içerisine<math> [cqa/rcb]</math> yerleştir.</center>

'''Aşama4:''' <br />
    <center>P' içerisine [#/#] ve  [#/u#]  yerleştir.</center>

'''Aşama5:'''<br />
Her bir Ґ için;
<center><math> [cqa/rcb]</math></center> yerleştir.

'''Aşama6:'''<br />
Ґ'nin her bir a elemanı için;
<center><math> [aqKabul/qKabul]</math> ve [qKabul/qKabula]</math> </center> yerleştir.

'''Aşama7:'''<br />
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.<br />
2. Michael Sipser: "Introduction to the Theory of Computation" Course Technology Press Second Edition, 2005.

== Dış bağlantılar ==
* [http://www.theory.informatik.uni-kassel.de/~stamer/pcp/pcpcontest_en.html 1.Post Correspondence Problemi konu alan bir puzzle]
* [http://www.theory.informatik.uni-kassel.de/~stamer/pcp/pcpcontest_en.html 1.Post Correspondence Problemi konu alan bir puzzle]
* [http://www.liafa.jussieu.fr/~carton/Enseignement/Complexite/MasterInfo/Cours/pcp.html Problèmes de correspondance de Post]

[[Kategori:Karmaşıklık teorisi]]
[[Kategori:Matematik teoremleri]]