Karar Verilebilirlik

Bu makale matematik ve bilgisayar bilimlerinde "karar verilebilirlik" teriminin özel anlamlarını tartışmaktadır . Daha genel bir yaklaşım için karara bakın .

Gelen matematiksel mantık terimi karar verilebilirlik : iki ilişkili kavramları kapsar mantıksal karar verilebilirlik ve algoritmik karar verilebilirlik .

Kararsızlık karar verilebilirlik olumsuzlanmasıdır. Her iki durumda da, mantıklı bir biçimde olsa bile kendimize bir soru sorduğumuzda her zaman sonuca varamayacağımız fikrini resmileştirme meselesidir.

Mantıksal bir sistemde bir ifadenin karar verilebilirliği, karar verilemezliği

Bir önerme (bir de bildiri diyor) olduğu söylenir Karar verilebilen bir in aksiyomatik teori bunun ortaya konabilir ya da yadsınması bu teorinin çerçevesinde gösterdi eğer. Bu nedenle, matematiksel bir ifadenin, bu teorinin aksiyomlarından çıkarılması veya olumsuzlamasının çıkarılması imkansızsa, bir teoride karar verilemez. Bu karar verilemezlik kavramını algoritmik karar verilemezlik kavramından ayırmak için (aşağıya bakınız), ifadenin aksiyomlar sisteminden bağımsız olduğunu da söylüyoruz . Bu durum özellikle, birlikte Öklid ' ünlü paraleller önermesiyle nispeten için, onun geometri ve hatta birlikte, süreklilik hipotezi nispeten için olağan küme teorisinin hiçbir orada hangi göre, kardinal l arasındaki. Doğal set sayıları ve bu ait gerçek sayılar kümesi , Paul Cohen undecidable olmak 1963 yılında gösterdi.

Gelen Klasik Mantık göre tamlık teoremi varsa, bir önerme bir teoride undecidable modelleri bu doğrudur önerme yanlıştır teori ve modellerin. Modeller genellikle bir ifadenin bir aksiyom sisteminden bağımsız olduğunu göstermek için kullanılır (bu bağlamda, karar verilemez değil bağımsız kullanmayı tercih ederiz ). Bu durumda kullanılan özellik, tamlık teoremi değil, düzeltme teoremi olarak adlandırılan, çok acil olan tersidir . Muhtemelen bu, tesadüfen, inşaat ile konsept modelinin ilk görünümü, XIX inci  yüzyıl modelleri Öklid dışı geometrilerin değil paralellik aksiyomu kontrol. Oldukça sezgisel olarak Öklid geometrisinin tutarlı olduğunu kabul edersek - paralellik aksiyomunun olumsuzlanması diğer aksiyomlardan çıkarılmaz - paralellik aksiyomu gerçekten de diğer geometri aksiyomlarından bağımsızdır veya sistemde karar verilemez. kalan aksiyomlardan oluşur.

Bir matematiksel teori her deyim Karar verilebilen olduğu söylenir tam aksi halde olduğu söylenir, eksik . Pek çok matematiksel teori eksiktir, çünkü teorinin dilinde ifade edilebilen, aksiyomlarla belirlenmeyen ifadeler vardır (grup teorisi, halkalar…). Böyle teorisi gibi bazı teoriler, cebirsel kapalı alanlarda a verilen karakteristik yüzden, kapalı gerçek alanlar , hatta Presburger en aritmetik , tamamlandı. Eksiklik teoremi arasında Gödel herhangi olduğunu garanti aksiyomatik teori , tutarlı ve temsil etmek yeterince güçlü Peano aritmetik (her zamanki aritmetik), eksik o (aşağıya bakınız) biz algoritmik anlamda karar verebilmeniz axiomatized şartıyla, olsun veya olmasın bir ifade bir aksiyomdur. Belirtmesi biraz karmaşık görünen bu son hipotez çok doğaldır ve matematikteki olağan aksiyomatik teoriler tarafından doğrulanmıştır .

Karar verilebilirlik, bir karar probleminin algoritmik kararsızlık

Tanım

Bir algoritma , sonlu sayıda adımla biten, buna karar veren, yani sorunun sorduğu soruya evet veya hayır cevabını veren mekanik bir prosedür varsa , karar probleminin karar verilebilir olduğu söylenir . Böyle bir algoritma yoksa, sorunun karar verilemez olduğu söylenir . Örneğin, durma sorunu kararlaştırılamaz. Algoritma veya mekanik prosedürle hesaplanabilen fonksiyon kavramını çeşitli şekillerde, örneğin Turing makinelerini kullanarak resmileştirebiliriz . Kullanılan tüm yöntemlerin yeterince genel olduklarında eşdeğer olduğu ortaya çıktı, bu da Church'ün tezi için bir argüman oluşturuyor  : mekanik bir prosedürle hesaplanabilen işlevler, aslında bu hesaplama modellerinden birine göre hesaplananlardır. Kilise'nin tezi, beklenen şekilde bir kararsızlık kanıtını yorumlamak için gereklidir.

Hiçbir mekanik işlem veya algoritma soruya cevap edebilirsek, bahsedebiliriz algoritmik karar verilemezlik gelen bu kavramı ayırt etmek, mantıksal karar verilemezlik önceki paragrafta maruz (ya da bazen de algoritmik karar verilebilirlik için Turing anlamında karar verilebilirlik gelen ve karar verilebilirlik arasında mantıksal karar verilebilirlik için Gödel duygusu).

Belki biraz açıklama gerekli: Bir sorunun karar verilemez olduğunu söylemek, sorulan sorunun bir çözümü olmadığı ve asla olmayacağı anlamına gelmez, sadece tek bir yöntemin olmadığı ve cevaplamak için iyi tanımlanmış, mekanik olarak uygulanabilir olduğu anlamına gelir. soru.

Karar verilebilir ve belirlenemeyen setler

Herhangi bir tamsayının bu kümeye ait olup olmadığı sorunu karar verilebilir, aksi takdirde karar verilemez olduğunda, doğal tam sayıların bir alt kümesinin karar verilebilir olduğu söylenir. Doğrudan tamsayı demetlerine genelleştiririz. Ayrıca bir karar verilebilir küme için yinelemeli olduğunu söylüyoruz . Karar verilebilir bir kümenin tamamlayıcısı karar verilebilir. Biz de göstermek computability teorisi bir ardışık enumerable seti olan tamamlayıcı ardışık enumerable olan özyinelemeli (yani Karar verilebilen).

Bu kavramlar "à la Gödel" kodlamaları ile resmi dillere genelleştirilmiştir . Bunları doğrudan tanımlamak da mümkündür. Mantıksal teoriler söz konusu olduğunda (kapalı, dolayısıyla tümdengelimle), daha sonra karar verilebilir bir teoriden veya karar verilemeyen bir teoriden bahsediyoruz . Bu kavramlar , önceki paragrafta görülen tam teori ve eksik teori ile karıştırılmamalıdır . Karar verilebilir veya karar verilemez bir teoriden bahsettiğimizde, bu zorunlu olarak bir algoritmik karar verilebilirlik sorunudur ve hiçbir zaman mantıksal karar verilebilirlik meselesidir . Tersine, karar verilebilir veya karar verilemez bir ifade veya önermeden bahsettiğimizde, gerekli olan mantıksal karar verilebilirliktir.

Karar verilebilir küme ve problem örnekleri

Tam sayıların tüm sonlu alt kümelerine karar verilebilir (kümenin tam sayılarının her biri için eşitliği test etmek yeterlidir). Doğal bir tamsayının eşit olup olmadığına karar vermek için bir algoritma oluşturabiliriz (ikiye böleriz, kalan sıfırsa sayı çifttir, kalan bir ise değildir), yani l bile doğal sayılar belirlenebilir; asal sayılar kümesi için de aynıdır . Çok fazla zaman (evrenin yaşından daha fazla) veya çok fazla kaynak (evrenin atom sayısından daha fazla) gerektireceğinden, pratikte karar verilmeden teorik olarak karar verilebilir. . Algoritmaların karmaşıklığı teorisinin amacı, kaynakları ve hesaplama süresini dikkate alarak karar problemlerini incelemektir.

Presburger'in aritmetiğinde , yani toplamalı ancak çarpmasız doğal tamsayılar teorisinde bir önermenin doğru olup olmadığına karar verilebilir.

Kararsız sorunlara örnekler

• Durdurma sorununun karar verilemezliği 1936'da Alan Turing tarafından gösterildi . Herhangi bir Turing makinesi ve bir giriş sözcüğü verildiğinde , hesaplamanın durup durmayacağına karar vermemize olanak tanıyan hiçbir algoritma yok. Church'ün tezi nedeniyle bu sonuç çok geneldir. Bilgisayar biliminin ortaya çıkışından bu yana, şu şekilde yorumlanabilir: Herhangi bir durumda durup durmayacağına karar vermek için, pratikte kullanılanlar gibi, yeterince güçlü bir dilin herhangi bir bilgisayar programının test edilmesine izin veren bir program yoktur. sonsuza kadar sınırlı bir zamanda veya döngüde.
• Daha genel olarak, Rice'ın teoremi , yalnızca hesaplamanın sonucuna bağlı olan bilgisayar programları üzerindeki herhangi bir sorunun (bitip bitmediği, hesaplanan değer vb.) Karar verilemez veya önemsiz olduğunu belirtir (burada, "önemsiz" şu anlama gelir: cevap program ne olursa olsun her zaman aynıdır (evet veya hayır).
• Birinci dereceden mantığın bir ifadesinin evrensel olarak geçerli olup olmadığını (herhangi bir teoride gösterilebilir) bilmek sorunu, seçilen dil imzasına (işlem veya ilişki sembolleri…) bağlıdır. Bazen karar problemi olarak adlandırılan bu problem , aritmetik dili için ve daha genel olarak en az bir ikili ilişki sembolü (<veya ∈ gibi) içeren herhangi bir birinci dereceden eşitlikçi dil için karar verilemez. Yalnızca tekli yüklem sembolleri içeren birinci dereceden eşitlikçi bir dil için (monadik eşitlikçi yüklemler hesabı), karar verilebilir.
• Standart aritmetik modelinde aritmetik dilinde belirtilen bir önermenin (her iki işlemi de alır, + ve ×) doğru olup olmadığı sorusu karar verilemez ( Gödel'in eksikliğinin ilk teoreminin veya Tarski'nin teoremi ).
• Peano'nun aritmetiğinin aksiyomlarından bir ifadenin kanıtlanabilirliği karar verilemez (bkz. Karar problemi ). Gödel, bu setin kesinlikle bir öncekine dahil olduğunu göstermiştir. Peano'nun aksiyomatiğinin sonsuz sayıda aksiyomu olduğundan, bu, daha önce belirtildiği gibi, dildeki karar sorununun karar verilemezliğinden doğrudan kaynaklanmamaktadır. İki sonuç, belirli koşulları sağlayan aritmetik teoriler için genel bir sonuçtan çıkarılabilir. Peano'nun aritmetiği bu koşulları sağlar, aynı zamanda sonlu sayıda aksiyoma sahip Robinson'un aritmetiği Q'yu da karşılar.
• Tutarlı bir küme teorisinin aksiyomlarından bir ifadenin ve daha genel olarak "yeterince" biçimsel aritmetiği ifade etmeyi mümkün kılan herhangi bir tutarlı teorinin kanıtlanabilirliği karar verilemez (bkz. Karar problemi ).
• Herhangi bir Diophantine denkleminin bir çözümü olup olmadığı sorusu . Karar verilemezliğinin kanıtı, Matiyasevich'in (1970) teoremidir .
• Lambda hesabının iki teriminin β-eşdeğeri olup olmadığı veya benzer şekilde, kombinatoryal mantığın iki teriminin özdeşliği olup olmadığı sorusu . Karar verilemezliği Alonzo Kilisesi tarafından kanıtlanmıştır .
• Mesaj yazışma sorun undecidable.

Karar verilebilir teoriler

Bir aksiyomatik teori her zaman belirli bir deyim bu teoride kanıtlanabilir olup olmadığı sorusuna evet ya da hayır cevap bir algoritma olup olmadığını Karar verilebilen olduğunu. Böyle bir algoritma, resmi bir kanıt arama algoritmasına kolayca genişletilebilir ("olağan" teoriler tarafından doğrulanan, bir aksiyom olma gerçeğinin karar verilebilir olduğu şartı altında): bir ifadenin kanıtlanabilir olduğunu bildiğimizde, numaralandırmak yeterlidir. bu ifadenin bir kanıtı bulunana kadar tüm iyi biçimlendirilmiş ispatlar. Bu arama algoritması, özellikle basit durumlar dışında, elbette yalnızca teorik ilgi alanıdır.

Bir teori karar verilebilir olsa bile , kararının algoritmik karmaşıklığı felç edici olabilir.

Karar verilebilir teorilere örnekler:

• Bir ifade ışığında, niceleyiciler veya ∃ olmadan eşdeğer bir ifade üreten niceleyicilerin ortadan kaldırılmasına dayanan algoritmalarla kapalı gerçek alanlar teorisi ; kuramın nicelik belirteçleri olmayan ifadeler önemsiz bir şekilde karar verilebilir; bilinen algoritmaların karmaşıklığı yüksektir ve yalnızca çok basit ifadelerin kararına izin verir;
• Aritmetik Presburger (durumda sınırlı çarpma ile aynı için işlenen ne miktarda çarpma olmadan aritmetik tam sayı veya bir sabittir).

Mantıksal karar verebilirlik ve algoritmik karar verebilirlik

Karar verilebilirliğin iki kavramının her biri sezgisel karar kavramını açıkça farklı anlamlarda yorumlar. Ancak birbirleriyle bağlantılıdırlar.

Aslında matematikte, bir ispatın bulunması zor olabilirse, son derece gayri resmi (ve tartışmalı - ama bu makalenin amacı bu değil) doğrulamanın "kolay" olması gerektiğini düşünüyoruz. Resmileştirdiğimizde, bunu bir cümle birliğinin resmi bir gösteri olup olmadığını anlama sorununun karar verilebilir olmasını isteyerek tercüme ederiz. Bunun doğru olması için, teorinin aksiyomları kümesinin karar verilebilir olduğu varsayılmalıdır ki bu, daha önce de belirtildiği gibi, çok doğaldır. Bu hipotez altında, bir teorinin teoremleri seti yinelemeli olarak numaralandırılabilir hale gelir  ; böyle bir teori, eğer tamamlanmışsa, o zaman karar verilebilir ( ek gerekçeler ve ayrıntılar için aksiyomatik teori makalesine bakın).

Öte yandan, karar verilebilir bir teori mutlaka tamamlanmış sayılmaz. Bu nedenle, cebirsel olarak kapalı alanlar teorisi tam değildir, çünkü karakteristik belirtilmemiştir: bu nedenle birinci dereceden ifade 1 + 1 = 0, teorinin bir sonucu değildir, çünkü 2'den farklı özelliklerle cebirsel olarak kapalı alanlar vardır ve birinci dereceden ifade 1 + 1 ≠ 0 da değildir, çünkü karakteristik 2'nin cebirsel olarak kapalı alanları vardır. Ancak cebirsel olarak kapalı alanlar teorisi karar verilebilir. Öte yandan, belirli bir özelliğin cebirsel olarak kapalı alan teorisi, tam ve karar verilebilirdir.

Gerçek ve karar verilebilirlik

Bu iki kavramı yararlı bir şekilde karşılaştırabilmek için, hakikat kavramının titiz bir tanımına sahip olmak gerekir; bu, Alfred Tarski tarafından formüle edilmiştir . (Birinci dereceden) mantıkta, belirli bir teori modelinde bir ifadenin, bu modelin nesneleri tarafından (teknik anlamda, ancak oldukça sezgisel olarak) karşılanması halinde doğru olduğunu söyleriz ; gösterilen bir ifade her modelde açıkça doğrudur ve tutarlı bir teori için bunun tersi doğrudur: Bu Gödel'in tamlık teoremidir . Durum, karar verilemeyen ifadeler için açıkça daha karmaşıktır: doğru oldukları modeller (önceki sonucun karşılığını alarak) ve yanlış oldukları modeller (bu tür modelleri sergilemek, dahası, bunu kanıtlamanın klasik yollarından biridir). kararsızlık) ve çoğu zaman bir vakayı diğerine tercih etmeye izin veren hiçbir argüman yoktur; bu örneğin geometride paralellik aksiyomu durumudur . Bununla birlikte, aritmetik ifadelerin belirli bir durumu vardır: "tüm n tamsayılar için P (n) doğrudur" şeklinde bir ifade (örneğin, "  n > 5, üç asal sayının toplamıdır"), eğer karar verilemezse, zorunlu olarak true ("naif" tamsayılar kümesinde, genellikle standart tamsayılar olarak adlandırılır ), çünkü aksi takdirde bir karşı örnek, olumsuzlamasının etkili bir gösterimini sağlayacaktır. Bu gözleme dayanarak, Stephen Cole Kleene tarafından aritmetik hiyerarşi çalışması olan tam bir hassas mantıksal teori geliştirildi .

Notlar ve referanslar

1. Öklid , The Elements , kitap I , postulat 5.
2. Bu, Vaught teoremi ile kolayca gösterilir , örneğin Chang ve Keisler 1990 , s.  139-140 veya ders notları arasında Elisabeth Bouscaren Paris-Sud.
3. Chang ve Keisler 1990 , s.  344.
4. içinde Açıklandı Chang ve Keisler 1990 , s.  43, bölüm 5'in alıştırması.
5. Rabin ve Fischer, 1974'te Presburger aritmetiği için herhangi bir karar algoritmasının , sabit bir c > 0 için yürütme süresinden daha büyük bir en kötü duruma sahip olduğunu gösterdi .22vsdeğil{\ displaystyle 2 ^ {2 ^ {cn}}}
6. Bu birinci dereceden mantıktır. Her bir asal tamsayı p için , bir alanın p karakteristiğine sahip olduğu gerçeği , birinci sırada 1 +… + 1 = 0 biçimindeki tek bir aksiyomla ifade edilir. Karakteristik 0 için sonsuz sayıda aksiyoma ihtiyacımız var (tüm olumsuzluklar öncekilerin).
7. Saptanabilirlik ile gösterilmiştir niceleyicilerin ortadan kaldırılması ile, Alfred Tarski 1948'de İlköğretim cebir ve geometri için bir karar yöntemi uyarınca, Chang ve Keisler 1990 , s.  58.

Ayrıca görün

Kaynakça

• Olivier Carton , Biçimsel diller, hesaplanabilirlik ve karmaşıklık ,2008[ baskının ayrıntıları ] ( çevrimiçi okuyun )
• Jean-Michel Autebert, Hesaplanabilirlik ve Karar Verilebilirlik , Dunod, 1992 ( ISBN  978-2225826320 )
• Pierre Wolper , Hesaplanabilirliğe Giriş , 3 e ed., Dunod, 2006 ( ISBN  978-2100499816 )
• (en) CC Chang ve H. Jerome Keisler , Model Theory , Amsterdam / New York / New York, NY, USA, Elsevier, coll.  "Mantık Üzerine Çalışmalar ve Matematiğin Temelleri",1990, 3 e  ed. ( 1 st  ed. 1973) ( ISBN  978-0-444-88054-3 , okuma çevrimiçi )

İlgili Makaleler

• Üstel fonksiyonda Tarski problemi  (in)
• ZFC'de karar verilemeyen ifadelerin listesi  (tr)
• Gödel kodlama
• Gödel'in eksiklik teoremleri

Dış bağlantı

"Hesaplamanın teorik sınırları. Verilemeyen problemler” Jean-François Raskin Samuel Fiorini ve Gilles Geeraerts tarafından verilen üç ders Döngüsü Belçika Koleji arasında Fen, Edebiyat ve Belçika Kraliyet Güzel Sanatlar Akademisi .