Prosty problem, którego rozstrzygalność nie jest znana

Przygotowuję się do wykładu skierowanego do studentów kierunków matematycznych, w ramach których rozważam omówienie koncepcji rozstrzygalności. Chcę podać przykład problemu, o którym obecnie nie wiemy, że jest rozstrzygalny lub nierozstrzygalny. Istnieje wiele takich problemów, ale jak dotąd żaden z nich nie wyróżnia się na tle innych.

Co to jest prosty do opisania problem, którego rozstrzygalność jest otwarta?

Matrix Śmiertelność problem dla macierzy 2x2. To znaczy, biorąc pod uwagę skończoną listę 2x2 macierzy całkowitych M ₁ , ..., M _k , czy M _i można pomnożyć w dowolnej kolejności (z dowolnie wieloma powtórzeniami), aby uzyskać macierz all-0?

(Przypadek 3x3 jest znany jako nierozstrzygalny. Przypadek 1x1 jest oczywiście rozstrzygalny.)

AKTUALIZACJA: Problem, o którym tu wspomniałem, jest obecnie nierozstrzygalny! http://arxiv.org/abs/1605.05274 Ponadto, artykuł został zainspirowany przeczytaniem tej samej odpowiedzi. :)

Programiści z głównych odbiorców matematyki mogą być zaskoczeni, gdy dowiedzą się, że pytanie „czy ten typ można domyślnie przekształcić na ten typ?” nie jest znany z rozstrzygania w żadnej z wersji Java 5, C # 4 i Scala 2.

Aby uzyskać więcej informacji, zobacz artykuł Andrew Kennedy'ego i Benjamina Pierce'a „O możliwości rozstrzygnięcia podtypu nominalnego z wariancją” . W artykule podano kilka przykładów dodatkowych ograniczeń dla systemów typów tych języków, zgodnie z którymi podtypowanie nominalne staje się znane lub nierozstrzygalne.

Co ciekawe, artykuł został napisany na długo przed dodaniem do C # ogólnej kowariancji i kontrowariancji, ale autorzy poprawnie przewidzieli kierunek, w którym zmierza język. (Nie jest to zaskakujące; autorzy zaprojektowali podstawowe wsparcie dla wariancji w CLR, z którego skorzystałem, dodając wariancję do C #! Zrobili ciężki lifting.)

Dziesiąty problem Hilberta dotyczący racjonalności: „Czy to równanie wielomianowe ma racjonalne rozwiązanie?”

Problem zadanej liniowej rekurencji wraz z jej wartościami początkowymi, czy przyjmuje wartość 0?

Dwa odniesienia:

http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/

http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf

Prosty problem, którego rozstrzygalność nie jest znana, jest następujący (myślę, że nadal jest otwarty):

Nieskończone szachy :

$Z \times Z$

$n$$n$

Innym prostym problemem jest zachowanie mrówki Langtona podczas skończonej konfiguracji początkowej.

Zachowanie mrówki Langtona ze skończonym wsparciem :

Kwadraty na płaszczyźnie mają różne kolory, albo czarny, albo biały. Dowolnie identyfikujemy jeden kwadrat jako „mrówkę”. Mrówka może podróżować w dowolnym z czterech głównych kierunków na każdym kroku. Mrówka porusza się zgodnie z poniższymi zasadami:

• Na białym kwadracie obróć o 90 ° w prawo, odwróć kolor kwadratu, idź o jedną jednostkę do przodu
• Na czarnym kwadracie obróć o 90 ° w lewo, odwróć kolor kwadratu, przejdź o jedną jednostkę do przodu

Wejście : skończona konfiguracja (czarno-biała) płaszczyzny i pozycja mrówki;
Pytanie : Czy mrówka zawsze kończy budowę powtarzającej się nieskończonej „autostrady”?

Dla nieskończonego wsparcia problem jest nierozstrzygalny, patrz: A. Gajardo, A. Moreira i E. Goles, Złożoność mrówki Langtona

Problem Collatz to prosty do opisania problem, którego rozstrzygalność jest otwarta. Polega na prostym powtarzaniu elementarnych operacji arytmetycznych.

$f(n)=\mathsf{\{}$ $n/2$$3n+1$

$n_0$

Co ciekawe, uogólnienie problemu Collatz okazało się nierozstrzygalne.

Bibliografia:

1- NIEZWYKŁE PROBLEMY: SAMPLER , BJORN POONEN

2- Weisstein, Eric W. „Collatz Problem”. From MathWorld - zasoby internetowe Wolfram.

3- Problem 3X + 1: Przegląd , Jeffrey C. Lagarias

Nie wiadomo, czy można zdecydować, czy dany kształt może pokryć płaszczyznę .

Rozstrzygalność spójnego ograniczania zapytań jest otwarta od ponad dwudziestu lat. Rozwiązanie tego byłoby przełomem w teorii baz danych.

$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$

W koniunkcyjnej zapytaniami jeden używa i połączyć razem egzystencjalnie ilościowo predykatów. W terminologii SQL zapytania łączące są zapytaniami WYBIERZ Z GDZIE, używając „=” i „AND”, ale bez podkwerend lub agregacji. Jest to prawdopodobnie najpopularniejszy rodzaj zapytania do bazy danych i obejmuje większość zapytań w wyszukiwarkach.

$I$$Q_1$$Q_2$

$\ne$

$(N,+,\times)$$(N,+,\times)$

Wskaźniki do obszernej literatury i rygorystycznego traktowania można znaleźć w dokumencie ToDS (w druku) niektórych osób.

$Q$$R$$Q$$Q \text{ AND } R$$Q$

Problem z korespondencją postu ze stałą liczbą płytek od 3 do 6.

Chociaż nie jest to łatwe do opisania, ma bardzo „zabawny” opis i uważam, że nadaje się do rozmów na poziomie intuicji.

Ogólny problem wysokości gwiazdy: „ile zagnieżdżenia gwiazd Kleene muszę reprezentować ten regularny język, z dopuszczalnym wyrażeniem regularnym z dopełnianiem?”

Nie wiemy nawet, czy algorytm, który zawsze zwraca 1 (z wyjątkiem 0 dla języków bez gwiazdek, co jest rozstrzygającym przypadkiem) jest poprawny.

Problem z teorii automatów.

$D$

$x$$D$$x$$x$$L(D) \cap Primes$

Komentarze: Pierwotnie słyszałem ten problem z odpowiedzi wymiany stosu autorstwa Jeffreya Shallita. Jeśli znasz jakieś odniesienia do tego, daj mi znać. Dziękuję Ci!

Powiązane posty:

(1) Czy pozostały jakieś otwarte problemy związane z DFA?

(2) https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime

Powiązane prace: https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf

„Minimal Elements for the Prime Numbers” C. Brighta, R. Devillersa i J. Shallita

Iterowane mapy interwału (opis stąd ):

(bardzo związane z problemem zaproponowanym przez Magnus Find)

$F$$x$$x$$x$$F(x)$$F(F(x))$$F$$x$$F$

$F$$x$$y$$x$$y$

$F$

$F$$x$$y$$x$$F$

Odniesienie: Asarin 2011 .

wydaje się, że istnieje dość naturalny sposób / kąt, aby zbadać to pytanie, które zostało wykorzystane w co najmniej 3 artykułach, jak następuje.

$TM(k,l)$$k$$l$$k,l$$k,l$

wyniki mogą być wyświetlane na siatce, jak w niektórych z poniższych pozycji. również w regionie pośrednim wiadomo, że niektóre (nierozwiązane) maszyny są w stanie symulować hipotezę Collatza dla niektórych danych wejściowych.

dlatego wyraźnie istnieje zjawisko podobne do „punktu przejściowego” , działające tutaj, ale nie w obszarze obliczalnym, ale w nietypowym sensie pomiędzy obliczalnym a nieobliczalnym.

• Małe maszyny Turinga i uogólniona konkurencja bobrów Michel

• Złożoność małych uniwersalnych maszyn Turinga: ankieta Woods, Neary

• Na granicach rozpuszczalności i nierozpuszczalności w systemach tagów. Teoretyczne i eksperymentalne wyniki De Mol

$2^8$

również jako przykład „bliskiej szansy” lub „pytania otwartego stosunkowo niedawno rozwiązanego jako ukończone TM”, maszyna Wolfram 2,3 okazała się uniwersalna w 2007 roku za nagrodę w wysokości 25 000 $ . konkurs został ogłoszony w maju 2007 r., a zwycięzca konkursu Smith ogłosił go w październiku 2007 r .

istnieje dość naturalny sposób mapowania najbardziej otwartych problemów na pytania dotyczące (nie) rozstrzygalności. większość otwartych problemów na ogół nie jest możliwych do udowodnienia lub udowodnienia.

w sieci istnieje pewne nieformalne zamieszanie dotyczące nierozstrzygalności problemu P vs NP , który nie jest wyłącznie problemem decyzyjnym, dlatego mówienie o jego nierozstrzygalności nie jest technicznie poprawne. ale z drugiej strony wydaje się, że istnieje ścisły / naturalny związek między nierozstrzygalnością i udowodnieniem w następujący sposób.

na przykład rozważ

$L$$x$$O(n^x)$

czy ten język jest rozstrzygalny? jest to pytanie o język z otwartą rozstrzygalnością, który jest zasadniczo ściśle związany (nawet, praktycznie identyczny) z problemem P vs NP i jego nieodłączną (nie?) sprawdzalnością.

jeśli chodzi o P vs NP jako „prosty do opisania”, wymaga jedynie pojęć TM , notacji Big O , niedeterminizmu, które są dość proste (niektóre z najbardziej podstawowych pojęć TCS) i nauczane na poziomie licencjackim lub które są utalentowane licealista mógł zrozumieć.

w rzeczywistości NP vs P / Poly jest również otwarty i można go odwzorować na otwarte pytanie o rozstrzygalność w ten sam sposób, i można to stwierdzić jako dość prosty problem dotyczący wzrostu minimalnych obwodów (monotonicznych?) w celu uznania NP za kompletne problemy (np. kliki).