Czy istnieje wynik w teorii obliczalności, która nie jest relatywizowana?

Czytałem artykuł Andreja Bauera Pierwsze kroki w teorii obliczeń syntetycznych . Na zakończenie zauważa to

Nasza aksjatyzacja ma swoje granice: nie może udowodnić żadnych wyników w teorii obliczeń, które nie relatywizują się do obliczeń wyroczni. Jest tak, ponieważ teorię można interpretować jako wariant efektywnego toposu zbudowanego z częściowych funkcji rekurencyjnych z dostępem do wyroczni.

To sprawiło, że zastanawiałem się nad nierelatywacyjnymi wynikami obliczalności. Wszystkie wyniki, które znam z teorii obliczeń, odnoszą się do obliczeń z wyroczniami.

Czy istnieją wyniki w teorii obliczalności , które się nie relatywizują? Czyli wyniki, które dotyczą obliczalności, ale nie dotyczą obliczeń w odniesieniu do niektórych wyroczni?

Rozumiem przez to znane twierdzenie w teorii obliczalności, a nie jakieś ugotowane stwierdzenie. Jeśli pojęcie relatywizacji nie ma sensu dla wyniku, to nie jest to, czego szukam.

Interesujące jest również to, czy wynik można podać w języku teorii syntetycznych obliczeń, czy nie.

computability relativization Anonimowy
źródło

Każdy wie o nierelatywizujących wynikach teorii złożoności, takich jak IP = PSPACE. Pytam o niewyspecjalizowanych relatywizacji Obliczalność resuts teorii, nie złożoność wyników teorii.

Anonimowy

@Erfan: Twoje komentarze nie dotyczą pytania. Moje pytanie dotyczy teorii obliczalności, mówisz o teorii złożoności. Szukam wyników niereletywizujących, twierdzenie o hierarchii czasu relatywizuje się. Jeśli masz pytanie dotyczące twierdzenia o hierarchii czasu i relatywizacji, możesz opublikować osobne pytanie.

Anonimowy

Istotne rzeczy: hipoteza homogeniczności sformułowana przez H. Rogersa została odrzucona przez Richarda A. Shore'a; Hipoteza homogeniczności (1979): istnieje stopień Turinga taki, że nie jest izomorficzny do (struktura stopni Turinga z częściowym zamówienie ). Zobacz podobne pytanie na lo.logic

a

$\mathbf{a}$

D (\geq a)

$\mathcal{D}(\geq \mathbf{a})$

D

$\mathcal{D}$

\leq_{T}

$\leq_{T}$

Marzio De Biasi

Dobre pytanie :-)

Andrej Bauer,

@Marzio: Interesujące. „ Oznacza to, że istnieje zdanie pierwszego rzędu w języku zawierającym tylko co jest prawdziwe w odniesieniu do stopni Turinga, ale jest fałszywe, jeśli relatywizujesz zdanie do stopni Turinga dla niektórych (i oczywiście , praca w stopniach Turinga jest równoznaczna z udzieleniem wszystkim maszynom Turinga dostępu do jako wyroczni). Dlatego dowodu, że jest prawdziwe, nie można relatywizować do . $\varphi$ $\leq_T$ $\geq_Tx$ $x$ $\geq_Tx$ $x$ $\varphi$ $x$ "Ale nie jest tak naprawdę wynikiem teoria obliczalności, jest gotowa na twierdzenie o meta.

φ

$\varphi$

Anonimowy

Odpowiedzi:

Twierdzenie Higmana o osadzeniu: grupy generowane skończalnie przedstawione obliczeniowo są właśnie skończonymi podgrupami grup skończonych przedstawianych. Co więcej, każda grupa prezentowana obliczalnie (nawet ta generowana w sposób policzalny) jest podgrupą grupy przedstawionej na koniec.

Zauważ, że ta wypowiedź mogłaby zrelatywizować do: „The grupach -computably prezentowanych (z pewnym oracle ) są dokładnie skończenie generowane podgrupy skończenie prezentowanych grup”, ale tak nie jest, jak można udowodnić, że z jakiegoś nieobliczalnych istnieją - grupy przedstawione komputerowo, które nie są przedstawione komputerowo. $O$ $O$ $O$ $O$

Rzeczywiście, myślę, że każdy zakaz relatywizacji wynikiem teoria obliczalności musi mieć coś z tym smaku, jak jakiejś części wyniku lub jego dowód musi jakoś „nail down” prawdziwej obliczalności od obliczalności z wyrocznią . W tym przypadku to skończoność utrudnia „rzeczywistą obliczalność”. Zauważ, że jak poprosił Scott Aaronson, wynik ten jest niezmienny dla każdego ze zwykłych modeli obliczeń (maszyna Turinga, pamięć RAM itp.), Ale nie jest relatywizowany (ponownie, ponieważ wszystkie zwykłe modele obliczeń „rzeczywistych” dzielą niektóre wspólna „właściwość skończoności”). $O$

Z drugiej strony można argumentować, że to „nie ma znaczenia” w przypadku tego pytania, ponieważ bardziej przypomina definicję obliczalności opartą na grupach, niż jest to „wynik teorii obliczeń”. Z drugiej strony jest to definicja obliczalności, która jest odporna na modelowanie, ale nie jest relatywizująca . (W przeciwieństwie do, powiedzmy, charakterystyki Kleene funkcji obliczalnych, które łatwo relatywizuje, po prostu dodając charakterystyczną funkcję twojej wyroczni do generującego zestawu funkcji. Wydaje się, że nie ma analogicznej operacji dla grup w kontekście Higmana Osadzania).

Joshua Grochow
źródło

Czy to skończoność (w porównaniu z nieskończonością) wyróżnia twój przykład, czy policzalność (vs. nieobliczalność)?

András Salamon

Przepraszam za moją ignorancję, ale czy twierdzenie Higmana jest jednolite? Czyli, biorąc pod uwagę grupę obliczalną, czy możemy jednolicie obliczyć skończoną grupę, która ją zawiera?

Andrej Bauer

Ups, w moim pytaniu proszę zastąpić słowo „generowanie skończone” słowem „skończone przedstawienie” To był trywialny błąd. Zastanawiam się, czy możemy zastąpić „skończoną prezentację” czymś bardziej ogólnym.

Andrej Bauer

@AndrewMorgan: Zgadzam się z początkiem twojego sporu, ale nie zgadzam się z twoim wnioskiem. Jest to często bardzo przydatne, że jest -Complete. Nie myślę o relatywizacji Cooka-Levina jako o czymś nienaturalnym ... Bardzo podoba mi się sugestia Andreja i pomyślimy o tym ...

S A T^{O}

$SAT^O$

N P^{O}

$NP^O$

Joshua Grochow

@AndrewMorgan: uzgodniony. Myślę, że rodzaj węzła byłby dobrym kandydatem :).

Joshua Grochow

Często się nad tym zastanawiałem!

Jeśli przez „wyniki w teorii obliczalności” masz na myśli wyniki, które są niezmienne w odniesieniu do wyboru modelu maszyny (maszyny Turinga, pamięci RAM itp.), To nie znam ani jednego przykładu takiego wyniku, a ja na pewno pamiętałbym, gdybym go widział.

Najbliżej mogę zasugerować odpowiedź: Myślę, że w teorii obliczeń istnieje wiele interesujących pytań, które mogą zależeć od modelu maszyny. Na przykład: czy funkcja Busy Beaver ze swoją zwykłą definicją w odniesieniu do maszyn Turinga jest nieskończenie często dziwna? Czy wartość BB (20) jest niezależna od ZFC? Niezależnie od odpowiedzi na te pytania, z pewnością mogą się różnić w przypadku relatywizowanych analogów funkcji BB.

Scott Aaronson
źródło

Oto mniej lub bardziej trywialny przykład: Rozważ problem zatrzymania maszyn Turinga, którym wyraźnie zabroniono (z definicji modelu obliczeniowego) dostępu do wyroczni. Jest nierozstrzygalny zarówno w stosunku do wyroczni, jak i trywialnej wyroczni, a jednak jest rozstrzygalny w odniesieniu do wyroczni w przypadku problemu zatrzymania. (Sam problem nie zmienia się w stosunku do wyroczni, ponieważ nie ma dostępu do wyroczni, ale (nieograniczona) TM, która decyduje o problemie, staje się silniejsza biorąc pod uwagę wyrocznię.)

Istnieje również wiele innych przykładów. Po prostu pobaw się trochę modelem obliczeniowym i możesz znaleźć inne podobne wyniki.

Philip White
źródło

Ciekawe: co dokładnie jest nie tak z tą odpowiedzią? Być może downvoters nie wierzą, że można zabronić maszynie Turinga dostępu do wyroczni i wymagać dalszego wyjaśnienia tego?

Philip White

Wydaje się, że nie jest to bardzo uczciwa definicja relatywizacji, aby pozwolić maszynie na wyrocznię, ale nie pozwolić jej na użycie wyroczni.

David Eppstein

Ciekawe, choć nie to, czego szukam. Szukam znanego wyniku w teorii obliczalności, który nie relatywizuje, ani argumentu, jak przygotować taki wynik.

Anonimowy

Rozważ następujące stwierdzenie: H (problem z zatrzymaniem dla maszyn Turinga bez wyroczni) nie jest obliczalny. Z drugiej strony H jest obliczalny w stosunku do wyroczni z problemem zatrzymania. Nawet jeśli uważamy to za sposób relatywizacji oświadczenia, nie jest to interesujące. Prawdopodobnie istnieje podobny sposób relatywizacji dowolnego stwierdzenia, które powoduje, że jest ono fałszywe. Relatywizacja to nie tylko gdzieś przymocowanie wyroczni. Relatywizacja jest interesująca, gdy zachowuje interesującą klasę argumentów, więc jeśli instrukcja nie jest relatywizowana, wiemy, że klasa argumentów nie może udowodnić instrukcji.

Kaveh

Weź np. Metodę relatywizacji w BGS. Jest to interesujące, ponieważ zachowuje proste argumenty diagonalizacji, więc nie mogą rozstrzygnąć P vs. NP. Jeśli relatywizacja nie zachowuje takich argumentów, prawdopodobnie nie jest to interesujący sposób relatywizacji instrukcji. Dobra relatywizacja powinna wytrwać jak najwięcej znanych argumentów i udowodnionych wyników, im mniej zachowa, tym mniej będzie interesująca.

Kaveh