Kararsız sorunların listesi - List of undecidable problems

İçinde hesaplanabilirlik teorisi, bir kararsız problem bir tür hesaplama problemi evet / hayır yanıtı gerektirir, ancak her zaman doğru yanıtı veren herhangi bir bilgisayar programının bulunamayacağı durumlarda; yani, olası herhangi bir program bazen yanlış cevap verir veya hiçbir cevap vermeden sonsuza kadar çalışır. Daha resmi olarak, kararlaştırılamayan bir sorun, dili çok önemli olmayan bir sorundur. özyinelemeli küme; makaleye bakın Karar verilebilir dil. Var sayılamayacak kadar birçok kararlaştırılamayan sorun, bu nedenle aşağıdaki liste mutlaka eksiktir. Karar verilemeyen diller yinelemeli diller olmamasına rağmen, alt kümeler nın-nin Turing tanınabilir diller: yani, bu tür karar verilemeyen diller yinelemeli olarak numaralandırılabilir.

Matematikteki kararlaştırılamayan problemlerin çoğu değilse de çoğu şu şekilde ortaya çıkabilir: kelime problemleri: iki farklı sembol dizisinin (bazı matematiksel kavram veya nesnelerin kodlanması) aynı nesneyi temsil edip etmediğini belirleme.

Aksiyomatik matematikte karar verilemezlik için bkz. ZFC'de karar verilemeyen ifadelerin listesi.

İçindeki sorunlar mantık

İle ilgili sorunlar soyut makineler

  • durdurma sorunu (bir Turing makinesi belirli bir girişte durur) ve ölüm sorunu (her başlangıç ​​konfigürasyonu için durup durmayacağının belirlenmesi).
  • Bir Turing makinesinin bir meşgul kunduz şampiyonu (yani, aynı sayıda durum ve sembole sahip durdurucu Turing makineleri arasında en uzun süre çalışandır).
  • Rice teoremi kısmi fonksiyonların tüm önemsiz özellikleri için, belirli bir makinenin bu özellik ile kısmi bir fonksiyonu hesaplayıp hesaplamadığının karar verilemez olduğunu belirtir.
  • Bir için durma sorunu Minsky makinesi: girişi olmayan sonlu durumlu bir otomat ve artırılabilen, azaltılabilen ve sıfır için test edilebilen iki sayaç.
  • Nondeterministic'in Evrenselliği Aşağı açılan otomat: tüm kelimelerin kabul edilip edilmediğini belirleme.

İle ilgili sorunlar matrisler

  • ölümlü matris problemi: sonlu bir dizi verildiğinde belirleme n × n tamsayı girişli matrisler, bir sırayla, muhtemelen tekrarla çarpılıp çarpılamayacakları, sıfır matris. Bunun altı veya daha fazla 3 × 3 matris kümesi veya iki 15 × 15 matris kümesi için karar verilemez olduğu bilinmektedir.[3]
  • Negatif olmayan tamsayı girdileri olan sonlu bir üst üçgen 3 × 3 matris kümesinin bir serbest yarı grup.
  • Sonlu olarak oluşturulmuş iki alt grup olup olmadığını belirleme Mn(Z) ortak bir öğeye sahiptir.

İçindeki sorunlar kombinatoryal grup teorisi

İçindeki sorunlar topoloji

Analiz sorunları

  • Belirli sınıflardaki işlevler için, sıfır eşdeğerlik sorunu olarak bilinen iki işlevin eşit olup olmadığını belirleme sorunu (bkz. Richardson teoremi );[4] bir fonksiyonun sıfırları; bir fonksiyonun belirsiz integralinin de sınıfta olup olmadığı.[5] Elbette, bu sorunların bazı alt sınıflarına karar verilebilir. Örneğin, bir transandantal temel işlevler alanına ait olan herhangi bir işlevin temel entegrasyonu için etkili bir karar prosedürü vardır. Risch algoritması.)
  • "Bir temel meromorfik fonksiyonun belirli kontur çoklu integralinin, analitik olduğu her yerde gerçek analitik manifold üzerinde sıfır olup olmadığına karar verme problemi", MRDP teoremi çözme Hilbert'in onuncu problemi.[5]
  • Bir çözümün etki alanını belirleme adi diferansiyel denklem şeklinde
nerede x bir vektör içinde Rn, p(t, x) bir vektördür polinomlar içinde t ve x, ve (t0, x0) ait olmak Rn + 1.[6]

Diğer problemler

  • Post yazışma sorunu.
  • Belirli bir dizi olup olmadığını belirleme sorunu Wang fayans uçağı döşeyebilir.
  • Sorun, bir etiket sistemi durur.
  • Belirleme sorunu Kolmogorov karmaşıklığı bir dizenin.
  • Hilbert'in onuncu problemi: Diophantine denkleminin (çok değişkenli polinom denklemi) tamsayılarda bir çözümü olup olmadığına karar verme problemi.
  • Olup olmadığını belirleme bağlamdan bağımsız gramer tüm olası dizeleri üretir veya belirsiz ise.
  • Bağlamdan bağımsız iki gramer verildiğinde, aynı dizgi kümesini mi oluşturduklarını veya birinin diğeri tarafından oluşturulan dizelerin bir alt kümesini mi oluşturduğunu veya her ikisinin de ürettiği herhangi bir dizge olup olmadığını belirlemek.
  • Rasyonel koordinatlara sahip belirli bir başlangıç ​​noktasının periyodik olup olmadığını veya belirli bir açık kümenin çekim havzasında mı, iki boyutta parçalı doğrusal yinelenmiş bir haritada mı yoksa üç boyutlu parçalı doğrusal bir akışta mı bulunduğunu belirlemek.[7]
  • Olup olmadığının belirlenmesi λ-hesap formül normal bir forma sahiptir.
  • Conway'in Hayat Oyunu bir başlangıç ​​modeli ve başka bir model verilip verilmediğine göre, ikinci model ilk modelden itibaren görünebilir mi?
  • Kural 110 - "X" özelliği ile ilgili soruların çoğu daha sonra ortaya çıkacak karar verilemez.
  • Kuantum mekaniksel bir sistemin bir sisteme sahip olup olmadığını belirleme sorunu spektral boşluk.[8]
  • Bir oyuncunun bir oyunda kazanan bir stratejisi olup olmadığının belirlenmesi Sihir: Toplama.[9]
  • Planlama Kısmen gözlemlenebilir Markov karar süreci.
  • Seyahat planlaması.

Ayrıca bakınız

Notlar

  1. ^ Wells, J. B. (1993). "İkinci dereceden lambda-kalkülüsünde yazılabilirlik ve tür denetimi eşdeğerdir ve karar verilemez". Tech. Rep. 93-011. Bilgisayar. Sci. Dept., Boston Univ .: 176–185. CiteSeerX  10.1.1.31.3590.
  2. ^ Trahtenbrot, B.A. (1950). "Sonlu alanlar için karar problemi için bir algoritmanın imkansızlığı". Doklady Akademii Nauk SSSR (N.S.). 70: 569–572. BAY  0033784.
  3. ^ Cassaigne, Julien; Halava, Vesa; Harju, Tero; Nicolas, Francois (2014). "Matris Ölümleri için Daha Sıkı Karar Verilemezlik Sınırları, Köşedeki Sıfır Sorunları ve Daha Fazlası". arXiv:1404.0644 [cs.DM ].
  4. ^ Keith O. Geddes, Stephen R. Czapor, George Labahn, Bilgisayar Cebiri için Algoritmalar, ISBN  0585332479, 2007, s. 81ff
  5. ^ a b Stallworth, Daniel T. ve Fred W. Roush Belirli İntegrallerin Kararsız Bir Özelliği American Mathematical Society'nin Bildirileri Cilt 125, Sayı 7, Temmuz 1997, Sayfalar 2147-2148
  6. ^ Graça, Daniel S .; Buescu, Jorge; Campagnolo, Manuel L. (21 Mart 2008). "Tanım Alanının Sınırlılığı Polinom ODE'ler için Kararsızdır". Teorik Bilgisayar Bilimlerinde Elektronik Notlar. 202: 49–57. doi:10.1016 / j.entcs.2008.03.007.
  7. ^ Moore, Cristopher (1990), "Dinamik sistemlerde öngörülemezlik ve karar verilemezlik" (PDF), Fiziksel İnceleme Mektupları, 64 (20): 2354–2357, Bibcode:1990PhRvL..64.2354M, doi:10.1103 / PhysRevLett.64.2354, PMID  10041691.
  8. ^ Cubitt, Toby S .; Perez-Garcia, David; Kurt, Michael M. (2015). "Spektral boşluğun karar verilemezliği". Doğa. 528 (7581): 207–211. arXiv:1502.04135. Bibcode:2015Natur.528..207C. doi:10.1038 / nature16059. PMID  26659181.
  9. ^ Herrick, Austin; Biderman, Stella; Churchill, Alex (2019-03-24). "Magic: The Gathering is Turing Complete". arXiv:1904.09828v2. Bibcode:2019arXiv190409828C. Alıntı dergisi gerektirir | günlük = (Yardım)

Kaynakça

  • Brookshear, J. Glenn (1989). Hesaplama Teorisi: Biçimsel Diller, Otomata ve Karmaşıklık. Redwood City, Kaliforniya: Benjamin / Cummings Publishing Company, Inc. Ek C, bir dilbilgisinin belirsizlikler içerip içermediğine karar veren algoritmaların imkansızlığını ve Duraklama Problemi örneği olarak program doğruluğunu bir algoritma ile doğrulamanın imkansızlığını içerir.
  • Halava, Vesa (1997). "Matris teorisinde karar verilebilir ve belirlenemeyen problemler". TUCS teknik raporu. 127. Turku Bilgisayar Bilimleri Merkezi. CiteSeerX  10.1.1.31.5792. Alıntı dergisi gerektirir | günlük = (Yardım)
  • Moret, B. M. E .; H. D. Shapiro (1991). P'den NP'ye Algoritmalar, 1. cilt - Tasarım ve Verimlilik. Redwood City, Kaliforniya: Benjamin / Cummings Publishing Company, Inc. Bölüm 2, "Algoritmaların analizi için matematiksel teknikler" de üstel performansa sahip algoritmalarla problemlerin çözülemezliği tartışılmaktadır.
  • Weinberger, Shmuel (2005). Bilgisayarlar, sertlik ve modüller. Princeton, NJ: Princeton University Press. Gruplar için problem kelimesinin karar verilemezliğini ve topolojideki çeşitli problemleri tartışır.

daha fazla okuma

Dış bağlantılar