Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS)

14

Odpowiedź: nieznana.

Zadawane pytania są naturalne, otwarte i pozornie trudne; pytanie jest teraz wiki społeczności.

Przegląd

Pytanie ma na celu podzielenie języków należących do klasy złożoności  - wraz z maszynami decyzyjnymi Turinga (TM), które akceptują te języki - na dwie uzupełniające się podklasy:P

  • języki gnostyczne i bazy TM (które można zweryfikować / zrozumieć), w przeciwieństwie do
  • kryptyczne języki i bazy TM (których nie można zweryfikować / zrozumieć).

Definicje: liczby gnostyczne a liczby tajemnicze , bazy TM i języki

W ramach aksjomatów PA i ZFC wyróżniamy gnostyczne od tajemniczych maszyn i języków Turinga w następujący sposób:

D0   Mówimy, że obliczalna liczba rzeczywista   jest gnostyczna , jeżeli jest powiązana z niepustym zestawem baz TM, przy czym każda baza TM jest określona w PA jako jawna lista liczb zawierająca prawidłowy kod na uniwersalnej bazie TM, tak że dla dowolnej dokładności ϵ > 0 dostarczone jako wejście, każda TM możliwa do udowodnienia (w ZFC) zatrzymuje się z liczbą wyjściową o, która w sposób możliwy do udowodnienia (w ZFC) spełnia r - ϵ < o <rϵ>0o .rϵ<o<r+ϵ

Uwaga   Wiadomo, że niektóre obliczalne liczby rzeczywiste nie są gnostyczne (konkretny przykład patrz Raphaela Reitziga na pytanie jkffa „ Czy istnieją dowody istnienia niekonstruktywnego algorytmu? ”). Aby uniknąć zmagania się z tymi liczbami obliczalnymi, ale niezręcznymi, nakłada się ograniczenie, aby wykładniki środowiska wykonawczego były obliczalne przez TM, które są jawnie wyliczone w PA (w przeciwieństwie do TM domyślnie określonych w ZFC). Dalsza dyskusja znajduje się w rozdziale Uwagi wstępne (poniżej).

Teraz szukamy definicji, które wychwytują intuicję klasy złożoności P zawiera podzbiór języków tajemniczych , do których nie można przypisać żadnego (gnostycznego) wykładnika czasu wykonywania dolnej granicy.

Patrząc w przyszłość, ostateczna definicja ( D5 ) określa ideę kanonicznie tajemniczej decyzji TM , której definicja jest tworzona w celu uniknięcia redukcji, które (trywialnie) maskują tajemnicze obliczenia poprzez nałożenie obliczeniowych zbędnych obliczeń epi. Uzasadnienie i źródła tej kluczowej definicji omówiono później - pod nagłówkiem Rozważania końcowe  - i z wdzięcznością przyjmuje się komentarze Timothy Chowa, Petera Shora, Sasho Nikolova i Lucy Trevisana.

D1   Biorąc pod uwagę maszynę Turinga M, która zatrzymuje się dla wszystkich ciągów wejściowych, M jest nazywana tajemniczą iff, następujące stwierdzenie nie jest ani możliwe do udowodnienia, ani obalenia dla co najmniej jednej gnostycznej liczby rzeczywistej  :r0

Oświadczenie: Czas działania M wynosi w odniesieniu do długości wejściowej nO(nr)n

Maszyny Turinga, które nie są tajemnicze, mówimy, że są gnostycznymi TM.

D2   Mówimy, że decyzja maszyny Turinga M jest wydajna, jeśli ma gnostyczny wykładnik czasu wykonania  taki że język L, który akceptuje M, nie jest akceptowany przez żadną inną TM, która ma wykładnik czasu wykonania gnostyka mniejszy niż  r .rr

D3   Mówimy, że język L jest tajemniczy, jeśli jest akceptowany przez (a)  co najmniej jedną maszynę Turinga M, która jest zarówno wydajna, jak i tajemnicza, a ponadto (b)  żadna TM, która jest zarówno wydajna, jak i gnostyczna, akceptuje L.

Wyrazić D3 w inny sposób, język jest tajemniczy w bazach TM, które najskuteczniej akceptują ten język, same są tajemnicze.

Mówimy, że języki, które nie są tajemnicze językami gnostycznymi .

D4   Mówimy, że tajemnicza TM jest silnie tajemnicza, jeśli język, który akceptuje, jest tajemniczy.

D5   Mówimy, że silnie tajemnicza jest TM kanonicznie tajemnicza, jeśli jest wydajna.

Wyrazić D5 w inny sposób, każdy tajemniczy język jest akceptowany przez zestaw kanonicznie tajemniczych TM decyzji, które są najbardziej wydajnymi TM decyzjami, które akceptują ten język.

Zadawane pytania

Następująca hipoteza C0 jest naturalna i (najwyraźniej) otwarta:

C0   Klasa złożoności P zawiera co najmniej jeden tajemniczy język.

Trzy pytania są zadawane, Q1 - Q3 , z których pierwszy jest:

P1   Czy hipoteza C0 jest niezależna od PA lub ZFC?

Przy założeniu, że C0 jest prawdziwe - albo w ZFC, albo jako niezależny aksjomat uzupełniający ZFC - dwa kolejne pytania są naturalne:

Q2   Czy może być co najmniej jeden tajemniczy język w P może być konkretnie przedstawiony, to znaczy przedstawiony jako słownik wyraźnych słów w skończonym alfabecie, który zawiera wszystkie słowa o dowolnej określonej długości? Jeśli tak, pokaż taki słownik.

P3   Czy można przedstawić konkretnie co najmniej jedną kanonicznie tajemniczą decyzję TM, czyli jako opis umożliwiający zbudowanie fizycznej maszyny Turinga, która decyduje (w czasie wielomianowym) wszystkie słowa ze słownika Q2 ? Jeśli tak, zbuduj taką maszynę Turinga i obliczając ją, pokaż tajemniczy słownik języka z Q2 .

Uwagi dotyczące definicji

Definicja D0 oznacza, że ​​każda gnostyczna liczba rzeczywista jest obliczalna, ale wiadomo, że niektóre obliczalne liczby rzeczywiste nie są gnostyczne. Przykłady można znaleźć w odpowiedziach na MathOverflow autorstwa Michaëla Cadilhaca i Ryana Williamsa oraz na TCS StackExchange autorstwa Raphaela Reitziga . Mówiąc bardziej ogólnie, definicje D0 – D5 są tworzone w taki sposób, aby wykluczały odniesienia do wykładników wykonawczych innych niż gnostyczne.

Jak omówiono w wiki TCS „ Czy P zawiera niezrozumiałe języki? ”, Definicje D0 – D5 zapewniają, że każdy kryptyczny język jest akceptowany przez co najmniej jedną TM, która jest kanonicznie kryptyczna. (Zauważ też, że w obecnym pytaniu słowo „tajemnicze” zastępuje mniej opisowe słowo „niezrozumiałe” użyte w wiki).

Ponadto - w świetle D3 (a) i D3 (b)  - nie istnieje żadne obliczeniowo trywialne zredukowanie kanonicznie kryptycznej TM do gnostycznej TM, która w sposób możliwy rozpoznaje ten sam język. W szczególności D3 (a) i D3 (b) utrudniają strategie redukcji polilimiterów przedstawione w komentarzach Petera Shora i Sasho Nikolova oraz niezależnie przez Lucę Trevisana , a także utrudniają strategię redukcji wielomianu Timothy Chowa , wszystkie z których podobnie maskują tajemnicze obliczenia poprzez nałożenie obliczeniowego zbędnego epi-obliczenia .

Zasadniczo definicje „gnostyczny” i „tajemniczy” są celowo dostrojone, aby były solidne w odniesieniu do matematycznie trywialnych redukcji (i jest całkiem możliwe, że dalsze dostosowanie tych definicji może być pożądane).

Względy metodologiczne

Przegląd Lance'a Fortnowa „ Status problemu P w porównaniu z NP ” bada metody ustalania niezależności (lub innych) przypuszczeń w teorii złożoności; szczególnie pożądane są sugestie, w jaki sposób metody, które Lance recenzuje, mogą pomóc (lub nie) w odpowiedzi na pytanie 1 .

Oczywiste jest, że wiele dalszych pytań jest naturalnych. Np. Hipoteza Hartmanisa-Stearnsa inspiruje nas do pytania: „Czy istnieją tajemnicze maszyny Turing w czasie rzeczywistym? Czy ich istnienie (lub nie) jest niezależne od PA lub ZFC?”

Uwagi dotyczące typu Zeilbergera

W przypadku, gdy odpowiedź na pytanie 1 brzmi „tak”, wówczas wyrocznie decydujące o członkostwie w istnieją poza PA lub ZFC, a zatem nie wiadomo (obecnie), że istotnym elementem współczesnej teorii złożoności jest system formalny logika. P

Pod tym względem teoria złożoności różni się od większości dyscyplin matematycznych, tak że obawy wyrażone przez Dorona Zeilbergera w jego niedawnej „ Opinii 125: Teraz, gdy Alan Turing skończył 100 lat, nadszedł czas, aby rzucić nowe spojrzenie na jego wkład w sprawy seminarium , które przyniosły wiele dobrych, ale także wielu szkód ”, są prawdopodobnie uzasadnione.

Obawy Zeilbergera przybierają wyraźną formę jako kryterium Z0    (! Q1  ) i& (! C0  ), co jest równoważne z następującym kryterium:

Z0:   Kryterium wrażliwości Zeilbergera   Definicje klasy złożoności P   nazywane są wrażliwymi na Zeilbergera we wszystkich językach w P można udowodnić, że są gnostyczne.

Obecnie nie wiadomo, czy definicja złożoności P   według Stephena Cooka jest rozsądna ze względu na Zeilbergera.

Uwagi motywacyjne

Definicje „gnostyczny” i „tajemniczy” są tworzone z myślą o (ostatecznie) decydujących przypuszczeniach, takich jak:

C1   Niech iP będą ograniczeniami gnostycznymi P i N P odpowiednio. Zatem P N P jest albo możliwe do udowodnienia, albo można je obrócić w PA lub ZFC.NPPNPPNP

C2   (jak wyraźnie udowodniono w PA lub ZFC)PNP

Oczywiście C2   C1 , i odwrotnie, można sobie wyobrazić, że dowód (meta) twierdzenia C1 może dostarczyć wskazówek w kierunku dowodu (silniejszego) twierdzenia C2 . 

Ogólna motywacja to oczekiwanie / intuicja / nadzieja, że ​​w przypadku dobrze dostrojonego rozróżnienia między gnostycznymi a tajemniczymi TM i językami dowód C1, a nawet C2 może oświetlić - a nawet mieć porównywalne praktyczne implikacje - - przypuszczalnie o wiele trudniejszy i głębszy dowód, że . PNP

Juris Hartmanis był jednym z pierwszych teoretyków złożoności, którzy poważnie kontynuowali tę linię dochodzenia; patrz na przykład monografia Hartmanisa Wykonalne obliczenia i możliwe do udowodnienia właściwości złożoności (1978).

Uwagi nomenklaturowe

Z Oxford English Dictionary (OED) mamy:

  • gnostic (przym)  W odniesieniu do wiedzy; poznawczy; intelektualista   „Oni [liczby] istnieją w sposób witalny, gnostyczny i spekulacyjny, ale nie w sposób operacyjny”.

  • cryptic (przym)  Nie od razu zrozumiałe; tajemniczy, zagadkowy   „Zamiast prostych zasad przydatnych ludzkości, oni [filozofowie] narzucają krucyfiks i mroczne zdania”.

Najwyraźniej żaden Przegląd Matematyczny nie używał wcześniej słowa „gnostyk” w jakimkolwiek sensie. Zwraca się jednak uwagę na najnowszy artykuł Marcusa Krachta „ Gnosis ” ( Journal of Philosophical Logic , MR2802332), który wykorzystuje sens OED.

Najwyraźniej żaden przegląd matematyczny nie użył słowa „tajemniczy” - w sensie technicznym - w odniesieniu do teorii złożoności. Należy jednak zwrócić uwagę na artykuł Charlesa H. Bennetta „ Głębokość logiczna i złożoność fizyczna ” (w Universal Turing Machine: A Half-Century Survey , 1988), który zawiera fragment

Innym rodzajem złożoności związanym z przedmiotem byłaby trudność, biorąc pod uwagę przedmiot, znalezienia prawdopodobnej hipotezy, aby to wyjaśnić. Obiekty o takiej złożoności można nazwać „tajemniczymi” : znalezienie wiarygodnego źródła dla obiektu jest jak rozwiązanie kryptogramu.

Względy natury, otwartości i trudności

Naturalność tych pytań ilustruje tezę monografii Jurisa Hartmanisa pt. Feasible Computations and Provable Complexity Properties (1978), która:

„Wyniki dotyczące złożoności algorytmów zmieniają się dość radykalnie, jeśli weźmiemy pod uwagę tylko właściwości obliczeń, które można formalnie udowodnić.”

Otwartość i trudność tych pytań jest zasadniczo zgodna z wnioskiem przeglądu Lance'a Fortnowa „ Status problemu P kontra NP ” (2009), który:

„Nikt z nas tak naprawdę nie rozumie problemu P kontra NP, dopiero zaczęliśmy obierać warstwy wokół tego coraz bardziej złożonego pytania”.

Wskazówki dotyczące Wiki

Szczególnie poszukiwane są korekty definicyjne i strategie dowodowe odnoszące się konkretnie do pytań Q1 – Q3 i szeroko wyjaśniające przypuszczenia typu Hartmanisa C1 – C2 .

John Sidles
źródło
Nie jestem pewien, co masz na myśli w trzecim kwartale; wygląda na to, że reprezentacja danych wejściowych miałaby duży wpływ na dokładnie to, co działają bazy TM.
2
Co to jest dodatnia liczba rzeczywista półfinałowa? Rozumiem „pozytywny półfinał” dla prawdziwych macierzy symetrycznych, ale co to oznacza dla liczb !?
David Monniaux
Oznacza zero lub więcej (liczbę widzianą jako macierz 1x1).
John Sidles,
1
interesująca linia dochodzeń. od dawna myślałem, że blums przyspieszenie thm może mieć jakiś związek z takimi pytaniami i / lub P =? NP, ale nigdy nie widziałem, że przybity lub zbadany gdziekolwiek. w szczególności nie widziałem bardzo ścisłego / rygorystycznego dowodu, że nie ma języka w P, który również należałby do klasy identyfikowanej przez blum, tak że program „nie ma najszybszego algorytmu”
vzn
1
@JohnSidles Nie sądzę, że istnieje jakiś język gnostyczny w obrębie P, nawet jeśli NP jest zawarty w P. Być może możemy je rozdzielić jako te, które możemy rozwiązać, szukając, a inne metodą inną niż wyszukiwanie.
Tayfun Zapłać

Odpowiedzi:

26

Myślę, że istnieje zasadnicza podstawowa trudność z pytaniem, które tu zadajesz (i że zadałeś to pytanie w związku z niezrozumiałymi językami).

Z grubsza mówiąc, wydaje się, że szukasz języka L takiego

ale ZFC nie wie, że L PLPLP .

Aby zrozumieć trudności z Twojego pytania, myślę, że trzeba najpierw zrozumieć, że istnieje zasadnicza różnica pomiędzy intensjonalnych i ekstensjonalnych definicji języka . Extensionally, L jest określana przez co słowa są czy nie są członkami L . Oznacza to, że dwa języki L i L są zasadniczo równe wtedy i tylko wtedy, gdy zawierają dokładnie takie same słowa jak członkowie. W przeciwieństwie do tego, intensional definicja L opisuje pewne warunki dla słowo aby być w L . Maszyna Turinga, która akceptuje lub formuła pierwszego rzęduLLLLLLLL która obowiązuje wtedy i tylko wtedy, gdy x L , może być uważana za intensywną definicję Lϕ(x)xLL .

Chodzi o to, że każdy który jest (przedłużająco) w P, przyjmuje niezwykle prosty opis, ponieważ P jest tak zwaną „złożoną” klasą złożoności. Mianowicie, wystarczy wziąć wielomianowo taktowaną maszynę Turinga, która kończy się dokładnie w pożądanym czasie. Każdy „rozsądny” system do wykonywania matematyki, taki jak PA lub ZFC, będzie w stanie udowodnić, że L P, jeśli użyjesz tego prostego opisu LLPPLPL .

Więc jeśli chcesz pomylić ZFC, będziesz musiał wymyślić (intensywny) opis który jest „zbyt skomplikowany”, aby ZFC mógł uznać go za równoważny z prostym opisem LLL . Jest to możliwe, ale w pewnym sensie zbyt łatwo jest być interesującym. Wszystko, co musisz zrobić, to wziąć coś, o czym wiemy, że ZFC nie rozumie (np. Własną spójność) i jakoś pomieszać go z definicją Na przykład, oto opis zestawu liczb całkowitych:L

x jest parzyste, a nie koduje dowodu, że ZFC jest niespójny.x

Zakładając, że ZFC jest spójny, powyższa formuła określa zestaw parzystych liczb całkowitych, ale ZFC tego nie zna. Przy odrobinie majsterkowania możemy łatwo uzyskać opis zestawu liczb całkowitych, których ZFC nie będzie w stanie udowodnić, że jest w P .

Rezultat jest taki, że jeśli masz nadzieję, że powodem, dla którego trudno jest udowodnić, że jest to, że istnieją języki w P, które są „zbyt skomplikowane”, abyśmy mogli o tym myśleć, to myślę, że źle szczekasz drzewo. Podsumowując, każdy język w P jest w P z trywialnych powodów. Możesz mętnieć wody, bawiąc się niemożliwie nieprzejrzystymi opisami języków w P , ale jest to ogólna sztuczka, która nie ma nic wspólnego z P , więc nie sądzę, że daje wiele wglądu.PNPPPPPP

Timothy Chow
źródło
Timothy, dziękuję za ten wspaniały esej. Czy doceniam jednak poprawnie, że standardowa definicja złożoności obliczeniowej P - per Arora & Barak : nowoczesne podejście i / lub wykonalne obliczenia Hartmanisa i możliwe do udowodnienia właściwości złożoności , czy też oświadczenie Millenium Prize - NIE jest rozległe ? Być może jednak niektóre problemy byłyby łatwiejsze do rozwiązania, gdyby definicja P została odpowiednio zmieniona, uzasadniając to tym, że (według Hartmanisa) „Musimy dalej badać, w jaki sposób należy zmienić nasze„ spojrzenie na świat ”złożoności algorytmów, jeśli rozważymy tylko to, co da się udowodnić właściwości algorytmów. ”
John Sidles,
2
@JohnSidles standardowa definicja P to „zestaw wszystkich języków, które mogą być określone przez niektóre programy Polytime TM”. to, jak definiowany jest język (intencjonalnie lub rozszerzająco), wcale nie wchodzi w obraz: wchodzi w obraz dopiero wtedy, gdy musimy udowodnić, że dana maszyna akceptuje określony język.
Sasho Nikolov,
1
Sasho, ciąg odpowiedzi Timothy'ego Chowa (gdy go czytam) brzmi: „Jeśli zdefiniujemy P szeroko , to decyzja o członkostwie w P jest trywialna”. Istotą twojego komentarza (jak go czytam) jest to, że zgodnie z dzisiejszą konwencją „ P jest zdefiniowane intencjonalnie ”. Połączenie tych dwóch obserwacji pozwala nam docenić uwagę Hartmanisa: „Wyniki dotyczące złożoności algorytmów zmieniają się dość radykalnie, jeśli weźmiemy pod uwagę tylko właściwości obliczeń, które można formalnie udowodnić”. I naturalnie zastanawiamy się, jak można zmienić definicję P , aby łatwiej udowodnić dobre twierdzenia.
John Sidles,
1
@John: Wprowadziłem terminy „intensywny” i „ekstensywny” dla celów ekspozycyjnych. Terminy te nie są formalnie używane w matematyce. W szczególności nie jestem pewien, czy to pomaga zastosować te przymiotniki do „standardowej definicji ” Z drugiej strony zgadzam się z tym, że badanie różnych sposobów definiowania P może być owocne. PP
Timothy Chow
Tak, definicje gnostyczne i transcendentalne są zamierzone w celu (ostatecznie) udowodnienia stwierdzeń, takich jak: Twierdzenie Niech P ' i NP' będą ograniczeniami gnostycznymi P i NP odpowiednio. Następnie P '≠ NP' . Dla odpowiednio szerokiej, ale naturalnej definicji „gnostyka”, taki dowód może być porównywalnie pouczający i mieć porównywalne praktyczne implikacje, do (przypuszczalnie o wiele trudniejszego?) Dowodu, że P ≠ NP . AFAICT, Juris Hartmanis był jednym z pierwszych teoretyków złożoności, którzy poważnie kontynuowali tę linię dochodzenia.
John Sidles
8

P1: Brak
Q2: Tak, co najmniej dwa-1-binarne


Lemat: Każda TM z obliczalnym wykładnikiem czasu wykonywania, który wynosi co najmniej 1, jest transcendentalna.

Dowód:
niech A i B będą rekurencyjnie nierozłącznymi zestawami .M0M1r0,r1,r2,r3,...M0M1rm jest niż negatywne i obliczalne i zawsze ma się [ifmA wtedy stwierdzenie D1 jest prawdziwe] i [if mB wtedy stwierdzenie D1 jest fałszywe]. r0,r1,r2,r3,...rmDlatego maszyna Turinga jest transcendentalna.


Definicja:
co najmniej dwa-1-in-binarne to zbiór liczb całkowitych nieujemnych, których
reprezentacja binarna ma co najmniej dwie 1-y. (założę się, że nigdy nie zgadłeś ^ _ ^)

Definicja:
M jest maszyną Turinga, która skanuje binarną reprezentację danych
wejściowych, akceptuje, jeśli znajdzie co najmniej dwa 1, i odrzuca inaczej.

Oczywiście M decyduje o wartości co najmniej dwa-1-in-binarne i ma wykładnik czasu działania 1, a żadna inna maszyna Turinga z mniejszym wykładnikiem czasu wykonywania również nie decyduje o co najmniej dwóch-1-sekundach binarnych.
Trywialnie111Na mocy lematu M jest skuteczny i transcendentalny.
Te średnie co najmniej dwa-1-binarne są również transcendentalne.

Dlatego TPCCC jest twierdzeniem PA (i ZFC), a
co najmniej dwa-1-in-binarne jest konkretnym językiem transcendentalnym.


źródło
Ricky, dziękuję bardzo! To zajmie kilka dni, aby kontemplować swoją pomysłową „przy-najmniej-dwa-1S-w-binarny” (ALT1siB) Język i TM, który akceptuje go ... istnieją względy naturalności że D1-5 są (mam nadzieję) dostrojony, aby zapewnić i że (miejmy nadzieję) ALT1siB szanuje. Szczególnie poszukiwane są intuicje dotyczące „Czego ALT1siB uczy nas o złożoności?” Jeśli chcielibyście przedstawić uwagi w tym zakresie, bylibyśmy wdzięczni.
John Sidles,
3
(Mam nadzieję, że zdajesz sobie z tego sprawę, ale) Jedyną rzeczą, której używam w ALT1siB jest to, że ma dokładnie liniową złożoność, więc nie uczy nas niczego o złożoności. Lemat uczy nas, że większość naturalnych maszyn Turinga jest transcendentalna.
r
Hmmm ... inaczej mówiąc, ponieważ nasza definicja transcendentalnego jest tak szeroka, że ​​(według twojego lematu) nawet TM, że my (myślimy, że) rozumiemy OK - to znaczy TM uważamy za gnostyczne - są w rzeczywistości transcendentalne, to definicja „transcendentalna” musi być (miejmy nadzieję minimalnie) ograniczona. Przykład: chcemy szanować naszą intuicyjną intuicję, że TM, które decydują o pierwotności za pomocą testu pierwotności AKS,gnostyczne, a nie transcendentalne. Twoja odpowiedź pokazuje, że potrzebne jest (miejmy nadzieję niewielkie) dostrojenie definicyjne ... ale co?
John Sidles,
1
Ricky, zastanawiam się, czy nie miałbyś nic przeciwko edycji odpowiedzi, aby podać wyraźne definicje dla m , s i t . Na obecnym etapie należy odgadnąć definicje tych liczb i nie jestem wcale pewien, czy poprawnie zgadłem. W szczególności, czy dobrze rozumiem, że zmiana „rzeczywistej” na „racjonalną” w D1 zamknąłaby lukę, na którą wskazuje Twój post (AFAICT), tak że zgodnie ze zmienionym D1 przynajmniej niektóre TM są gnostyczne?
John Sidles,
1

Definicja 1: Niech xn:=2+i=0n[1/2i if i encodes a proof that ZF is inconsistent, and 0 otherwise]. Clearly, we can build a Turing machine which, given n, will compute xn. Also the xn converge to x:=2+i=0[1/2i if i encodes a proof that ZF is inconsistent, and 0 otherwise].

So x is a gnostic real, which is equal to 2 if and only if ZF is consistent.

Definition 2: For any gnostic real x>1, let Mx be a Turing machine which takes an index n of a Turing machine N and an input s, simulates N on s for |s|x/log(|s|) steps (this function is time-constructible, because x is gnostic), and inverts the result. By the Recursion Theorem, we may choose Mx to be Mx with a fixed index of Mx as its first input. Then a standard argument (the Time Hierarchy Theorem) shows that Mx has runtime O(|s|y) precisely when yx, and that Mx is efficient for its language.

Therefore, for x as in Definition 1, Mx will run in time O(|s|2) precisely if x=2, ie if ZF is consistent; moreover this fact will itself be provable in ZF. So [if ZF is consistent], Mx is a [strongly and canonically] cryptic machine, and this fact will be provable in ZF+Con(ZF).

However, ZF+on(ZF) proves that all languages in P are gnostic, since it proves that ZF proves that every language has runtime O(|s|z) for every z. So it is undecidable in ZF whether any cryptic language exists.

To answer your second and third questions, the definition I gave above for Mx is quite concrete; I don't think a full Turing machine description would be very illuminating. I suppose I could give a pseudo-code description of the program, though.

Ben Standeven
źródło
Ben, thank you for this carefully reasoned and thoughtfully phrased answer. It will take a few days to digest it ... I hope to comment in a week or so!
John Sidles