Algoritmikusan megoldhatatlan probléma

A kiszámíthatóság elméletében algoritmikusan megoldhatatlan probléma az a probléma, amelynek minden objektumra igen vagy nem válasza van valamilyen bemeneti adathalmazból, amelyre (elvileg) nincs olyan algoritmus , amely bármilyen objektumot kapott bemeneti adatként. , megállna és véges számú lépés után megadná a helyes választ.

Absztrakt gépekkel kapcsolatos problémák

• Állítsa le a problémát
• Az önalkalmazhatóság problémája
• Foglalt hód
• A Rice-tételben megfogalmazott bármely probléma
• Határozza meg, hogy a " Life " játékban egy adott kezdeti konfiguráció elér-e valaha egy adott végső konfigurációt [1]

Mátrixokkal kapcsolatos problémák

• Haldokló mátrix probléma : Adott egy véges n  ×  n négyzetmátrixból álló halmaz , határozza meg, hogy van-e ezen mátrixok mindegyikének vagy némelyikének olyan szorzata (esetleg ismétlődésekkel) olyan sorrendben, amely nullmátrixot eredményez. A probléma még n=3 esetén is eldönthetetlen (n=2 esetén az eldönthetőség nyitott kérdés [2] ). [3]
• Identitásmátrix probléma : Adott egy n  ×  n négyzetmátrixból álló véges halmaz , határozza meg, hogy van-e e mátrixok mindegyikének vagy némelyikének szorzata (esetleg ismétlődésekkel) olyan sorrendben, amely az azonosságmátrixot eredményezi. A probléma n=4-től induló egész mátrixok esetén eldönthetetlen [4] és n=2 esetén eldönthető [5] (n=3 esetén a eldönthetőség nyitott kérdés). A probléma megegyezik azzal a kérdéssel, hogy egy mátrix félcsoport csoport-e.
• A mátrix félcsoport szabadságának problémája n=3-tól induló egész mátrixokra algoritmikusan megoldhatatlan, n=2 esetén pedig nyitott.

Egyéb kérdések

• Engedélyezési probléma ( német  Entscheidungsproblem ).
• Egy képlet levezethetősége a Peano aritmetikában .
• Posta levelezési probléma .
• Tetszőleges karakterlánc Kolmogorov-komplexitásának kiszámítása . Ennek az állításnak a fontos gyakorlati következményei a programozás területén:
  • lehetetlen létrehozni egy ideális archiválót , amely bármilyen bemeneti fájlhoz létrehoz egy olyan programot, amely a lehető legkisebb méretű kinyomtatja ezt a fájlt
  • ideális méretoptimalizáló fordító létrehozásának lehetetlensége
• Hilbert tizedik problémája
  • különösen lehetetlen ilyen függvényt kiszámítani: f(n) = max{min{max{|x_1|, |x_2|, ..., |x_k|: P(x_1, x_2, ..., x_k ) = 0} }}, ahol k 1-től n-ig terjed, P az összes polinomra terjed ki legfeljebb n fokú k változóban, és az egyes tagok együtthatójának modulusa nem haladja meg az n-t. Ennek a függvénynek az értéke lehetővé teszi, hogy a megoldások felsorolását egy legfeljebb n fokozatú diofantini egyenletre korlátozzuk, legfeljebb n változóval, amelynek együtthatói modulusa nem haladja meg az n-t. Például f(1)=1, f(2)=5 Ha lenne egy kiszámítható függvény, amely lépést tartana f(n-nel), akkor Hilbert tizedik feladatának az ellenkezője lenne a megoldása.
• Határozza meg, hogy a sík csempézhető-e az adott Wang lapkakészlettel .
• Határozza meg, hogy a sík csempézhető-e adott poliominokészlettel .
• A másod- és magasabb rendek egységesítésének
• Típuskövetkeztetési probléma a Hindley-Milner típusú rendszerben N - rangú polimorfizmussal .

Problémák, amelyek algoritmikus megoldhatatlansága nem bizonyított

Egyes problémák esetében az azokat megoldó algoritmus ismeretlen, és természetüknél fogva hasonlóak az ismert, algoritmikusan megoldhatatlan problémákhoz. Az ilyen problémák algoritmikus megoldhatóságára vonatkozó kérdések nyitott problémák . Íme néhány ilyen feladat:

• A tizedik Hilbert-feladat analógja a 3. fokú egyenletekhez
• Hilbert tizedik feladatának analógja racionális számok egyenleteire [6]
• Haldokló mátrix feladat 2-es rendű mátrixokhoz

Lásd még

• Formális elmélet algoritmikus eldönthetősége
• Godel befejezetlenségi tétele

Jegyzetek

1. ↑ Life univerzális számítógép . Letöltve: 2010. május 13. Az eredetiből archiválva : 2014. október 31.. (határozatlan)
2. ↑ Mikor halandó egy mátrixpár? . Letöltve: 2010. május 6. Az eredetiből archiválva : 2015. december 8. (határozatlan)
3. ↑ Cassaigne, Julien; Halava, Vesa; Harju, Tero & Nicolas, Francois (2014), Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More, arΧiv : 1404.0644 [cs.DM]. 
4. ↑ Paul C. Bell; Igor Potapov. Az identitásmegfelelési probléma eldönthetetlenségéről és alkalmazásai Word és Matrix Semigroups számára  // International Journal of Foundations of Computer  Science : folyóirat. - World Scientific, 2010. - Vol. 21.6 . - P. 963-978 . - doi : 10.1142/S0129054110007660 .
5. ↑ Christian Choffrut; Juhani Karhumaki. Néhány döntési probléma egész mátrixokon. (neopr.)  //ITA. - 2005. - T. 39. (1) bekezdés . - S. 125-131 . - doi : 10.1051/ita:2005007 .
6. ↑ Uszpenszkij V. A. , Szemjonov A. L. Megoldható és megoldhatatlan algoritmikus problémák. // Kvant , 1985, 7. sz., p. 9-15