Entscheidungsproblem

Entscheidungsproblem (Türkçe: karar problemi), 1928 yılında David Hilbert ve Wilhelm Ackermann tarafından tanımlanan bir matematik ve bilgisayar bilimi problemi. Problem; girdi olarak bir önerme kabul eden bir algoritmanın, çıktı olarak bu önermenin evrensel geçerliliğini ya da geçersizliğini hesaplayabilmesini tartışır. Böyle bir algoritmanın imkansız olduğu 1936 yılında Alonzo Church tarafından önerildikten hemen sonra öğrencisi Alan Turing tarafından kanıtlandı.

Alan Turing, bu problemin imkansızlığını durma problemi üzerinden kanıtladığı makalesinde a-machine (ks. automatic machine) adında ilk kez hipotetik bir hesaplama makinesi tanımladı; bu model daha sonra Turing makinesi olarak adlandırıldı.

Referans