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.

401 views