Bilgisayar Biliminde "Durma Problemi" (Halting Problem) Nedir?

"Durma problemi", Alan Turing tarafından ortaya atılan ve teorik bilgisayar biliminin temel sınırlarını gösteren, çözümü olmayan bir karar problemidir. Problem şu soruyu sorar: "Herhangi bir bilgisayar programının, herhangi bir girdi verildiğinde, sonsuza kadar çalışıp çalışmayacağını veya bir sonuca ulaşıp 'duracağını' önceden belirleyebilecek genel bir algoritma yazmak mümkün müdür?"

Turing, böyle bir genel algoritmanın var olamayacağını, mantıksal bir çelişki yaratarak kanıtlamıştır. Kanıtı, kabaca şöyle bir mantığa dayanır: Farz edelim ki, böyle bir "DurmaAnalizcisi" programı yazabildik. Bu program, girdi olarak başka bir programı ve onun girdisini alır, "durur" veya "sonsuz döngüye girer" diye cevap verir. Şimdi, bu DurmaAnalizcisi'ni kullanarak, kendi kaynak kodunu girdi olarak aldığında, eğer DurmaAnalizcisi "durur" cevabını verirse sonsuz bir döngüye giren, "sonsuz döngüye girer" cevabını verirse de hemen duran, "ParadoksProgramı" adında yeni bir program yazalım. Şimdi şu soruyu soralım: ParadoksProgramı'nı, kendi kaynak koduyla çalıştırdığımızda ne olur? Eğer duracaksa, sonsuz döngüye girmesi gerekir. Eğer sonsuz döngüye girecekse, durması gerekir. Bu, bir çelişkidir. Dolayısıyla, böyle bir genel "DurmaAnalizcisi" programı yazılamaz. Bu, bilgisayarların çözemeyeceği bazı problemlerin var olduğunun matematiksel bir kanıtıdır.

Kelimeler: durma problemi, halting problem, alan turing, bilgisayar bilimi, hesaplanabilirlik teorisi, algoritma