В качестве продолжения завершающей программы Shortest, выходной размер которой превышает число Грэма, а Golf - число больше, чем TREE (3) , я представляю новую задачу.
Номер загрузчика очень большой, его сложно объяснить (так как он сам был результатом упражнения в гольф-коде с гибкой целью). Существует определение и объяснение здесь , но для целей замкнутости, я попытаюсь объяснить это позже в этой должности , а также.
Алгоритм, который использовал Ralph Loader, дает одно из самых больших чисел среди всех (вычислимых) алгоритмов, когда-либо написанных! Действительно, число загрузчика является самым большим «вычислимым» числом в вики-сайте Googology. (Под «вычислимым» числом они подразумевают число, определенное в терминах вычислений.) Это означает, что если ответ производит интересное число, большее числа загрузчика (т.е. не только число загрузчика + 1), вы можете перейти в История гугологии! При этом программы, которые выдают что-то вроде номера загрузчика + 1 , безусловно, являются верными ответами и претендентами на этот вопрос; просто не жди славы.
Ваша задача состоит в том, чтобы создать завершающую программу, которая выдает число, превышающее число загрузчика. Это код-гольф , поэтому выигрывает самая короткая программа!
- Вы не можете принимать участие.
- Ваша программа должна в конечном итоге завершиться детерминистически, но вы можете предположить, что машина имеет бесконечную память.
- Вы можете предположить, что тип числа вашего языка может содержать любое конечное значение, но вам нужно объяснить, как именно это работает в вашем языке (например: имеет ли плавание бесконечную точность?)
- Бесконечности не допускаются как выходные данные.
- Недостаток числового типа вызывает исключение. Это не обернуть вокруг.
- Вы должны предоставить объяснение того, почему ваш номер такой большой, и версию вашего кода, на которую не обращали внимания, чтобы проверить, действительно ли ваше решение действительно (так как нет компьютера с достаточным объемом памяти для хранения номера загрузчика).
Итак, вот объяснение номера загрузчика. См. Http://googology.wikia.com/wiki/Loader%27s_number и ссылки в нем для более точной информации. В частности, он содержит программу, которая выдает номер загрузчика точно (по определению).
Исчисление конструкций по существу является языком программирования с очень особыми свойствами.
Прежде всего, любая синтаксически допустимая программа завершается. Там нет бесконечных петель. Это будет очень полезно, потому что это означает, что если мы запустим программу произвольного исчисления конструкций, наша программа не застрянет. Проблема в том, что это означает, что исчисление конструкций не является полным по Тьюрингу.
Во-вторых, среди нетуринговых полных языков он является одним из самых мощных. По сути, если вы можете доказать, что машина Тьюринга будет останавливаться на каждом входе, вы можете запрограммировать функцию в исчислении конструкций, которая будет имитировать ее. (Это не делает его тьюринг завершенным, потому что есть машины остановки, которые вы не можете доказать, останавливаются.)
Номер загрузчика - это, по сути, номер занятого бобра для исчисления конструкций, который можно вычислить, поскольку все программы coc завершаются.
В частности, loader.c определяет вызываемую функцию D. Приблизительно, D(x)итерирует по всем битовым строкам меньше, чем x, интерпретирует их как кок-программы, запускает синтаксически допустимые и объединяет результаты (которые также будут битовыми строками ). Возвращает это объединение.
Номер загрузчика есть D(D(D(D(D(99))))).
Более читаемая копия кода из вики по googolology
int r, a;
P(y,x){return y- ~y<<x;}
Z(x){return r = x % 2 ? 0 : 1 + Z (x / 2 );}
L(x){return x/2 >> Z(x);}
S(v,y,c,t){
int f = L(t);
int x = r;
return f-2 ? f>2 ? f-v ? t-(f>v)*c : y : P(f,P(S(v,y,c,L(x)), S(v+2,t=S(4,13,-4,y),c,Z(x)))) : A(S(v,y,c,L(x)),S(v,y,c,Z(x)));
}
A(y,x){return L(y)-1 ? 5<<P(y,x) : S(4,x,4,Z(r));}
D(x)
{
int f;
int d;
int c=0;
int t=7;
int u=14;
while(x&&D(x-1),(x/=2)%2&&(1)){
d = L(L(D(x))),
f = L(r),
x = L(r),
c - r||(L(u)||L(r)-f||(x/=2)%2&&(u=S(4,d,4, r),t=A(t,d)),f/2&(x/=2)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),
c&&(x/=2)%2&&(t=P(~u&2|(x/=2)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r)
u/2&(x/=2)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);
}
return a = P( P( t, P( u, P( x, c)) ),a);
}
main(){return D(D(D(D(D(99)))));}
источник
Ответы:
JavaScript, D ^ 6 (9) (
508501495492487485481 байт)Это кодированный код.
Декодированный код:
Декодированный, негольфированный код (условия и прочее хранятся в loader.c):
В этом предполагается, что:
NumberNumberАлгоритм кодирования / декодирования:
Кодировка выполняется следующим образом:
Алгоритм декодирования:
Сжатие было сделано с этим кодом , отметьте только последний флажок. Так как это сначала закодирует наибольшее сохранение, это не самое эффективное сжатие, но я тоже не знаю, как сделать его меньше.
JavaScript, (339 символов )
Этот код примет 16-битную строку как a, преобразует ее в 8-битную строку с тем же двоичным кодом (BE) и
evalэтим.Декодированный код является закодированным кодом выше.
Доказательство того, что D ^ 6 (9)> D ^ 5 (99)
Для этого мы бы сравнили D (9) и 99.
При ручном запуске кода D (9) оказывается равным
(15*2^14849+1)*2^((15*2^14849+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^929+1)*2^((15*2^929+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^(15*2^59+1)))))))))))))))))))))))))))))))), а даже D (0) равно8646911284551352321.Итак, D (9) >>> 99, а поскольку D строго возрастает, D ^ 6 (9)> D ^ 5 (99).
D(D(D(D(D(99)))))наD(D(D(D(D(D(9)))))). Также это перемешало буквы.&&(1)дляD(x)условия цикла./2s в>>1s, потому чтоNumberfor...inнаfor...of.evalдляDудаленияreturn.источник
Python 3, D ^ 6 (9) (
608600599 байт)Это кодированный код. Выдержки:
В этом предполагается, что:
Это в основном порт моего ответа JavaScript . Для более подробной информации, проверьте это.
Сжатие было сделано с этим .
Я не очень хорошо осведомлен в Python, поэтому, безусловно, есть места для сохранения байтов.
Я думаю, что суб-600 возможно.суб-600 был доказан.Sдля уменьшения скобокu/2в третьей последней строке определенияDtou>>1, сохранение байта от сжатия его до символа с другими>>1s.источник
Рубин, D ^ 6 (9) (553 байта)
Это кодированный код. Выдержки:
Этот код является номером загрузчика с D 6 (9) вместо.
В этом предполагается, что:
Это в основном порт моего ответа на JavaScript и Python 3 ответов . Для более подробной информации, проверьте их.
Сжатие было сделано с этим (может появиться, поскольку это не существует).
Я новичок в Ruby, так что, возможно, под 512 возможно, но я сомневаюсь в этом.
источник