Czy są jakieś szczególne problemy, o których wiadomo, że są nierozstrzygalne z powodów innych niż przekątna, samodzielne odniesienie lub redukowalność?

28

Każdy nierozstrzygnięty problem, który znam, należy do jednej z następujących kategorii:

  1. Problemy nierozstrzygalne z powodu diagonalizacji (pośrednie samodzielne odniesienie). Problemy te, podobnie jak problem zatrzymania, są nierozstrzygalne, ponieważ można użyć rzekomego decydenta dla języka do zbudowania bazy TM, której zachowanie prowadzi do sprzeczności. Możesz także wrzucić do tego obozu wiele nierozstrzygniętych problemów dotyczących złożoności Kołmogorowa.

  2. Problemy nierozstrzygalne z powodu bezpośredniego odniesienia. Na przykład można wykazać, że język uniwersalny jest nierozstrzygalny z następującego powodu: gdyby był rozstrzygalny, wówczas można by użyć twierdzenia rekurencyjnego Kleene do zbudowania bazy TM, która otrzyma własne kodowanie, zapytaj, czy zaakceptuje własne dane wejściowe , to robi odwrotnie.

  3. Problemy nierozstrzygalne z powodu redukcji istniejących nierozstrzygalnych problemów. Dobrymi przykładami są tutaj problem korespondencji pocztowej (redukcja problemu zatrzymania) i entscheidungsproblem.

Kiedy uczę moich studentów teorii teorii obliczeń, wielu uczniów również to rozumie i często pyta mnie, czy są jakieś problemy, które możemy udowodnić, że są nierozstrzygalne bez ostatecznego powrotu do jakiegoś rodzaju sztuczek polegających na samookreśleniu. Potrafię niestrukturalnie udowodnić, że istnieje nieskończenie wiele nierozstrzygalnych problemów za pomocą prostego argumentu liczności odnoszącego liczbę baz TM do liczby języków, ale nie daje to konkretnego przykładu nierozstrzygalnego języka.

Czy są jakieś języki, o których wiadomo, że są nierozstrzygalne z powodów, które nie zostały wymienione powyżej? Jeśli tak, jakie są i jakie techniki zastosowano, aby wykazać ich nierozstrzygalność?

templatetypedef
źródło
@EvilJS Rozumiałem, że dowodem nierozstrzygalności była zdolność do symulacji baz TM, choć może się mylę?
templatetypedef
Można powiedzieć, że twierdzenie Rice'a może nie pasować do żadnej z tych kategorii, ale dowód twierdzenia tak jest.
Ryan
1
@EvilJS To dobra uwaga. Naprawdę, szukam tutaj, czy istnieje jakaś fundamentalnie inna technika, której możemy użyć. Byłoby na przykład miło, gdyby ktoś zidentyfikował problem jako nierozstrzygalny w przypadku, gdy nie ma on znanego związku z odniesieniem do TM lub argumentem typu Godelinga. Jeśli najlepsze, co możemy zrobić, to „ustaliliśmy to dawno temu, a potem zdaliśmy sobie sprawę, że łatwiej jest to udowodnić w inny sposób”, co w pewnym sensie byłoby odpowiedzią - powyższe trzy techniki zasadniczo uwzględniają wszystkie dowody nierozstrzygalność, o której wiemy.
templatetypedef
2
Zajęty bóbr rośnie zbyt szybko, aby mógł go obliczyć dowolny program. Konkretnie, można zdefiniować funkcję jako jeden plus największa liczba obliczona przez program długości co najwyżej . Czy to się liczy jako diagonalizacja? f(n)n
Yuval Filmus
1
@YuvalFilmus Być może jestem tu zbyt surowy, ale dla mnie to brzmi jak argument przekątny: konstruujesz funkcję, która jest zdefiniowana jako różna od wszystkich funkcji obliczanych przez TM.
templatetypedef

Odpowiedzi:

10

Tak, są takie dowody. Opierają się one na twierdzeniu o niskiej podstawie .

Zobacz tę odpowiedź na Czy są jakieś dowody na nierozstrzygalność problemu zatrzymania, który nie zależy od samoreferencji lub diagonalizacji? pytanie o cstheory po więcej.

Kaveh
źródło
Jeśli ktoś jest zainteresowany zaawansowanymi technikami teorii obliczalności, zajrzyj do książek Roberta I. Soare Rekurencyjnie policzalne zbiory i stopnie oraz teoria obliczeń i zastosowania .
Kaveh
Popraw mnie, jeśli się mylę, ale czy dowód twierdzenia o niskiej podstawie nie obejmuje zastosowania funkcji do siebie i pytania, czy nie daje wartości? Jeśli tak, to czy nie jest to tylko warstwa pośrednia na przekątnej argumentu?
templatetypedef
@templatetypedef, nie jestem ekspertem, ale o ile rozumiem nie. Patrz np. Strona 109 w książce Soare.
Kaveh
@templatetypedef, ps1: w pytaniu o to, co uważamy za diagonalizację, jest niejasna. Jeśli nie będziemy ostrożni, możemy rozszerzyć to, co uważamy za diagonalizację, za każdym razem, gdy widzimy coś, co nie było. Weźmy na przykład metody priorytetowe lub dowolną ogólną metodę konstruowania obiektów część po części, aby uniknąć równości z jakimkolwiek obiektem z danej klasy.
Kaveh
2
@David, :) I otworzyć stronę z książki chcę podzielić, kliknij na przycisk zakładowego na górze, a następnie wyjąć z wyjątkiem parametrów idi pgz linkiem.
Kaveh
0

nie jest to odpowiedź twierdząca, ale próba znalezienia czegoś w pobliżu tego, o co prosi się z kreatywnego punktu widzenia. istnieje wiele problemów w fizyce, które są „dalekie” od matematycznych / teoretycznych sformułowań nierozstrzygalności, i wydają się one coraz bardziej „odległe” i „mało przypominają” pierwotnych sformułowań dotyczących problemu zatrzymania itp .; oczywiście używają problemu zatrzymania u podstaw, ale łańcuchy rozumowania stają się coraz bardziej odległe i mają również silny „zastosowany” aspekt / naturę. niestety nie wydaje się jeszcze żadnych świetnych badań w tej dziedzinie. ostatni problem, który „zaskakująco” okazał się nierozstrzygalny w fizyce, który przyciągnął wiele uwagi:

Luka widmowa - różnica energii między stanem podstawowym a pierwszym stanem wzbudzonym układu - ma kluczowe znaczenie dla kwantowej fizyki wielu ciał. Wiele trudnych otwartych problemów, takich jak hipoteza Haldane'a, kwestia istnienia przerwanych topologicznych faz cieczy spinowych oraz hipoteza przerwy Yang-Millsa, dotyczą luk spektralnych. Te i inne problemy są szczególnymi przypadkami ogólnego problemu luki widmowej: czy biorąc pod uwagę hamiltonian kwantowego układu wielu ciał, czy jest on szczelny czy bez przerwy? Tutaj dowodzimy, że jest to nierozstrzygalny problem. W szczególności konstruujemy rodziny układów spinów kwantowych na dwuwymiarowej sieci z niezmiennymi translacyjnie oddziaływaniami najbliższego sąsiada, dla których problem luki widmowej jest nierozstrzygalny. Wynik ten rozciąga się na nierozstrzygalność innych właściwości niskoenergetycznych,

w pytaniu wydaje się, że wszystkie (nieformalne) dowody nierozstrzygalności mają pewną „samoreferencyjną” strukturę, co zostało formalnie udowodnione w jeszcze bardziej zaawansowanej matematyce, tak że zarówno problem zatrzymania Turinga, jak i twierdzenie Godelsa mogą być postrzegane jako przykłady tego samego podstawowego zjawiska. patrz np .:

Twierdzenie o zatrzymaniu, twierdzenie Cantora (nieizomorfizm zbioru i jego zestawu sił) oraz twierdzenie o niekompletności Goedela to wszystkie przypadki twierdzenia Lawpowa o stałym punkcie, który mówi, że dla dowolnej zamkniętej kartezjańskiej kategorii, jeśli istnieje mapa epimorficzna e: A → (A⇒B), a następnie każdy f: B → B ma ustalony punkt.

w książkach Hofstadtera pojawia się także długa medytacja na ten temat (wewnętrznej?) wzajemnej więzi autoreferencyjności i nierozstrzygalności. innym obszarem, w którym wyniki nierozstrzygalności są powszechne i początkowo były nieco „zaskakujące”, są zjawiska fraktalne. przekrojowy wygląd / znaczenie nierozstrzygalnych zjawisk w naturze jest w tym momencie prawie uznaną zasadą fizyczną, po raz pierwszy zaobserwowaną przez Wolframa jako „zasada równoważności obliczeniowej” .

vzn
źródło
inne „zaskakujące / stosowane” obszary nierozstrzygalności: aperiodyczne przechyłki , ostateczna stabilizacja w grze
Conway
3
Rozumiem, że dowody na to, że wszystkie te problemy są nierozstrzygalne, sprowadzają się do redukcji z problemu zatrzymania. Czy to nieprawda?
templatetypedef
odpowiedź zasadniczo przyznaje, że (wszystkie znane wyniki nierozstrzygalności można sprowadzić do problemu zatrzymania). twoje pytanie jest prawie sformułowane jako przypuszczenie i nie jestem świadomy żadnej sprzecznej wiedzy, i widzę wiele poszlak na jego poparcie. ale najbliższym znanym formalnym dowodem są najwyraźniej stałe sformułowania nierozstrzygalności (wydaje się, że nie istnieją inne formalne sformułowania „autoreferencji”). Innym sposobem powiedzenia tego wszystkiego jest to, że kompletność Turinga i nierozstrzygalność to dwa poglądy zasadniczo tego samego zjawiska.
vzn