Post Correspondence Problemi

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ı 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ı

[1]

, domino taşları kümesinide

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

([2], [3], [4], [5], [6])

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,

([7], [8], [9])

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=([10], [11], ... , [12])

ş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 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 [13] 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

[14]

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

[15]

yerleştir. Aşama4: P' içerisine [16] ve [17] yerleştir. Aşama5: Her bir Ґ için;

[18]

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

[19]

ve [20] yerleştir. Aşama7: En son olarak; q Kabul durumu yerleştirilir ve kabul durumu oluşturulur. 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 * 1.Post Correspondence Problemi konu alan bir puzzle * 1.Post Correspondence Problemi konu alan bir puzzle * Problèmes de correspondance de Post

Kaynaklar

Vikipedi

Post Correspondence Problemi

Post Correspondence Problemi Hakkında Detaylı Bilgi

Kaynaklar

Görüşler ve Yorumlar