Durdurma Problemi ve Karar Verilemezlik
Durdurma problemi, belirli bir programın belirli bir girdi üzerinde durup durmadığına karar verme meselesi, algoritmik olarak karar verilemez bir problemin tipik bir örneğidir ve bu problemden yapılan indirgemeler, diğer birçok problemin karar verilemezliğini kanıtlamaktadır.
Tanım
Bir karar problemi, hiçbir Turing makinesinin tüm girdiler üzerinde doğru bir şekilde karar verememesi durumunda karar verilemez olarak tanımlanmaktadır; durdurma problemi, rastgele bir makinenin rastgele bir girdi üzerinde durup durmadığını sormaktadır ve diğer problemlerin indirgeme yoluyla karar verilemez olduğunun gösterildiği prototipik karar verilemez problemdir.
Kapsam
Bu konu, durdurma probleminin kesin ifadesini, köşegenleştirme (diagonalization) yoluyla karar verilemezliğinin kanıtını, karar verilemezliği aktarmak için çok-bir indirgeme (many-one reduction) tekniğini, programların önemsiz olmayan özellikleri üzerine Rice teoremini ve Entscheidungsproblem ile gruplar için kelime problemi (word problem for groups) gibi klasik karar verilemez problemleri kapsamaktadır.
Temel sorular
- Programların durup durmadığına karar veren bir algoritma neden yoktur?
- İndirgemeler, bir problemin diğerinden karar verilemez olduğunu kanıtlamak için nasıl kullanılmaktadır?
- Rice teoremi, programların özelliklerine karar verme hakkında ne söylemektedir?
- Hangi ünlü matematiksel problemlerin karar verilemez olduğu ortaya çıkmıştır?
Temel kuramlar
- Durdurma probleminin çözülemezliği
- Köşegen argümanı (diagonal argument), bir durdurma karar vericisinin varsayılmasının bir çelişkiye yol açtığını göstermektedir, bu nedenle hiçbir algoritma tüm programlar ve girdiler için durdurmaya karar veremez.
- İndirgeme ve karar verilemezlik aktarımı
- Bilinen bir karar verilemez problem hedef bir probleme indirgenirse, hedef de karar verilemez olmaktadır; bu da indirgemeyi karar verilemezliği belirlemek için standart bir araç haline getirmektedir.
- Rice teoremi
- Bir program tarafından hesaplanan fonksiyonun her önemsiz olmayan özelliği karar verilemezdir, bu nedenle programların esasen hiçbir ilginç davranışsal özelliği algoritmik olarak kararlaştırılamaz.
Klinik önem
Karar verilemezlik sonuçları, otomatik akıl yürütme ve program analizi üzerinde kesin sınırlar belirlemektedir: sonlandırmayı veya program özelliklerini doğrulamak için mükemmel genel amaçlı araçların var olamayacağını göstermekte ve mantık, cebir ve sayı teorisindeki birçok problemin neden algoritmik bir çözümü olmadığını açıklamaktadır.
Tarihçe
Turing ve Church, 1936'da, birinci dereceden geçerliliğe karar veren bir algoritma sorusu olan Entscheidungsproblem'in çözülemez olduğunu, Turing'in argümanının merkezinde durdurma probleminin yer aldığını göstermişlerdir. Rice, 1953'te bu fenomeni genelleştirmiş ve karar verilemezlik daha sonra Novikov tarafından gruplar için kelime problemi (word problem for groups) ve Matiyasevich tarafından Hilbert'in onuncu problemi gibi somut problemler için de belirlenmiştir.
Öne çıkan isimler
- Alan Turing
- Alonzo Church
- Henry Gordon Rice
- Pyotr Novikov
İlgili konular
Temel eserler
- sipser2013
- turing1936
- rogers1987
Sıkça sorulan sorular
- Daha hızlı bir bilgisayar durdurma problemini neden çözemez?
- Karar verilemezlik hızdan veya bellekten bağımsızdır: köşegen argümanı, ne kadar süre verilirse verilsin, herhangi bir algoritmayı tamamen dışlamaktadır. Durdurma problemi prensipte çözülemezdir, sadece pratik olarak imkansız değildir.
- Bir programın durup durmadığını hiç anlayabilir miyiz?
- Belirli programlar için analiz veya çalıştırma yoluyla genellikle evet. İmkansız olan, her program ve girdi için soruyu doğru bir şekilde yanıtlayan tek bir algoritmanın varlığıdır. Bu nedenle pratik sonlandırma denetleyicileri yalnızca kısıtlı sınıflarda başarılı olmakta veya bir yanıt verememektedir.