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

92

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?

Lew Reyzin
źródło
26
Problem Collatz to prosty do opisania problem, którego rozstrzygalność jest otwarta. Uogólnienie problemu Collatz okazało się nierozstrzygalne. math.mit.edu/~poonen/papers/sampler.pdf mathworld.wolfram.com/CollatzProblem.html
Mohammad Al-Turkistany
2
Być może możesz też pokazać tę fajną „sztuczkę”: napisz mały program (możesz nazwać go „goldbach”), który iteruje przez parzyste liczby całkowite i sprawdza, czy n i = p j + p k dla niektórych liczb pierwszych p j , p k < n i i zatrzymuje się w przypadku ujemnym ... następnie powiedz „cóż, nie wiemy, czy problem zatrzymania programu jest możliwy do rozstrzygnięcia!” :-). Pokazuje silną korelację między problemami teorii liczb a problemem zatrzymania. ni5ni=pj+pkpj,pk<ni
Marzio De Biasi,
8
Wydaje się to miłe, ale koncepcja rozstrzygalności nie dotyczy tylko jednej konkretnej instancji, ponieważ w obu przypadkach odpowiedź jest tylko ustalonym tak / nie.
Lev Reyzin
6
@MarzioDeBiasi, to nie jest „silna korelacja” między problemem zatrzymania a teorią liczb. Wszelkie przypuszczenia w formie „łamliwe widżety istnieją / nie istnieją” można przekształcić w program, który zatrzymuje, jeśli istnieje łamliwy widżet, o ile rozstrzygalność jest rozstrzygalna, a widżety są rekurencyjnie wyliczalne. Istnienie takiego programu to tylko najbardziej trywialny związek między problemem zatrzymania a teorią widżetów.
David Richerby
2
@DavidRicherby: dość przekonujący :-). Próbowałem tylko wyjaśnić (zaskakujący dla mnie) fakt, że rozwiązanie problemu zatrzymania dla kilku bitów kodu odpowiada rozwiązaniu długoletniej matematyki. Powinienem więc zastąpić „silną korelację” „słabą korelacją, ale dla mnie zadziwiającą” :-) :-)
Marzio De Biasi,

Odpowiedzi:

91

Matrix Śmiertelność problem dla macierzy 2x2. To znaczy, biorąc pod uwagę skończoną listę 2x2 macierzy całkowitych M 1 , ..., 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.)

Scott Aaronson
źródło
6
epubs.siam.org/doi/abs/10.1137/1.9781611974782.12 Igor Potapov i Pavel Semukhin niedawno wykazali, że jest to rozstrzygalne.
Chao Xu,
4
@ChaoXu: Wydaje się, że ten papier dotyczy tylko macierzy niepodzielnych .
2
@RickyDemer Masz rację, mój błąd.
Chao Xu,
57

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.)

Eric Lippert
źródło
7
@vzn: Kompilator Microsoft C # można przekształcić w nieograniczoną rekurencję. Zobacz mój artykuł na ten temat: blogs.msdn.com/b/ericlippert/archive/2008/05/07/…
Eric Lippert,
3
@vzn: Istnieją sposoby, aby kompilator Java również zachowywał się źle, ale nie znam szczegółów.
Eric Lippert,
2
Język typów w @vzn Scala został ukończony przez Turinga, dlatego moduł sprawdzania typów Scali może zapętlać się. Zobacz tutaj, aby uzyskać szczegółowe informacje. To samo dotyczy Haskell . Nie jestem wystarczająco zaznajomiony z językiem C # i Javą, aby wiedzieć, czy można zapętlić ich repozytorialne sprawdzanie typów.
Martin Berger,
3
@vzn: Może to również Cię zainteresować: rozdzielczość przeciążenia w C # 3 jest co najmniej NP-HARD, ponieważ możesz zmusić kompilator do rozwiązywania dowolnych problemów SAT: blogs.msdn.com/b/ericlippert/archive/2007/03 / 28 /…
Eric Lippert,
7
@vzn: Wreszcie pytanie „czy to jest trochę akademickie?” odpowiedź oczywiście brzmi tak. Pytanie „czy bla jest znany z rozstrzygalności?” jest z natury pytaniem akademickim. Przypadki te nie występują w realistycznym kodzie linii biznesowych. Znaczenie tego pytania z punktu widzenia inżynierii jest bezpieczne ; czy wroga strona trzecia może dostarczyć kod, w którym jego analiza przed uruchomieniem może spowodować złe zachowanie? Tak dzieje się w Internecie, gdy wrogie strony trzecie wysyłają JavaScript do Twojej przeglądarki.
Eric Lippert,
47

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

Boris Bukh
źródło
1
Dzięki - czy masz link do jakiegoś miejsca, które mówi, że jest otwarte?
Lew Reyzin
1
Zobacz www-math.mit.edu/~poonen/papers/subrings.pdf (drugi akapit). Istnieje również artykuł z wystawy
Boris Bukh
pomocne byłoby również zobaczenie szkicu / opisu, dlaczego ten problem nie jest równoważny z 10 problemem Hilbertsa i ten sam dowód nie ma zastosowania.
vzn
2
vzn: Równania ponad wymierne mogą być postrzegane jako szczególny przypadek równań nad liczbami całkowitymi (przez pomnożenie w celu wyczyszczenia mianowników). Pytanie brzmi zatem, czy ten szczególny przypadek 10. problemu Hilberta jest już nierozstrzygalny. Równania diofantyczne wytworzone przez istniejące dowody nie mają wymaganej specjalnej formy.
Scott Aaronson,
1
@vzn Jednym z powodów tego, że jest subtelny, jest to, że większość (być może wszystkie) strategie dowodowe naruszyłyby hipotezę Mazura. Więcej informacji na stronie 1 pierwszego linku Borysa Bukha.
David E. Speyer,
23

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

Nieskończone szachy :

Z×Z

nn


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”?

wprowadź opis zdjęcia tutaj

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

Marzio De Biasi
źródło
20

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

f(n)={ n/23n+1

n0

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

Mohammad Al-Turkistany
źródło
13
Ściśle mówiąc, odpowiedź na twoje pytanie brzmi: „tak” lub „nie”, więc nie może być nierozstrzygalna. Z drugiej strony stwierdzenie, czy konkretna liczba jest liczbą Collatz, może być nierozstrzygalne.
Lew Reyzin
@LevReyzin Thanks. Edytowane w celu rozwiązania problemu.
Mohammad Al-Turkistany,
Cieszę się, że ta odpowiedź została już uwzględniona i sugeruję, że wszystkie inne główne problemy teorii liczb otwartych można sformułować podobnie, jak w innych komentarzach / odpowiedziach i uważam, że to podstawowe ogniwo jest bliskie kluczowemu twierdzeniu o niezbadaniu przez społeczności teoretyczne.
vzn
badanie przypuszczeń Collatza z bardziej TCS / kąta empirycznego z wieloma referencjami tutaj (np. poprzez rekursję przetwornika FSM , system znaczników itp.)
vzn
16

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

Q1Q2Q1IQ2I

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.

IQ1Q2

(N,+,×)(N,+,×)

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

QRQQ AND RQ

András Salamon
źródło
Oto powiązany artykuł .
Martin Berger,
1
@MartinBerger: Wersja ToDS zawiera wspomniany powyżej dowód twardości NP, ma pełne dowody i ma otwarty dostęp (choć pomija materiał o związkach CQ z powodu braku miejsca). dx.doi.org/10.1145/2556524
András Salamon
15

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.

Shaull
źródło
13

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.

Denis
źródło
10

Problem z teorii automatów.

D

xDxxL(D)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

Michael Wehar
źródło
7

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

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

FxxxF(x)F(F(x))FxF

Fxyxy

F

FxyxF

Odniesienie: Asarin 2011 .

Nicolas Perrin
źródło
2

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)klk,lk,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.

vzn
źródło
ps De Mol ref pdf nie był dla mnie do pobrania z arxivu w momencie pisania, zawiesza się
dniu
-10

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ż

LxO(nx)

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).

vzn
źródło
3
LxL=xΘ(nx)LL
2
twierdzenie, że liczba całkowita jest nieobliczalna, jest nonsensem. i nie sądzę, aby na zasadę wykluczonego środka miało wpływ to, czy stwierdzenie jest możliwe do udowodnienia.
Sasho Nikolov,
5
popraw odpowiedź lub przestań zostawiać komentarze. Widziałem te pytania, ale jeśli nie możesz ich użyć lub odpowiedzi na nie, aby naprawić swój własny bałagan odpowiedzi, lub, co gorsza, jeśli nie chcesz, może powinieneś trollować inną społeczność.
Sasho Nikolov,
5
do rzeczy, problem w twojej odpowiedzi jest trywialnie rozstrzygalny, niezależnie od rozwiązania lub formalnej niezależności problemu P vs NP od ZFC. ponadto tworzenie problemów, które mogą być nierozstrzygalne lub trywialnie rozstrzygalne w zależności od prawdy słynnego przypuszczenia, jest niczym więcej niż uroczym ćwiczeniem (na które do tej pory całkowicie się nie udaje), aw większości przypadków nie pokazuje nic o wewnętrznej trudności przypuszczenia .
Sasho Nikolov,