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$

Nieporównywalne liczby naturalne

Odpowiedzi: