Karar Verilemezlik ve Durma Problemi
Durma problemi, belirli bir programın belirli bir girdi üzerinde nihayetinde durup durmadığını sorgular ve Turing'in hiçbir algoritmanın tüm durumlar için bu soruyu yanıtlayamayacağına dair kanıtı, karar verilemez bir problemin kurucu örneğini oluşturmaktadır.
Tanım
Bir karar problemi, hiçbir algoritmanın her girdi için doğru bir şekilde yanıtlayamadığı durumlarda karar verilemezdir; rastgele bir programın rastgele bir girdi üzerinde durup durmadığına karar veren durma problemi, kendi kendine referans veren bir köşegen argümanıyla kanıtlanmış, kanonik karar verilemez problemdir.
Kapsam
Bu konu, durma probleminin karar verilemezliğini ortaya koyan köşegenleştirme argümanını, karar verilebilir, tanınabilir ve eş-tanınabilir problemler arasındaki ayrımı, programların tüm önemsiz olmayan semantik özelliklerinin karar verilemez olduğunu gösteren Rice teoremini ve mantık, matematik ve bilgisayar bilimleri genelindeki doğal karar verilemez problemler kataloğunu kapsamaktadır.
Temel sorular
- Neden hiçbir tek algoritma her programın durup durmadığına karar veremez?
- Bir problemin karar verilebilir olması ile sadece tanınabilir olması arasındaki fark nedir?
- Program davranışının esasen tüm ilginç özellikleri neden karar verilemezdir?
- Karar verilemezlik, durma probleminden diğer problemlere nasıl yayılmaktadır?
Temel kuramlar
- Durma probleminin karar verilemezliği
- Durmaya karar veren bir algoritmanın var olduğunu varsaymak, tam olarak durmayacağı tahmin edildiğinde duran bir program aracılığıyla bir çelişkiye yol açar; bu nedenle böyle bir algoritma var olamaz.
- Rice teoremi
- Bir program tarafından hesaplanan fonksiyonun her önemsiz olmayan özelliği — davranışa dayalı olarak bazı programlar için geçerli olup diğerleri için geçerli olmayan her şey — karar verilemezdir ve durma sonucunu tüm semantik özelliklere genellemektedir.
Klinik önem
Durma ve Rice teoremi gereği, programların tüm önemsiz olmayan davranışsal özellikleri karar verilemez olduğundan, hiçbir araç sonsuz döngüleri mükemmel bir şekilde tespit edemez, rastgele doğruluğu doğrulayamaz veya her programı tam olarak analiz edemez; bu nedenle statik analizciler ve doğrulayıcılar yaklaşık sonuçlar üretmek, yanlış alarmları kabul etmek veya kapsamlarını kısıtlamak durumundadır.
Tarihçe
Turing, 1936'da Cantor ve Gödel'den esinlenen bir köşegen argümanı kullanarak durma probleminin ve mantık için karar probleminin karar verilemezliğini ortaya koymuştur. Rice, kapsamlı genellemesini 1953'te kanıtlamış ve sonraki on yıllarda, Diophantine denklemleri üzerindeki Hilbert'in onuncu problemi de dahil olmak üzere birçok doğal problemin karar verilemez olduğu gösterilmiştir.
Öne çıkan isimler
- Alan Turing
- Henry Gordon Rice
- Emil Post
- Alonzo Church
İlgili konular
Temel eserler
- turing1937
- sipser2013
Sıkça sorulan sorular
- Bir programın durup durmadığını görmek için onu çalıştırmak neden yeterli değildir?
- Programı çalıştırmak, ancak gerçekten durursa durduğunu gösterir; eğer sonsuza dek çalışacaksa, sonlu bir bekleme süresi bunu ortaya çıkarmaz. Durma problemi, her program ve girdi için sonlu sürede her zaman doğru cevabı veren bir yöntem gerektirir ve Turing böyle bir yöntemin var olmadığını kanıtlamıştır.
- Karar verilemezlik, program analizini umutsuz hale mi getirir?
- Hayır, ancak mükemmel analizin neden imkansız olduğunu açıklamaktadır. Araçlar, muhafazakar davranarak, güvenli olduğunu kanıtlayamadıkları her şeyi işaretleyerek, kısıtlı program sınıflarını tam olarak ele alarak veya düşmanca veya patolojik durumlarda başarısız olabileceklerini kabul ederek birçok pratik durumu çözerek bu durumla başa çıkmaktadır.