Nieporównywalne liczby naturalne

„Nazwa największej gry liczbowej” wymaga od dwóch graczy potajemnego zapisania numeru, a zwycięzcą jest osoba, która zapisała większą liczbę. Gra zazwyczaj pozwala graczom zapisywać funkcje ocenione w danym momencie, więc byłoby również do przyjęcia. $2^{2^{2^{2}}}$

Wartości funkcji Busy Beaver, , nie można ustalić (w ZFC lub w żadnym rozsądnym spójnym systemie aksjomatycznym) dla dużych wartości . W szczególności nie można ustalić zgodnie z tym artykułem . Nie oznacza to jednak, że nie możemy porównywać wartości funkcji Busy Beaver. Na przykład możemy udowodnić, że jest ściśle monotoniczny . $BB(x)$ $x$ $BB(10^4)$ $BB(x)$

Załóżmy, że zezwalamy graczom na zapisywanie wyrażeń obejmujących kompozycje funkcji elementarnych, liczb naturalnych i funkcji Busy Beaver. Czy są dwa wyrażenia, które obaj gracze mogą zapisać, abyśmy mogli udowodnić w ZFC, że ustalenie zwycięzcy w ZFC jest niemożliwe (zakładając, że ZFC jest spójny)?

EDYCJA: Pierwotnie to pytanie brzmiało „... dowolne kombinacje funkcji obliczeniowych, liczb naturalnych i funkcji Busy Beaver”.

Jeśli pozwolimy przyjąć wartość jeśli [coś bezbożnego dużego i niewyrażalnego na tej stronie] i jeśli tak nie jest, to i są nieporównywalne. $f(x)$ $3$ $BB(x) >$ $7$ $f(10^4)$ $6$

To mnie nie satysfakcjonuje, głównie dlatego, że $f$ nie jest rozsądną funkcją dla kogoś, kto mógłby skorzystać z tej gry. Nie wiem jednak, jak wyrazić swoją intuicję na ten temat, więc ograniczyłem pytanie, aby uniknąć częściowych funkcji.

computability undecidability

— Stella Biderman
źródło

Można nierozstrzygalności

być przedłużony do, powiedzmy, poszczególnych bitów? Jeśli tak, wtedy po prostu trzeba zrobić coś takiego porównania 3rd najmniej znaczącego bitu

z 8 najmniej znaczącego bitu.

B B (10^{4})

$BB(10^4)$

B B (10^{4})

$BB(10^4)$

— mhum

@mhum takie pytania są trudne, ponieważ wartość

jest w rzeczywistości zależna od kodowania. Istnieją kodowania, dla których

jest zawsze parzyste, na przykład. Rozumiem, że wszystkie pytania w tym zakresie są albo łatwe do obliczenia, albo otwarte, w zależności od kodowania.

B B (x)

$BB(x)$

B B (x)

$BB(x)$

— Stella Biderman

Zgodnie z odpowiedzią w tym poście: cstheory.stackexchange.com/questions/9652/… , wygląda na to, że BB jest rzeczywiście ściśle monotoniczny

— Avi Tal

Sztuka grania w takie gry polega na naginaniu zasad, więc nie sądzę, żeby liczyło się stwierdzenie, że jakaś funkcja jest nieracjonalna. Gdybyśmy grali w tę grę, zdecydowanie uderzyłbym cię najbardziej obrzydliwą funkcją, o jakiej mogę myśleć (i jestem logikiem).

— Andrej Bauer,

Kiedy mówisz „nierozstrzygalny”, zakładam, że masz na myśli, że jest on niezależny od teorii takiej jak ZFC. Będą takie zdania jak (dla liczb naturalnych , ), które nie są ustalane przez ZFC, zakładając, że ZFC jest spójne. Ponieważ w przeciwnym razie moglibyśmy obliczyć funkcję po prostu szukając dowodów w ZFC takich instrukcji.

b (m) > n

$B(m)>n$

m

$m$

n

$n$

B

$B$

Ponieważ jest zakończone Turinga, istnieje pewna maszyna Turinga z Con (ZFC) $B$ $\Phi$ $\iff$ akceptuje z oracle (powiedzmy na wejściu 0) i Con (ZFC) $\Phi$ $B$ $\neg$ $\iff$ odrzuca. $\Phi$

Zakładając, że faktycznie Con (ZFC) jest prawdą, wiemy, że akceptuje i istnieje pewien zbiór faktów , który został użyty w obliczeniach (możemy to ustawić tak, aby dostęp do Oracle działa w ten sposób). Zatem jest fałszem, ale fakt ten nie jest możliwy do udowodnienia w ZFC, w przeciwnym razie ZFC udowodniłby swoją spójność. Oczywiście można to przepisać jako $\Phi$ $B(m_i)=n_i$ $1\le i\le k$

\sum_{ja = 1}^{k} (b (m_{ja}) - n_{ja})^{2)} > 0

$\sum_{i=1}^k (B(m_i)-n_i)^2>0$

i tak zapewne (*) zapewniaodpowiedźTakna Twoje pytanie.

\begin{matrix} (*) & \sum_{ja = 1}^{k} b (m_{ja})^{2)} + n_{ja}^{2)} > \sum_{ja = 1}^{k} 2) b (m_{ja}) n_{ja} \end{matrix}

$\sum_{i=1}^k B(m_i)^2+n_i^2>\sum_{i=1}^k 2B(m_i)n_i\tag{*}$

Jednak nie sądzę, możemy dowiedzieć się, co te liczby , są, ponieważ zapytania są adaptacyjne (co jest proszony o zależy od odpowiedzi na poprzednie pytania, a nie wiemy, te odpowiedzi). $m_i$ $n_i$

— Bjørn Kjos-Hanssen
źródło

n, m

$n,m$

n_{0} = B (7910)

$n_0=B(7910)$

B (7910) \leq n_{0}

$B(7910)\le n_0$