Yazan : Şadi Evren ŞEKER

Problem kısaca bir programın bir zaman sonra durup durmayacağının belirsizliği üzerine tartışmadır.

Yani basitçe elimizde bir program ve bu programın parametresi olsun (programa verilebilen bir girdi). Programın bitip bitmeyeceğini bilemeyiz.

Peki bunu nasıl ispatlarız? Burada ispat için olmayana ergi (proof by contradiction) kullanılabilir. Önecelikle problemimizi modelleyelim:

D(P,G) : P, programının verilen G girdisi ile durup durmayacağı olsun.

Buna göre D(P,G) sonucunda ya durur ya da durmaz sonuçlarından birisi çıkacak.

Biliyoruz ki bir programın kendisi de bir girdidir. En azından programın kendisi bir bilgidir ve bu bilginin yazıldığı dilde bir metin olması ve bir veri şeklinde gösterilmesi mümkündür. Öyleyse D(P,P) gösterimi bir programa kendisinin girdi olarak verilmesi durumudur. Basitçe bir programı girdi alan bir program var ve bu program girdi olarak aldığı programın bitip bitmeyeceğine karar verecek şeklinde düşünülebilir. Çünkü yapmak istediğimiz tam da budur. Bir programın bitip bitmediğine karar veren bir program bulmak istiyoruz, öylesyse acaba bu bulmaya çalıştığımız ve bir programın bitip bitmediğine karar veren programın kendisinin bitip bitmeyeceğine aynı program karar verebilir mi?

D(P,P): kendisinin bitip bitmeyeceğine karar vermeye çalışan programımız olsun.

Şimdi olmayana ergi (proof by contradiction) kullanılacağı için D(P,P)’nin terisini almalıyız. Öyle bir T(P) tanımlayalım ki üzeirnde çalıştığımız P programı için D’nin tersi olsun ve D(P,P) durur dediğinde T(P) durmaz, D(P,P) durmaz dediğinde ise T(P) durur desin.

Şimdi artık çelişkimizi ortaya koyabiliriz. D(T,T) şayet sonuç olarak durmaz çıkarırsa tanımı itibariyle biliyoruz ki T(T) durur çıkarmalıdır. Tersi durumda D(T,T) şayet sonuç olarak durur çıkarırsa, T(T) durmaz çıkarmalıdır. Buradaki iki durumda da çelişki vardır çünkü T girdisi D(T,T) işleminde şayet durur çıkarıyorsa T(T) işleminde de durur çıkarmalıdır. (Tanımı itibariyle T ya durur ya durmaz, birisinde durur diğerinde durmaz çıkarması bir çelişkidir). Tersi durum olan D(T,T) için durmaz çıkarıyorsa T(T) için de durmaz çıkarmalıdır. Ancak görüldüğü üzere bu sonuçların tam tersi çıkarılmıştır. Bu durumda bir çelişkidir.

Sonuç olarak D her zaman doğru sonuçları veremez. Bunun anlamı durup durmayacağına karar verilebilen bir D yazılamaz demektir.

Basit Anlatımı

Çok saygı duyduğum bir hocam tarafından, burada yazılanların arasındaki bağlantıda problem olduğu söylendi . Bunun üzerine olayı çok daha basit bir şekilde anlatmaya çalışıyorum.

Durma problemi, bir programın durup durmayacağının asla bilinememesidir.

Yani hiçbir zaman bir program yazıp, bütün programların bitip bitmeyeceğine karar veremeyiz, böyle bir program yazılamaz.

Bunu anlamanın en kolay yolu, basit bir öz çelişkiden (self contradiction) geçer.

Örneğin bir program yazıp, programların bitip bitmeyeceğini (durup durmayacağını, halt) bulmayı hedeflediğimizi düşünelim. Ve bu programa T ismini verelim.

Dolayısıyla T(P) gibi bir yapı olacak ve T programımız, P programını parametre olarak alıp, bu programın bitip bitmeyeceğini söyleyecektir.

Şimdi öz çelişki (self contradiction) oluşturan duruma bakalım ve soralım acaba T(T) ne döndürür?

Yani programların bitip bitmeyeceğini söyleyen T programını kendisine parametre olarak verirsek ne olur?

Diğer bir deyişle, bir program yazıp, programların bitip bitmeyeceğini bulmak istiyoruz, peki bu program kendisinin bitip bitmeyeceğini söyleyebilir mi?

Elbetteki hayır.

Dolayısıyla bir programın bitip bitmeyeceğini bulan başka bir program yazılırsa, bu program en az kendisinin bitip bitmeyeceğini söyleyemeyecek ve dolayısıyla bütün programların bitip bitmeyeceğini söyleyebilecek bir program yazılamayacaktır.

Yorumlar

  1. latex

    bence yine dogru degil, diger programlarin bitip bitmeyecegine karar veren bir program veya turing machine degil. bu ozel bir bilgin falci veya kahin gibi birsey.

    burada onemli olan, zaten biz programin bitip bitmeyecegini bilemiyoruz, ama diyelim ki bilen bir kahin var, bunu bilen bir kahin bile olsa yine de bunu bilemeyiz.

    siz kahini kahine girdi verip sonuc almaya calisiyorsunuz, ama kahin sadece herhangi bir turing makinesine verilen girdinin bitip bitmeyecegini soyluyor, bunu soyleyen biri bile olsa yine de contradiction olusur deyip olayi kapatiyor, benim anladigim budur.

  2. Şadi Evren ŞEKER Article Author

    Evet çok farklı yaklaşımları var, sanırım kast ettiğiniz oracle machine (kahin makinesi) bu yaklaşım için haklısınız, yani bir makinenin çalışıp çalışmayacağını kahin söylese bile bu sefer kahinin bitip bitmeyeceğini bilemeyiz durumu.

    Ancak burada oracle machine, aslında turing makinesinin belirli bir girdi için yaptığını, herhangi bir girdi için genellemeyememekten kaynaklanan probleme işaret eder.

    Aslında bu durum bütün problemlerin sayılamaz olduğu ile de gösterilebilir. Örneğin öyle bir girdi verilebilir ki turing makinesi çalışamaz, bunu cantor ispat etmiştir, aşağıdaki yazıda biraz değinmeye çalışmıştım:

    http://www.bilgisayarkavramlari.com/2010/03/31/cardinality-sayisallik/

    Başarılar

  3. Emir Rencber

    Bence eksik bir yazı. Programın sona erip ermeyeceği hakkında durulmuş sadece. Daha açık olarak anlatmak gerekirse, turing makinesinin bandına bir kelime koyuyoruz, ve bu kelimenin sahip olduğumuz dile ait olup olmadığını anlamaya çalışıyoruz. Örneğin kelimemiz o kadar uzun olabilir ki, alfebemiz sadece a harfinden oluşmaktadır, makinemiz çok uzun bir süre a okumuştur ama banda koyduğumuz kelimenin sonuna ulaşamamştır; fakat belki 3 milyar harf sonra bir b harfi olabilir, veya olmayabilir. bunu bilemediğimiz için makinenin durduğu varsayılır. Bu yüzden de haltingproblem semidecidable idir zaten. Decidable olup olmadığına karar veremeyiz, ama not decidable da diyemeyiz.
    Selamlar

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir