Durdurma problemi

Halting problemi bilgisayar bilimlerinde bir problemdir. Problem, bir bilgisayar programına bakarak programın sonsuza kadar çalışıp çalışmayacağını bulmaktır. Eğer bir program başka bir programa bakıp o programın sonsuza kadar çalışıp çalışmayacağını söyleyebiliyorsa o programın "durma problemini çözdüğünü" söyleriz.

Örneğin, bunun gibi bir program:

while True: devam et;

sonsuza kadar dönecek, ancak program

while False: devam et;

çok çabuk durur.

Durma sorununu çözen bir program var mı? Olmadığı ortaya çıktı. Bu gerçeği, eğer yarılanma problemini çözen bir program varsa, imkansız bir şeyin gerçekleştiğini göstererek kanıtlıyoruz. Bu yüzden şimdilik gerçekten yarılanma problemini çözen bir program varmış gibi davranacağız. Burada P, F fonksiyonunu (I argümanı ile çağrılan) değerlendirecek ve sonsuza kadar çalışırsa true, aksi takdirde false döndürecek bir fonksiyondur.

def P(F, I): if F(I) runs forever: return True; else: return False;

P herhangi bir programa bakabilir ve sonsuza kadar çalışıp çalışmayacağını öğrenebilir. P'yi Q adını vereceğimiz yeni bir program yapmak için kullanırız. Q'nun yaptığı şey başka bir programa bakmak ve ardından aşağıdaki soruyu yanıtlamaktır: "Eğer bu programı çalıştırır ve kendisinin bir kopyasına bakmasını sağlarsak, sonsuza kadar çalışır mı?". Tek yapmamız gereken Q'ya eski programın kendisine baktığı yeni bir program yaratmasını söylemek ve ardından yeni programın sonsuza kadar çalışıp çalışmayacağını öğrenmek için P'yi kullanmaktır.

def Q(F): return P(F, F);

Şimdi başka bir R programı yapıyoruz. R başka bir programa bakıyor ve Q'dan bu programla ilgili cevabını istiyor. Eğer Q "evet, eğer bu programı çalıştırırsak ve kendisinin bir kopyasına bakmasını sağlarsak sonsuza kadar çalışacaktır" cevabını verirse, R durur. Eğer Q "hayır, eğer bu programı çalıştırır ve kendi kopyasına bakmasını sağlarsak, sonsuza kadar çalışmayacaktır" cevabını verirse, R sonsuz bir döngüye girer ve sonsuza kadar çalışır.

def R(F): if Q(F): return; //terminate else: while True: continue; //loop forever

Şimdi R'nin kendisinin bir kopyasına bakmasını sağlarsak ne olacağına bakacağız. İki şey olabilir: ya duracak ya da sonsuza kadar çalışacaktır.

Eğer R'yi çalıştırıp kendi kopyasına bakmasını sağlamak sonsuza kadar çalışmıyorsa, Q "evet, eğer bu programı çalıştırıp kendi kopyasına bakmasını sağlarsak sonsuza kadar çalışacaktır" cevabını vermiştir. Ancak Q bunu R'nin kendisine bakarken söylemiştir. Yani Q'nun aslında söylediği şudur: "evet, eğer R'yi çalıştırır ve kendisinin bir kopyasına bakmasını sağlarsak sonsuza kadar çalışacaktır". Yani: Eğer R kendi kopyası üzerinde çalışıyorsa sonsuza kadar çalışmaz, o zaman sonsuza kadar çalışır. Bu imkansızdır.

Eğer R'yi çalıştırıp kendi kopyasına bakmasını sağlamak sonsuza kadar çalışıyorsa, Q "hayır, eğer bu programı çalıştırıp kendi kopyasına bakmasını sağlarsak sonsuza kadar çalışmayacaktır" cevabını vermiştir. Ancak Q bunu R'nin kendisine bakarken söylemiştir. Yani Q'nun aslında söylediği şudur: "hayır, eğer R'yi çalıştırır ve kendisinin bir kopyasına bakmasını sağlarsak sonsuza kadar çalışmaz". Yani: Eğer R kendisinin bir kopyası üzerinde çalışıyorsa sonsuza kadar çalışır, o zaman sonsuza kadar çalışmaz. Bu da imkansızdır.

Ne olursa olsun, imkansız bir durumla karşı karşıyayız. Yanlış bir şey yaptık ve bunun ne olduğunu bulmamız gerekiyor. Yaptığımız şeylerin çoğu yanlış değildi. "Bir programın kendi kopyasına bakmasını sağlamak yanlıştır" ya da "başka bir programın söylediklerine bakıp bir şey söylerse döngüye girmek, başka bir şey söylerse durmak yanlıştır" diyemeyiz. Bunları yapmamıza izin verilmediğini söylemek mantıklı değildir. Yaptığımız ve yanlış gibi görünen tek şey, P gibi bir program varmış gibi davranmış olmamızdır. Yanlış olabilecek tek şey bu olduğuna ve bir şey yanlış olmak zorunda olduğuna göre, yanlış olan da budur. Bu, P gibi bir programın var olmadığının kanıtıdır. Durma problemini çözen bir program yoktur.

Bu kanıt 1936 yılında Alan Turing tarafından bulunmuştur.

Sorular ve Yanıtlar

S: Halting problemi nedir?

C: Halting problemi, bilgisayar biliminde bir bilgisayar programını inceleyen ve programın sonsuza kadar çalışıp çalışmayacağını belirleyen bir problemdir.

S: Bir programın halting problemini çözüp çözmediğini nasıl anlarız?

C: Bir program başka herhangi bir programa bakıp o programın sonsuza kadar çalışıp çalışmayacağını söyleyebiliyorsa o programın "durma problemini çözdüğünü" söyleriz.

S: Böyle bir programın var olmadığını kanıtlamanın bir yolu var mı?

C: Evet, eğer böyle bir program olsaydı imkansız bir şey olacağını göstererek. Bu kanıt 1936 yılında Alan Turing tarafından bulunmuştur.

S: P ne işe yarar?

C: P, başka bir F fonksiyonunu (I argümanı ile çağrılan) değerlendiren ve sonsuza kadar çalışırsa doğru, aksi takdirde yanlış döndüren bir fonksiyondur.

S: Q ne yapar?

C: Q başka bir programa bakar ve ardından aynı programı kendi üzerinde çalıştırmanın sonsuz döngüyle sonuçlanıp sonuçlanmayacağı sorusunu yanıtlar. Bunu, verilen F fonksiyonunun bir değerlendirmesini yapmak için P'yi kullanarak yapar.

S: R ne yapar?

C: R başka bir programa bakar ve Q'ya bu programla ilgili cevabını sorar. Eğer Q "evet, eğer bu programı çalıştırırsak ve kendi kopyasına bakmasını sağlarsak sonsuza kadar çalışacaktır" cevabını verirse, R durur; ancak Q "hayır, eğer bu programı çalıştırırsak ve kendi kopyasına bakmasını sağlarsak sonsuza kadar çalışmayacaktır" cevabını verirse, R sonsuz bir döngüye girer ve sonsuza kadar çalışır.

S: R'nin kendisine bakmasını sağladığınızda ne olur?

C: İki şey olabilir - ya R durur ya da sonsuza kadar çalışır - ancak P gibi programların var olmadığı konusunda kanıtlananlara göre her iki sonuç da imkansızdır, bu nedenle R'nin kendisine bakmasını sağlamaya giden yolda bir yerlerde bir şeyler yanlış gitmiş olmalıdır.