Entscheidungsproblem -Entscheidungsproblem

In matematik ve bilgisayar bilimleri , Entscheidungsproblem ( telaffuz [ɛntʃaɪ̯dʊŋspʁoˌbleːm] , Alman "Karar sorunu" için) yarattığı bir sorundur David Hilbert ve Wilhelm Ackermann sorun bir sorar 1928 yılında algoritması girişi açıklamada ve cevapları gibi gördüğü "Evet" veya "Hayır", ifadenin evrensel olarak geçerli olup olmadığına , yani aksiyomları karşılayan her yapıda geçerli olup olmadığına göre .

tamlık teoremi

By Birinci derece mantık bütünlüğü teoremi yüzden, bir açıklama ve aksiyomlardan çıkarılabilir edilebilmesi halinde ise evrensel geçerlidir Entscheidungsproblem ayrıca belirli bir deyim aksiyomlarından kanıtlanabilir olup olmadığına karar vermek bir algoritma soran olarak görülebilir mantık kurallarını kullanarak .

1936'da, Alonzo Church ve Alan Turing , " etkili bir şekilde hesaplanabilir " sezgisel kavramının bir Turing makinesi tarafından hesaplanabilen fonksiyonlar (veya eşdeğeri olarak, ifade edilebilenler tarafından) tarafından yakalandığını varsayarak , Entscheidungsproblem'e genel bir çözümün imkansız olduğunu gösteren bağımsız makaleler yayınladılar . lambda taşı ). Bu varsayım şimdi Church-Turing tezi olarak biliniyor .

Sorunun geçmişi

Entscheidungsproblem'in kökeni , 17. yüzyılda başarılı bir mekanik hesaplama makinesi yaptıktan sonra , matematiksel ifadelerin doğruluk değerlerini belirlemek için sembolleri manipüle edebilen bir makine yapmayı hayal eden Gottfried Leibniz'e kadar uzanır . İlk adımın temiz bir resmi dil olması gerektiğini fark etti ve sonraki çalışmalarının çoğu bu amaca yönelikti. 1928'de David Hilbert ve Wilhelm Ackermann soruyu yukarıda özetlenen biçimde ortaya koydu.

Hilbert, "programının" devamı olarak 1928'de uluslararası bir konferansta üç soru sordu ve bunların üçüncüsü "Hilbert's Entscheidungsproblem " olarak bilinir hale geldi . 1929'da Moses Schönfinkel , Paul Bernays tarafından hazırlanan karar probleminin özel durumları hakkında bir makale yayınladı .

1930 gibi geç bir tarihte Hilbert, çözülemez bir sorun diye bir şeyin olmayacağına inanıyordu.

Olumsuz cevap

Soruya cevap verilmeden önce, "algoritma" kavramının resmi olarak tanımlanması gerekiyordu. Bu, 1935'te Alonzo Church tarafından λ-hesabına dayanan "etkili hesaplanabilirlik" kavramıyla ve sonraki yıl Alan Turing tarafından Turing makineleri konseptiyle yapıldı . Turing bunların eşdeğer hesaplama modelleri olduğunu hemen anladı .

Entscheidungsproblem'e olumsuz yanıt daha sonra 1935-36'da Alonzo Church tarafından ( Church'in teoremi ) ve bundan kısa bir süre sonra bağımsız olarak Alan Turing tarafından 1936'da ( Turing'in kanıtı ) verildi. Church, verilen iki λ-hesap ifadesinin eşdeğer olup olmadığına karar veren hesaplanabilir bir fonksiyon olmadığını kanıtladı . Stephen Kleene'nin daha önceki çalışmalarına büyük ölçüde güvendi . Turing, herhangi bir Turing Makinesinin durup durmayacağına karar veren bir "genel yöntemin" varlığı sorununu ( durma sorunu ), Entscheidungsproblem'i çözebilecek bir "algoritma" veya "genel yöntem"in varlığı sorununa indirgedi . Eğer 'Algoritma' bir Turing Makinesine eşdeğer olarak anlaşılırsa ve ikinci sorunun cevabı (genel olarak) olumsuz ise, Entscheidungsproblem için bir Algoritmanın varlığına ilişkin soru da (genel olarak) olumsuz olmalıdır. Turing, 1936 tarihli makalesinde şunları söylüyor: "Her bilgi işlem makinesine karşılık gelen 'o' bir formül 'Un(it)' oluşturuyoruz ve 'Un(it)'in kanıtlanabilir olup olmadığını belirlemek için genel bir yöntem varsa, şunu gösteriyoruz: o zaman 'o'nun hiç 0 yazdırıp yazdırmadığını belirlemek için genel bir yöntem vardır" .

Hem Church'ün hem de Turing'in çalışmaları, Kurt Gödel'in eksiklik teoremi üzerindeki önceki çalışmalarından , özellikle mantığı aritmetiğe indirgemek için mantıksal formüllere sayılar atama yönteminden (bir Gödel numaralandırması ) büyük ölçüde etkilenmiştir .

Entscheidungsproblem ilgilidir Hilbert'in onuncu sorununa bir sorar, algoritma karar vermek Diofant denklemleri bir çözümümüz var. 1970 yılında Yuri Matiyasevich tarafından kurulan böyle bir algoritmanın olmaması da Entscheidungsproblem'e olumsuz bir cevap anlamına geliyor.

Bazı birinci dereceden teoriler algoritmik olarak kararlaştırılabilir; bunun örnekleri arasında Presburger aritmetiği , gerçek kapalı alanlar ve birçok programlama dilinin statik tip sistemleri yer alır . Bununla birlikte, Peano'nun aksiyomlarında ifade edilen doğal sayıların genel birinci derece teorisine bir algoritma ile karar verilemez.

Pratik karar prosedürleri

Mantıksal formül sınıfları için pratik karar prosedürlerine sahip olmak, program doğrulaması ve devre doğrulaması için oldukça önemlidir . Saf Boolean mantıksal formüllerine genellikle DPLL algoritmasına dayalı SAT çözme teknikleri kullanılarak karar verilir . Lineer gerçek veya rasyonel aritmetik üzerinde birleşik formüller kullanılarak karar verilebilir simpleks algoritması , doğrusal tamsayı aritmetiği (formüller Presburger aritmetik ) kullanılarak karar verilebilir Cooper'ın algoritmasını veya William Pugh 'ın Omega testi . Olumsuzluklar, bağlaçlar ve ayrılıklar içeren formüller, tatmin edicilik testinin zorluklarını bağlaçların kararınınkiyle birleştirir; günümüzde genellikle , SAT çözümünü bağlaçlar ve yayılma teknikleri için karar prosedürleriyle birleştiren SMT çözme teknikleri kullanılarak karar verilir. Gerçek kapalı alanlar teorisi olarak da bilinen gerçek polinom aritmetiği karar verilebilir; bu, silindirik cebirsel ayrıştırma kullanılarak bilgisayarlarda gerçekleştirilmiş olan Tarski-Seidenberg teoremidir .

Ayrıca bakınız

Notlar

Referanslar

Dış bağlantılar