Lista problemów nierozstrzygalnych

W teorii obliczalności problem nierozstrzygalny jest rodzajem problemu obliczeniowego , który wymaga odpowiedzi tak/nie, ale nie może istnieć żaden program komputerowy, który zawsze daje poprawną odpowiedź; to znaczy, każdy możliwy program czasami dawałby złą odpowiedź lub działał w nieskończoność bez udzielania żadnej odpowiedzi. Bardziej formalnie, problem nierozstrzygalny to problem, którego język nie jest zbiorem rekurencyjnym ; zobacz artykuł Rozstrzygalny język . Istnieje niezliczona ilość wiele nierozstrzygalnych problemów, więc poniższa lista jest z konieczności niekompletna. Chociaż języki nierozstrzygalne nie są językami rekurencyjnymi, mogą być podzbiorami języków rozpoznawalnych przez Turinga , tj. takie języki nierozstrzygalne mogą być rekurencyjnie przeliczalne.

Wiele, jeśli nie większość, nierozstrzygalnych problemów matematycznych można przedstawić jako zadania tekstowe : określanie, kiedy dwa odrębne ciągi symboli (kodujące pewne matematyczne pojęcie lub obiekt) reprezentują ten sam przedmiot, czy nie.

Aby zapoznać się z nierozstrzygalnością w matematyce aksjomatycznej, zobacz Lista stwierdzeń nierozstrzygalnych w ZFC .

Problemy z logiką

Entscheidungsproblem Hilberta .
Wnioskowanie typu i sprawdzanie typu dla rachunku lambda drugiego rzędu (lub równoważnego).
Ustalenie, czy zdanie pierwszego rzędu w logice grafów może być zrealizowane przez skończony graf nieskierowany.
Twierdzenie Trachtenbrota - Skończona spełnialność jest nierozstrzygalna.
klauzul Horna pierwszego rzędu .

Problemy dotyczące maszyn abstrakcyjnych

Problem zatrzymania ( określenie, czy maszyna Turinga zatrzymuje się na danym wejściu) i problem śmiertelności (określenie, czy zatrzymuje się dla każdej konfiguracji początkowej).
Ustalenie, czy maszyna Turinga jest zapracowanym mistrzem bobrów (tj. jest najdłużej działającą spośród zatrzymujących się maszyn Turinga z taką samą liczbą stanów i symboli).
Twierdzenie Rice'a stwierdza, że dla wszystkich nietrywialnych właściwości funkcji cząstkowych nie można rozstrzygnąć, czy dana maszyna oblicza funkcję cząstkową z tą właściwością.
Problem zatrzymania maszyny Minsky'ego : automat skończony bez danych wejściowych i z dwoma licznikami, które można zwiększać, zmniejszać i testować na zero.
Uniwersalność niedeterministycznego automatu przesuwającego w dół : określanie, czy wszystkie słowa są akceptowane.
Problem, czy system tagów zatrzymuje się.

Problemy dotyczące macierzy

Problem macierzy śmiertelnej : określenie, przy danym skończonym zbiorze macierzy n × n z wpisami liczb całkowitych, czy można je pomnożyć w jakiejś kolejności, być może z powtórzeniami, w celu uzyskania macierzy zerowej . Wiadomo, że jest to nierozstrzygalne dla zestawu sześciu lub więcej macierzy 3 × 3 lub zestawu dwóch macierzy 15 × 15.
Ustalenie, czy skończony zestaw górnych trójkątnych macierzy 3 × 3 z nieujemnymi liczbami całkowitymi generuje swobodną półgrupę .
Ustalenie, czy dwie skończenie wygenerowane podgrupy macierzy liczb całkowitych mają wspólny element.

Problemy kombinatorycznej teorii grup

Zadanie tekstowe dla grup .
Problem konkubinatu .
Problem izomorfizmu grupowego .

Problemy w topologii

Ustalenie, czy dwa skończone kompleksy uproszczone są homeomorficzne .
Ustalenie, czy skończony kompleks uproszczony jest (homeomorficzny) rozmaitością .
Ustalenie, czy podstawowa grupa skończonego kompleksu uproszczonego jest trywialna.
Ustalenie, czy dwie rozmaitości 5 nie połączone po prostu są homeomorficzne, czy też 5-rozmaitość jest homeomorficzna z S ⁵ .

Problemy w analizie

W przypadku funkcji w niektórych klasach problem określenia: czy dwie funkcje są równe, znany jako problem zerowej równoważności (patrz twierdzenie Richardsona ); zera funkcji; czy całka nieoznaczona funkcji jest również w klasie. Oczywiście niektóre podklasy tych problemów są rozstrzygalne. Na przykład, istnieje efektywna procedura decyzyjna dla elementarnego całkowania dowolnej funkcji, która należy do dziedziny transcendentalnych funkcji elementarnych, algorytm Rischa .
„Problem z podjęciem decyzji, czy całka wielokrotna konturu oznaczonego elementarnej funkcji meromorficznej wynosi zero na całej rzeczywistej rozmaitości analitycznej, na której jest analityczna”, będąca konsekwencją twierdzenia MRDP rozwiązującego dziesiąty problem Hilberta .
Wyznaczanie dziedziny rozwiązania równania różniczkowego zwyczajnego postaci

{\ Displaystyle {\ Frac {dx} {dt}} = p (t, x), ~ x (t_ {0}) = x_ {0},}

gdzie x jest wektorem w R ⁿ , p ( t , x ) jest wektorem wielomianów w t i x , a ₀₀ (t , x ) należy do Rn ⁺¹ .

Problemy dotyczące języków formalnych i gramatyk

Problem z korespondencją pocztową .
Określenie, czy gramatyka bezkontekstowa generuje wszystkie możliwe ciągi, czy też jest niejednoznaczna.
Biorąc pod uwagę dwie gramatyki bezkontekstowe, określające, czy generują one ten sam zestaw ciągów, czy też jedna generuje podzbiór ciągów generowanych przez drugą, lub czy w ogóle istnieje ciąg, który generują obie.

Inne problemy

Problem ustalenia, czy dany zestaw płytek Wanga może pokryć płaszczyznę.
Problem wyznaczania złożoności struny Kołmogorowa .
Dziesiąty problem Hilberta : problem rozstrzygnięcia, czy równanie diofantyczne (równanie wielomianowe wielomianowe) ma rozwiązanie w liczbach całkowitych.
Ustalenie, czy dany punkt początkowy o współrzędnych wymiernych jest okresowy, czy też leży w basenie przyciągania danego zbioru otwartego, na mapach iterowanych fragmentarycznie liniowo w dwóch wymiarach lub w przepływie fragmentarycznie liniowym w trzech wymiarach.
Ustalenie, czy formuła rachunku różniczkowego λ ma postać normalną.
Conway's Game of Life , czy biorąc pod uwagę początkowy wzór i inny wzór, czy ten drugi wzór może kiedykolwiek pojawić się na podstawie początkowego.
Reguła 110 – większość pytań dotyczących możliwości pojawienia się własności „X” jest nierozstrzygalna.
Problem określenia, czy układ mechaniki kwantowej ma lukę widmową .
Ustalenie, czy gracz ma zwycięską strategię w grze Magic: The Gathering .
Planowanie w częściowo obserwowalnym procesie decyzyjnym Markowa .
Problem planowania podróży lotniczej z jednego miejsca do drugiego z uwzględnieniem opłat .

Zobacz też

Notatki

Bibliografia

Brookshear, J. Glenn (1989). Teoria obliczeń: języki formalne, automaty i złożoność . Redwood City, Kalifornia: Benjamin/Cummings Publishing Company, Inc. Dodatek C zawiera niemożność algorytmów decydujących, czy gramatyka zawiera niejednoznaczności, oraz niemożność zweryfikowania poprawności programu przez algorytm jako przykład problemu zatrzymania.
Halava, Vesa (1997). „Rozstrzygalne i nierozstrzygalne problemy w teorii macierzy”. Raport techniczny TUCS. 127 . Turku Centrum Informatyki. CiteSeerX 10.1.1.31.5792 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
Moret, BME; HD Shapiro (1991). Algorytmy od P do NP, tom 1 - Projektowanie i wydajność . Redwood City, Kalifornia: Benjamin/Cummings Publishing Company, Inc. Omawia trudność rozwiązywania problemów z algorytmami o wydajności wykładniczej w rozdziale 2, „Matematyczne techniki analizy algorytmów”.
Weinberger, Szmuel (2005). Komputery, sztywność i moduły . Princeton, NJ: Princeton University Press. Omawia nierozstrzygalność problemu tekstowego dla grup i różnych problemów topologicznych.

Dalsza lektura

Poonen, Bjorn (2 kwietnia 2012), Nierozstrzygalne problemy: próbnik , arXiv : 1204.0299 , Bibcode : 2012arXiv1204.0299P

Linki zewnętrzne

Dyskusja na MathOverflow