Несопоставимые натуральные числа

11

Игра «Назови наибольшее число» просит двух игроков тайно записать число, и победителем становится тот, кто записал большее число. Игра обычно позволяет игрокам записывать функции, оцененные в определенный момент, поэтому 2222 также было бы приемлемо записать.

Значение функции Busy Beaver, BB(x) , не может быть определено (в ZFC или любой разумной последовательной аксиоматической системе) для больших значений x . В частности, BB(104) не может быть определен согласно этой статье . Однако это не означает, что мы не можем сравнивать значения функции Busy Beaver. Например, мы можем доказать, что BB(x) строго монотонна .

Предположим, что мы позволяем игрокам записывать выражения, включающие композиции элементарных функций, натуральные числа и функцию Busy Beaver. Есть ли два выражения, которые два игрока могут записать так, что мы можем доказать в ZFC, что определение победителя в ZFC невозможно (при условии, что ZFC непротиворечив)?

РЕДАКТИРОВАТЬ: Первоначально этот вопрос сказал «... произвольные комбинации вычислимых функций, натуральных чисел и функции Busy Beaver».

Если мы позволим f(x) принять значение 3 если BB(x)> [что-то безбожно большое и невыразимое на этом сайте] и 7 если это не так, то f(104) и 6 несопоставимы.

Это не удовлетворяет меня, в основном потому, что f не является разумной функцией для кого-то, чтобы использовать в этой игре. Я не понимаю, как выразить свою интуицию по этому поводу, поэтому я ограничил вопрос, чтобы избежать кусочных функций.

Стелла Бидерман
источник
1
BB(104)BB(104)
2
BB(x)BB(x)
1
Согласно ответу в этом посте: cstheory.stackexchange.com/questions/9652/… кажется, что BB действительно строго монотонен
Ави Тал
Искусство играть в такие игры состоит в том, чтобы нарушать правила, так что я не думаю, что можно считать, что какая-то функция неразумна. Если бы мы играли в игру, я бы определенно поразил вас самой отвратительной функцией, которую я могу себе представить (и я логик).
Андрей Бауэр

Ответы:

9

B(m)>n
mnB

BΦ ΦB¬ Φ

ΦB(mi)=ni1ik

i=1k(B(mi)ni)2>0
(*)i=1kB(mi)2+ni2>i=1k2B(mi)ni

mini

Бьёрн Кьос-Хансен
источник
1
n,m
5
n0=B(7910)B(7910)n0