Seznam nerozhodnutelných problémů - List of undecidable problems

v teorie vypočítatelnosti, an nerozhodnutelný problém je typ výpočetní problém to vyžaduje odpověď ano / ne, ale tam, kde nemůže být žádný počítačový program, který vždy dává správnou odpověď; to znamená, že jakýkoli možný program by někdy dal špatnou odpověď nebo by běžel věčně, aniž by dal jakoukoli odpověď. Formálně je nerozhodnutelným problémem problém, jehož jazyk není a rekurzivní množina; viz článek Rozhodnutelný jazyk. Existují nespočetně mnoho nerozhodnutelných problémů, takže níže uvedený seznam je nutně neúplný. Ačkoli nerozhodnutelné jazyky nejsou rekurzivní jazyky, mohou být podmnožiny z Turing rozpoznatelné jazyky: tj. takové nerozhodnutelné jazyky mohou být rekurzivně spočetné.

Mnoho, ne-li většinu, nerozhodnutelných problémů v matematice lze považovat za slovní úlohy: určení, kdy dva odlišné řetězce symbolů (kódující nějaký matematický koncept nebo objekt) představují stejný objekt nebo ne.

Pro nerozhodnutelnost v axiomatické matematice viz Seznam nerozhodnutelných příkazů v ZFC.

Problémy v logika

• Hilberta Entscheidungsproblem.
• Odvození typu a kontrola typu pro lambda kalkul druhého řádu (nebo ekvivalent).^[1]
• Určení, zda věta prvního řádu v logika grafů lze realizovat konečným neorientovaným grafem.^[2]
• Trakhtenbrotova věta - Konečná uspokojivost je nerozhodnutelná.
• Splnitelnost první objednávky Horn klauzule.

Problémy s abstraktní stroje

• The zastavení problému (určení, zda a Turingův stroj zastaví na daném vstupu) a problém úmrtnosti (určení, zda se zastaví pro každou počáteční konfiguraci).
• Určení, zda je Turingův stroj a zaneprázdněný bobr šampion (tj. je nejdelší mezi zastavujícími Turingovými stroji se stejným počtem stavů a ​​symbolů).
• Riceova věta uvádí, že pro všechny netriviální vlastnosti částečných funkcí je nerozhodnutelné, zda daný stroj vypočítá částečnou funkci s touto vlastností.
• Problém zastavení pro Minský stroj: automat v konečném stavu bez vstupů a dvou čítačů, které lze zvyšovat, snižovat a testovat na nulu.
• Univerzálnost nedeterministické Pushdown automat: určení, zda jsou přijata všechna slova.

Problémy s matice

• The problém smrtelné matice: určující, vzhledem k konečné sadě n × n matice s celočíselnými položkami, ať už je lze vynásobit v určitém pořadí, případně opakováním, za vzniku nulová matice. Je známo, že je nerozhodnutelné pro sadu šesti nebo více matic 3 × 3 nebo sadu dvou matic 15 × 15.^[3]
• Určení, zda konečná sada horních trojúhelníkových matic 3 × 3 s nezápornými celočíselnými zápisy generuje volnou poloskupina.
• Určení, zda dvě definitivně generované podskupiny z M_n(Z) mají společný prvek.

Problémy v teorie kombinatorických grup

• The slovní úloha pro skupiny.
• The problém konjugace.
• The problém skupinového izomorfismu.

Problémy v topologie

• Určení, zda dva konečné zjednodušené komplexy jsou homeomorfní.
• Určení, zda konečný zjednodušený komplex je (homeomorfní) a potrubí.
• Určení, zda základní skupina konečného zjednodušeného komplexu je triviální.

Problémy v analýze

• U funkcí v určitých třídách je problém určení: zda jsou dvě funkce stejné, známý jako problém nulové ekvivalence (viz Richardsonova věta );^[4] nuly funkce; zda je ve třídě také neurčitý integrál funkce.^[5] Samozřejmě jsou rozhodující některé podtřídy těchto problémů. Existuje například účinný rozhodovací postup pro elementární integraci jakékoli funkce, která patří do pole transcendentálních elementárních funkcí, Rischův algoritmus.)
• „Problém rozhodování o tom, zda konečný mnohonásobný integrál elementární meromorfní funkce je nulový v celém reálném analytickém potrubí, na kterém je analytická,“ důsledek Věta o MRDP řešení Hilbertův desátý problém.^[5]
• Určení domény řešení řešení obyčejná diferenciální rovnice formuláře
  

${ displaystyle { frac {dx} {dt}} = p (t, x), ~ x (t_ {0}) = x_ {0},}$

kde X je vektor v Rⁿ, p(t, X) je vektor polynomy v t a X, a (t₀, X₀) patří R^{n + 1}.^[6]

Další problémy

• The Problém s korespondencí.
• Problém určení, zda daná sada Wang dlaždice může vykládat letadlo.
• Problém, zda a systém značek zastaví.
• Problém stanovení Kolmogorovova složitost řetězce.
• Hilbertův desátý problém: problém rozhodování, zda má diofantická rovnice (polynomiální rovnice s více proměnnými) řešení v celých číslech.
• Určení, zda a bezkontextová gramatika generuje všechny možné řetězce, nebo pokud je nejednoznačné.
• Vzhledem ke dvěma bezkontextovým gramatikám lze určit, zda generují stejnou sadu řetězců, nebo zda jedna generuje podmnožinu řetězců generovaných druhou, nebo zda vůbec existuje nějaký řetězec, který oba generují.
• Určení, zda je daný počáteční bod s racionálními souřadnicemi periodický, nebo zda leží v povodí přitažlivosti dané otevřené množiny, v po částech lineární iterované mapě ve dvou rozměrech nebo v po částech lineárním toku ve třech rozměrech.^[7]
• Určení, zda a λ-kalkul vzorec má normální formu.
• Conwayova hra o život na tom, zda dostal počáteční vzor a jiný vzor, ​​může se ten druhý vzor někdy objevit z původního.
• Pravidlo 110 - většina otázek týkajících se vlastnosti „X“, která se objeví později, je nerozhodná.
• Problém určení, zda má kvantově mechanický systém a spektrální mezera.^[8]
• Určení, zda má hráč vítěznou strategii ve hře o Magic: The Gathering.^[9]
• Plánování v Částečně pozorovatelný Markovův rozhodovací proces.
• Plánování cesty.

Viz také

• Seznamy problémů
• Seznam nevyřešených problémů
• Redukce (složitost)

Poznámky

Bibliografie

• Brookshear, J. Glenn (1989). Teorie výpočtu: formální jazyky, automaty a složitost. Redwood City, Kalifornie: Benjamin / Cummings Publishing Company, Inc. Příloha C obsahuje nemožnost algoritmů rozhodujících o tom, zda gramatika obsahuje nejednoznačnosti, a nemožnost ověřit správnost programu pomocí algoritmu jako příklad problému zastavení.
• Halava, Vesa (1997). "Rozhodnutelné a nerozhodnutelné problémy v teorii matic". Technická zpráva TUCS. 127. Turku Center for Computer Science. CiteSeerX  10.1.1.31.5792. Citovat deník vyžaduje | deník = (Pomoc)
• Moret, B. M. E .; H. D. Shapiro (1991). Algoritmy od P po NP, díl 1 - Návrh a účinnost. Redwood City, Kalifornie: Benjamin / Cummings Publishing Company, Inc. Diskutuje o neřešitelnosti problémů s algoritmy s exponenciálním výkonem v kapitole 2 „Matematické techniky pro analýzu algoritmů“.
• Weinberger, Shmuel (2005). Počítače, tuhost a moduly. Princeton, NJ: Princeton University Press. Diskutuje o nerozhodnutelnosti slovní úlohy pro skupiny a různých problémů v topologii.

Další čtení

• Poonen, Bjorn (2. dubna 2012), Nerozhodnutelné problémy: vzorkovač, arXiv:1204.0299, Bibcode:2012arXiv1204.0299P

externí odkazy

• Diskuse na MathOverflow