türkçeye "sonlanma problemi" olarak tercüme edilebilecek olan matematik ve bilgisayar bilimi problemidir. en basit tanımı ile bilgisayar programlarının durup durmayacağının gayrikabilitahmin oluşunu, bunu belirleme görevi atanabilecek türde bir program yazılamayacağını ele alır. (burada sözü edilen genel bir algoritmadır)
ilk bakışta bu sorun üzerinde düşünmeye dahi değmeyecek lüzumsuz bir mevzu gibi gelebilir, lakin öyle değildir. entscheidungsproblem için üç soru önem arz eder:
1) böyle bir program yazılabilseydi matematik ve bilgisayar dünyasında ne olurdu?
2) böyle bir program neden yazılamaz?
3) matematiğin soyut dünyası dışında bu problem bize tam olarak neyi ifade eder?
birinci sorudan başlayalım. şüphe yok ki, böyle bir program yazılabilseydi pek çok matematik problemi çok daha verimli bir yöntemle çözümlenebilirdi.
buna ilk örnek olarak collatz sanısını verebiliriz. bütün sayıların 1'e indirgenebileceği teoremidir. a sayısı çift ise bu a/2, tek ise de 3a+1 şeklinde indirgeme yapılabilir. bunun testi hâlâ devam etmektedir.
goldbach konjonktürünü düşünelim. 2'den büyük her çift sayının iki asal sayının toplamı şeklinde yazılabileceği iddiasıdır ki denemesi bilgisayarlarda 400,000,000,000,000'lere gelene kadar yapılmıştır.
fermat'nın son teoremi, yani "x^n + y^n = z^n" yüzyıllarca bir tartışma konusu olmuştur.
pi sayısının virgülden sonra kaç basamağı olacağını, basamakların bir sınırı olup olmadığını sadece pi değerini hesaplayan programın duracağı/durmayacağı bilgisi üzerinden anlamak mümkün olabilirdi. alan turing
ise bu makineyi yapmanın imkânsız olduğunu göstermiştir. bunu anlayabilmek için matematikçi olmaya gerek yoktur, reductio ad absurdum
dan yola çıkmak yeterlidir.
diyelim bu makineyi inşa ettik. makinenin işlevi ne? "x programı i inputu ile sonlanır mı?" sorusuna cevap vermek. bunu test edip evet veya hayır sonucunu veren makineye de m1 dedik. sonra m1'i ikinci bir makine ile birleştirdik. (o da m2 olsun) m2, m1'den gelen cevap evet ise loopa girsin, hayır ise sonlansın. bu oluşan yeni birleşik makinede yürüttüğümüz işlemin sonlanıp sonlanmayacağını, m1'in bir özdeşi ile çözümleyebilir miyiz? m1 sonlanırsa bütünsel olarak sonlanma olmaz, yok eğer sonlanmazsa da bütünsel olarak sonlanma olur. bu da kusursuz bir m1'in tasarlanamayacağının kanıtıdır.
ilginç bir şekilde, günümüzde insan beyninin algoritmik işlediğine dair bir algı vardır. bu öyle yanıltıcı bir algıdır ki, sanki beynin algoritmik olduğu kanıtlamazsa eğer; bu onun rastgele veya doğa kanunlarından azade bir işleyişe sahip olduğu anlamına gelmelidir. aksi yöndeki varsayımlar ise yapay zekanın zamanla bilinç kazanacağı çıkarımına, bilinci bilgisayarlara yükleme hayallerine kadar gidebilmektedir.roger penrose
buyurur ki; turing makineleri için bir entscheidungsproblem algoritması yoktur lakin sistem deterministiktir.
düşünsel olarak herhangi bir fiziksel sürece uygulanabilecek olan yorumlamasını sizlere bırakıyorum.