В таблицах Laver приводятся примерами программ , которые не были показаны , чтобы прекратить в стандартной системе аксиом математики ZFC но которые заканчиваются , когда один принимает очень большие кардинальные аксиомы.
Вступление
Классические столы Laver являются единственными конечными алгебры с основным множеством и операция , которая удовлетворяет идентичности и где для и где .An
{1,...,2n}
*
x * (y * z)=(x * y) * (x * z)
x*1=x+1
x<2n
2n*1=1
Более подробную информацию о классических таблицах Лейвера можно найти в книге Патрика Дехорного «Косы и самораспределение».
Вызов
Какой самый короткий код (в байтах), который вычисляется 1*32
в классических таблицах Лейвера и заканчивается точно, когда он находит n
с ? Другими словами, программа завершается тогда и только тогда, когда она находит с, но в противном случае она работает вечно.1*32<2n
n
1*32<2n
мотивация
Ранг в-ранг кардинал (также называемый I3-кардинал) является чрезвычайно большим уровнем бесконечности и , если предположить существование кардинала ранга в-ранг, то один может доказать больше теорем , чем если бы один не делает Предположим, что существует рядовой кардинал. Если существует кардинал ранга в ранг, то есть классическая таблица Лавера, где . Тем не менее, нет никаких известных доказательств того, что в ZFC. Кроме того, известно, что наименьшее значение где больше, чем (что является чрезвычайно большим числом, поскольку функция Аккермана является быстрорастущей функцией). Поэтому любая такая программа будет длиться очень долго.An
1*32<2n
1*32<2n
n
1*32<2n
Ack(9,Ack(8,Ack(8,254)))
Ack
Я хочу увидеть, насколько короткой может быть написана программа, чтобы мы не знали, завершается ли программа с использованием стандартной аксиоматической системы ZFC, но откуда мы знаем, что программа в конечном итоге заканчивается в гораздо более сильной аксиоматической системе, а именно ZFC + I3. Этот вопрос был вдохновлен недавним постом Скотта Ааронсона, в котором Ааронсон и Адам Йедидия построили машину Тьюринга с менее чем 8000 состояний, так что ZFC не может доказать, что машина Тьюринга не завершается, но известно, что она не завершается, если принять большие кардинальные гипотезы.
Как вычисляются классические таблицы Лейвера
При вычислении таблиц Лейвера обычно удобно использовать тот факт, что в алгебре мы имеем для всех в .An
2n * x=x
x
An
Следующий код вычисляет классическую таблицу Лейвера 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
источник
Ack(9,Ack(8,Ack(8,254)))
это нижняя граница для первой таблицы, в которой первая строка имеет период 32, т.е. где1*16 < 2^n
?table(n,x,y)
, и я думаю, что потребуется 25-30 состояний, чтобы установить константы и внешний цикл. Единственное прямое представление ТМ, которое я могу найти на esolangs.org, - esolangs.org/wiki/ScripTur, и это не совсем то, что в гольфе.Ответы:
Двоичное лямбда-исчисление, 215 бит (27 байт)
компилируется в (с использованием программного обеспечения по адресу https://github.com/tromp/AIT )
Это решение в основном связано с https://github.com/int-e
источник
CJam (
3632 байта)На практике эта ошибка выдается довольно быстро, потому что она переполняет стек вызовов, но на теоретически неограниченной машине это правильно, и я понимаю, что это предположение этого вопроса.
на самом деле не правильно, если мы кешируем вычисленные значения, чтобы избежать их повторного вычисления. Это подход, который я
j
выбрал , используя оператор (памятка) . Он тестирует A 6 в миллисекундах и переполняет стек, тестируя A 7 - и я фактически деоптимизированtable
в интересах игры в гольф.рассечение
Если мы предположим, что
n
это понимается из контекста, а немы можем удалить первый частный случай, давая
и это все еще работает, потому что
и для любого другого
y
,поэтому по индукции мы получаем
f(2^n, y) = y
.Для CJam оказывается удобнее поменять порядок параметров. И вместо использования диапазона
1 .. 2^n
я использую диапазон0 .. 2^n - 1
путем уменьшения каждого значения, поэтому рекурсивная функция, которую я реализую,источник
Pyth, 33 байта
Попробуйте онлайн! (Очевидно, что часть тестирования здесь не включена.)
источник
fi
в коде означает?