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

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ść?

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.

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:

• Nierozstrzygalność luki widmowej / Cubitt, Perez-Garcia, Wolf

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

• Problem zatrzymania, niepoliczalne zbiory: wspólny dowód matematyczny?

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