Расчеты таблицы умывальников и алгоритм, который, как известно, не заканчивается в ZFC

12

В таблицах Laver приводятся примерами программ , которые не были показаны , чтобы прекратить в стандартной системе аксиом математики ZFC но которые заканчиваются , когда один принимает очень большие кардинальные аксиомы.

Вступление

Классические столы Laver являются единственными конечными алгебры с основным множеством и операция , которая удовлетворяет идентичности и где для и где .An{1,...,2n}*x * (y * z)=(x * y) * (x * z)x*1=x+1x<2n2n*1=1

Более подробную информацию о классических таблицах Лейвера можно найти в книге Патрика Дехорного «Косы и самораспределение».

Вызов

Какой самый короткий код (в байтах), который вычисляется 1*32в классических таблицах Лейвера и заканчивается точно, когда он находит nс ? Другими словами, программа завершается тогда и только тогда, когда она находит с, но в противном случае она работает вечно.1*32<2nn1*32<2n

мотивация

Ранг в-ранг кардинал (также называемый I3-кардинал) является чрезвычайно большим уровнем бесконечности и , если предположить существование кардинала ранга в-ранг, то один может доказать больше теорем , чем если бы один не делает Предположим, что существует рядовой кардинал. Если существует кардинал ранга в ранг, то есть классическая таблица Лавера, где . Тем не менее, нет никаких известных доказательств того, что в ZFC. Кроме того, известно, что наименьшее значение где больше, чем (что является чрезвычайно большим числом, поскольку функция Аккермана является быстрорастущей функцией). Поэтому любая такая программа будет длиться очень долго.An1*32<2n1*32<2nn1*32<2nAck(9,Ack(8,Ack(8,254)))Ack

Я хочу увидеть, насколько короткой может быть написана программа, чтобы мы не знали, завершается ли программа с использованием стандартной аксиоматической системы ZFC, но откуда мы знаем, что программа в конечном итоге заканчивается в гораздо более сильной аксиоматической системе, а именно ZFC + I3. Этот вопрос был вдохновлен недавним постом Скотта Ааронсона, в котором Ааронсон и Адам Йедидия построили машину Тьюринга с менее чем 8000 состояний, так что ZFC не может доказать, что машина Тьюринга не завершается, но известно, что она не завершается, если принять большие кардинальные гипотезы.

Как вычисляются классические таблицы Лейвера

При вычислении таблиц Лейвера обычно удобно использовать тот факт, что в алгебре мы имеем для всех в .An2n * x=xxAn

Следующий код вычисляет классическую таблицу Лейвера An

# table (n, x, y) возвращает x * y в A n
Таблица: = функция (п, х, у)
если x = 2 ^ n, вернуть y;
elif y = 1, затем вернуть x + 1;
иначе возвращаемая таблица (n, таблица (n, x, y-1), x + 1); Fi; конец;

Например, вход table(4,1,2)вернется 12.

Код для table(n,x,y)довольно неэффективен, и он может вычисляться в таблице Laver только в разумные сроки. К счастью, есть намного более быстрые алгоритмы для вычисления классических таблиц Лавера, чем приведенные выше.A4

Джозеф Ван Имя
источник
2
Добро пожаловать в PPCG! Отличный пост!
NoOneIsHere
1
Согласно Википедии, Ack (9, Ack (8, Ack (8,254))) является нижней границей n, для которого период превышает 16. Для этого мы можем проверить 1 * 16, а не 1 * 32. Я исправлю свою программу соответственно.
Джон Тромп
1
Я начал писать машину Тьюринга, чтобы сделать это, и я думаю, что я обнаружил ошибку «фактор за двумя». Разве Догерти не доказал, что Ack(9,Ack(8,Ack(8,254)))это нижняя граница для первой таблицы, в которой первая строка имеет период 32, т.е. где 1*16 < 2^n?
Питер Тейлор
1
Если у вас есть двухсимвольная машина с 20 состояниями для Аккермана, тогда, пожалуйста, дайте мне ссылку, потому что я, вероятно, могу украсть некоторые идеи из нее. У меня есть 44 состояния для вычисления table(n,x,y), и я думаю, что потребуется 25-30 состояний, чтобы установить константы и внешний цикл. Единственное прямое представление ТМ, которое я могу найти на esolangs.org, - esolangs.org/wiki/ScripTur, и это не совсем то, что в гольфе.
Питер Тейлор
1
cheddarmonk.org/papers/laver.pdf - столько, сколько я ожидаю сделать на этой неделе, потому что я собираюсь путешествовать.
Питер Тейлор

Ответы:

4

Двоичное лямбда-исчисление, 215 бит (27 байт)

\io. let
  zero = \f\x. x;
  one = \x. x;
  two = \f\x. f (f x);
  sixteen = (\x. x x x) two;
  pred = \n\f\x. n (\g\h. h (g f)) (\h. x) (\x. x);
  laver = \mx.
    let laver = \b\a. a (\_. mx (b (laver (pred a))) zero) b
    in laver;
  sweet = sixteen;
  dblp1 = \n\f\x. n f (n f (f x)); -- map n to 2*n+1
  go2 = \mx. laver mx sweet mx (\_. mx) (go2 (dblp1 mx));
in go2 one

компилируется в (с использованием программного обеспечения по адресу https://github.com/tromp/AIT )

000101000110100000010101010100011010000000010110000101111110011110010111
110111100000010101111100000011001110111100011000100000101100100010110101
00000011100111010100011001011101100000010111101100101111011001110100010

Это решение в основном связано с https://github.com/int-e

Джон Тромп
источник
2
Я не уверен, как вы получили ваш счет, но по умолчанию представления должны оцениваться в соответствии с количеством байтов в коде. Я считаю 375 байт для этого представления. Вы также должны указать название языка и, при необходимости, ссылку на переводчика для языка.
Алекс А.
Вы, вероятно, должны включить в свой пост точный код длиной 234 бита.
CalculatorFeline
2
Кодировка может быть найдена в Википедии . Там также ссылка на этот переводчик (не проверено). Они должны быть проверены, и двоичная кодировка также должна быть в посте.
PurkkaKoodari
1
Для скомпилированных языков мы оцениваем код, написанный пользователем, а не количество байтов в сгенерированном двоичном файле.
Алекс А.
5
@AlexA. Это не обязательно ... любая форма кода, понятная компилятору или интерпретатору, подойдет.
feersum
4

CJam ( 36 32 байта)

1{2*31TW$,(+a{0X$j@(@jj}2j)W$=}g

На практике эта ошибка выдается довольно быстро, потому что она переполняет стек вызовов, но на теоретически неограниченной машине это правильно, и я понимаю, что это предположение этого вопроса.

Код для table(n,x,y)довольно неэффективен, и он может вычисляться только в таблице Laver A 4 в разумные сроки.

на самом деле не правильно, если мы кешируем вычисленные значения, чтобы избежать их повторного вычисления. Это подход, который я jвыбрал , используя оператор (памятка) . Он тестирует A 6 в миллисекундах и переполняет стек, тестируя A 7 - и я фактически деоптимизирован table в интересах игры в гольф.

рассечение

Если мы предположим, что nэто понимается из контекста, а не

f(x,y) =
    x==2^n ? y :
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

мы можем удалить первый частный случай, давая

f(x,y) =
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

и это все еще работает, потому что

f(2^n, 1) = 2^n + 1 = 1

и для любого другого y,

f(2^n, y) = f(f(2^n, y-1), 1) = f(2^n, y-1) + 1

поэтому по индукции мы получаем f(2^n, y) = y.

Для CJam оказывается удобнее поменять порядок параметров. И вместо использования диапазона 1 .. 2^nя использую диапазон 0 .. 2^n - 1путем уменьшения каждого значения, поэтому рекурсивная функция, которую я реализую,

g(y,x) =
    y==0 ? x+1
         : g(x+1, g(y-1, x))

1           e# Initial value of 2^n
{           e# do-while loop
  2*        e#   Double 2^n (i.e. increment n)
  31T       e#   table(n,1,32) is g(31,0) so push 31 0
  W$,(+a    e#   Set up a lookup table for g(0,x) = x+1 % 2^n
  {         e#   Memoisation function body: stack is 2^n ... y x
    0X$j    e#     Compute g(0,x) = x+1 % 2^n
            e#     Stack is 2^n ... y x (x+1%2^n)
    @(      e#     Bring y to top, decrement (guaranteed not to underflow)
            e#     Stack is 2^n ... x (x+1%2^n) (y-1%2^n)
    @jj     e#     Rotate and apply memoised function twice: g(x+1,g(y-1,x))
  }
  2j        e#   Memoise two-parameter function
            e#   Stack: 2^n g(31,0)
  )W$=      e#   Test whether g(31,0)+1 is 2^n
}g          e# Loop while true
Питер Тейлор
источник
1

Pyth, 33 байта

.N?qT^2NY?tY:N:NTtYhThT<:T1 32^2T

Попробуйте онлайн! (Очевидно, что часть тестирования здесь не включена.)

Дрянная Монахиня
источник
Какая петля? Кроме того, что fiв коде означает?
Утренняя монахиня