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

Ваша задача - написать программу с ожидаемым временем выполнения, превышающим оставшееся время до конца юниверса.

Вы можете предположить, что:

• Вселенная умрет от энтропии через 10 ¹⁰⁰⁰ лет.
• Твой компьютер:
  • Будет переживать вселенную, потому что она сделана из Unobtainium .
  • Имеет бесконечный предел памяти / стека / рекурсии.
  • Его процессор имеет ограниченную скорость.

Вы должны показать, что ваша программа завершает работу (извините, бесконечных циклов нет) и рассчитать ожидаемое время ее выполнения.

В стандартных лазейки применяются.

Это задача для игры в гольф, поэтому выигрывает самый короткий код, удовлетворяющий критериям.

РЕДАКТИРОВАТЬ :

К сожалению, было обнаружено (30 минут спустя), что поле невероятности Unobtainium влияет на внутренние часы компьютера, делая его бесполезным. Поэтому программы, основанные на времени, немедленно останавливаются. (Во всяком случае, кто бы оставил программу, которая просто ожидает, что станет ее живым наследием?).

Процессор компьютера аналогичен процессору Intel i7-4578U, поэтому одним из способов измерения времени выполнения является запуск вашей программы на аналогичном компьютере с меньшими входными данными (я надеюсь) и экстраполяция времени ее выполнения.

подиум

#CharsLanguageUpvotes        Author        
1    5      CJam              20       Dennis                  
2    5      J                      5         algorithmshark      
3    7      GolfScript       30       Peter Taylor          
4    9     Python             39       xnor                      
5    10   Matlab             5         SchighSchagh      

_{* Upvotes 31/08}

CJam, 5 байтов

0{)}h

Как это устроено

 0   " Push 0.                                 ";
 {   "                                         ";
   ) " Increment the Big Integer on the stack. ";
 }h  " Repeat if the value is non-zero.        ";

Эта программа остановится, когда куча больше не сможет хранить Big Integer, что не произойдет в ближайшее время на современном настольном компьютере.

Размер кучи по умолчанию на моем компьютере составляет 4 179 623 936 байт (Java 8 в Fedora). Его можно увеличить до произвольного значения с помощью -Xmx, поэтому единственным реальным ограничением является доступная основная память.

Время смерти

Предполагая, что интерпретатору требуется х бит памяти для хранения неотрицательного большого целого числа, меньшего 2 ^х , мы должны считать до 2 ^{8 × 4 179 623 936} = 2 ^{33 436 991 488} . С одним приращением за такт и моим Core i7-3770 (3,9 ГГц с турбонаддувом) это займет 2 ^{33 436 991 488} ÷ 3 400 000 000> 10 10 ^{065 537 393} секунды, что превышает 10 10 ^{065 537 385} лет.

JavaScript, 39

(function f(x){for(;x!=++x;)f(x+1)})(0)

объяснение

Поскольку JavaScript не точно представляет большие целые числа, цикл for(;x!=++x;)завершается, как только xпопадет 9007199254740992.

Тело цикла for будет выполняться Fib(9007199254740992) - 1раз, где Fib(n)n-е число Фибоначчи.

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

Таким образом, (Fib(9007199254740992) - 1) / 150000запуск программы займет не менее секунды. Я не смог рассчитать, Fib(9007199254740992)потому что он очень большой, но я знаю, что он намного больше, чем 10 ¹⁰⁰⁰ * 150 000.

РЕДАКТИРОВАТЬ: Как отмечено в комментариях, Fib(9007199254740992)составляет примерно 4,4092 * 10 ^{1882393317509686} , что действительно достаточно велико.

Python (9)

9**9**1e9

Это имеет более 10 ** 10000000 битов, поэтому вычисление этого должно перенести нас далеко после тепловой смерти.

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

Редактировать: Гольф два символа, удаляя паренсов благодаря @ user2357112. TIL, что Python рассматривает последующие показатели как энергетическую башню.

GolfScript ( 12 7 символов)

9,{\?}*

Это вычисляет и печатает 8 ^ 7 ^ 6 ^ 5 ^ 4 ^ 3 ^ 2 ~ = 10 ^ 10 ^ 10 ^ 10 ^ 183230. Чтобы напечатать его (не говоря уже о вычислениях) за 10 ^ 1000 лет ~ = 10 ^ 1007,5 секунд, нужно напечатать около 10 ^ (10 ^ 10 ^ 10 ^ 183230 - 10 ^ 3) цифр в секунду.

Marbelous 68 66 байт

}0
--@2
@2/\=0MB
}0@1\/
&0/\>0!!
--
@1
00@0
--/\=0
\\@0&0

Marbelous - это 8-битный язык со значениями, представленными шариками только на машине, похожей на Rube Goldberg, так что это было не очень легко. Этот подход примерно эквивалентен следующему псевдокоду:

function recursiveFunction(int i)
{
    for(int j = i*512; j > 0; j--)
    {
        recursiveFunction(i - 1);
    }
}

поскольку максимальное значение равно 256 (в программе Marbleous оно представлено 0, который обрабатывается по-разному в разных местах), recursiveFunction (1) будет вызываться как сумма, 256!*512^256равная примерно 10^1200, достаточно легко, чтобы пережить юниверс.

У Marbelous нет очень быстрого интерпретатора, кажется, что он может выполнять 10^11вызовы этой функции в год, что означает, что мы смотрим на годы выполнения 10^1189.

Дальнейшее объяснение Marbelous правления

00@0
--/\=0
\\@0&0

00является литералом языка (или мрамором), представленным в шестнадцатеричном (т. е. 0). Этот мрамор падает на --, который уменьшает любой мрамор на 1 (00 оборачивается и превращается в FF или 255 в десятичном виде). Мрамор с теперь значением FF падает вниз, \\который толкает его на один столбец вправо, вниз @0. Это портал и телепортирует мрамор на другое @0устройство. Там, мрамор приземляется на /\устройство, которое является дубликатом, он помещает одну копию мрамора --слева (этот мрамор будет повторяться между порталами и уменьшаться на каждой петле) и одну =0справа от него.=0сравнивает мрамор с нулевым значением и позволяет мрамору упасть, если он равен, и толкает его вправо, если нет. Если мрамор имеет значение 0, он попадает на &0синхонизатор, который я объясню позже.

В общем, это просто начинается с 0 значения мрамора в цикле и уменьшает его до тех пор, пока оно снова не достигнет 0, а затем помещает этот 0 значение мрамора в синхронизатор и продолжает цикл в то же время.

}0@1
&0/\>0!!
--
@1

}0является устройством ввода, изначально n-й (базовый 0) ввод командной строки при вызове программы помещается в каждое }nустройство. Поэтому, если вы вызываете эту программу с помощью ввода 2 из командной строки, мрамор значения 02 заменит это }0. Этот шарик затем падает в &0устройство, другой синхронизатор, &nсинхронизаторы удерживают шарики, пока не &nбудут поданы все остальные соответствующие . Затем мрамор уменьшается, телепортируется и дублируется, как в ранее описанном цикле. Правильная копия затем проверяется на неравенство с помощью zero ( >0), если она не равна 0, она проваливается. Если он равен 0, он сдвигается вправо и приземляется !!, что завершает доску.

Итак, пока у нас есть цикл, который непрерывно ведет обратный отсчет от 255 до 0 и позволяет другому, аналогичному циклу (запитанному входом командной строки) запускаться один раз каждый раз, когда он достигает 0. Когда этот второй цикл выполняется n раз (максимум 256) ) программа завершается. Так что это максимум 65536 циклов цикла. Не достаточно, чтобы пережить вселенную.

}0
--@2
@2/\=0MB

Это должно выглядеть знакомо, входные данные уменьшаются один раз, затем это значение циклично оборачивается и копируется (обратите внимание, что мрамор уменьшается только один раз, а не при каждом запуске цикла). Затем он проверяется на равенство 0 и, если он не равен нулю, попадает на MB. Это функция в Marbelous, каждый файл может содержать несколько досок, и каждая доска - это функция, каждая функция должна быть названа перед сеткой :[name]. Каждая функция, кроме первой функции в файле, которая имеет стандартное имя: МБ. Таким образом, этот цикл непрерывно вызывает основную плату снова со значением, n - 1где n - это значение, с которым был вызван этот экземпляр функции.

Так почему же n*512?

Итак, первый цикл выполняется за 4 такта (и 256 раз), а второй цикл выполняется n раз до завершения платы. Это означает, что доска работает около n*4*256тиков. Последний цикл (который выполняет рекурсивный вызов функции) является компактным и выполняется в 2 такта, что означает, что ему удается вызывать функцию n*4*256/2 = n*512раз.

Какие символы вы не упомянули?

\/ Это мусорное ведро, которое удаляет шарики с доски, это гарантирует, что сброшенные шарики не будут мешать другим шарикам, которые зацикливаются в цикле, и предотвращают завершение программы.

бонус

Так как шарики, которые падают с нижней части мраморной доски, выводятся в STDOUT, эта программа печатает множество символов ASCII во время работы.

Perl, 66 58 символов

sub A{($m,$n)=@_;$m?A($m-1,$n?A($m,$n-1):1):$n+1;}A(9,9);

Вышесказанное является реализацией функции Аккермана – Петера . Я понятия не имею, насколько велик A (9,9), но я уверен, что для его оценки потребуется поразительно много времени.

MATLAB, 58 52 символа

Нам нужно по крайней мере одно арифметическое решение конечной точности, следовательно:

y=ones(1,999);while y*y',y=mod(y+1,primes(7910));end

x = единицы (1,999); y = x; в то время как any (y), y = mod (y + x, простые числа (7910)); конец

( спасибо @DennisJaheruddin за то, что он сбил 6 символов )

Количество циклов, необходимое для завершения, дается произведением первых 999 простых чисел. Поскольку подавляющее большинство из них превышает 10, время, необходимое для реализации конвергенции, будет на сотни или тысячи порядков больше минимального временного предела.

Mathematica, 25 19 байтов

Это решение было опубликовано до того, как временные функции были дисквалифицированы.

While[TimeUsed[]<10^10^5]

TimeUsed[]возвращает секунды с начала сеанса, а Mathematica использует типы произвольной точности. В году около 10 ⁷ секунд, поэтому достаточно 10 ¹⁰⁰⁰⁰ секунд.

Более короткая / простая (/ действительная) альтернатива:

For[i=0,++i<9^9^9,]

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

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

Питон 3 - 49

Это делает что-то полезное: вычисляет Пи с беспрецедентной точностью, используя бесконечные ряды Грегори-Лейбница.

На случай, если вам интересно, эта программа зацикливает 10**10**10**2.004302604952323время.

sum([4/(i*2+1)*-1**i for i in range(1e99**1e99)])

Произвольная точность: 78

from decimal import*
sum([Decimal(4/(i*2+1)*-1**i)for i in range(1e99**1e99)])

Источник изображения

Предельное дыхание

Из-за огромных вычислений 1e99**1e99итерации занимают чуть меньше 1e99**1e99года. Теперь (1e99**1e99)-1e1000почти ничего не меняет. Это означает, что эта программа будет работать намного дольше, чем смерть нашей вселенной.

возрождение

Теперь ученые предполагают 10**10**56 years, что Вселенная возродится из-за квантовых флуктуаций или туннелирования. Так что, если каждая вселенная будет в точности одинаковой, сколько всел будет жить в моей программе?

(1e99**1e99)/(1e10+1e1000+10**10**56)=1e9701

Предполагая, что вселенная всегда будет жить 1e10+1e1000годами, а затем потребуется 10**10**56годы, чтобы «перезагрузиться», моя программа будет жить через 1e9701вселенные. Это предполагает, конечно, что unobtainium может пережить Большой взрыв.

Python 59 (работает большую часть времени)

Я не смог устоять

from random import*
while sum(random()for i in range(99)):0

Хотя теоретически это может прекратиться менее чем за миллисекунду, среднее время выполнения значительно превышает 10^400указанный срок жизни юниверса. Спасибо @BetaDecay, @undergroundmonorail и @DaboRoss за сокращение до 17 символов или около того.

J - 5 символов, я думаю

Обратите внимание, что все последующее в арифметике произвольной точности, потому что число 9 всегда имеет немного xрядом с ним.

У нас в семи персонажах, !^:!!9xчто-то вроде бега

n = 9!
for i in range(n!):
    n = n!

в произвольной точности арифметики. Это определенно за предел, потому что Synthetica так сказал , поэтому у нас есть верхняя граница.

В шести символах мы также можем написать ^/i.9x, что вычисляет каждый промежуточный результат 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8. Wolfram | Alpha говорит, что 2^3^4^5^6^7^8это приблизительно 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 6.65185, что, вероятно, также очищает проверку.

У нас также есть пять символов !!!9x, что просто ((9!)!) !. W | A говорит 10 ^ 10 ^ 10 ^ 6.2695, что это должно быть достаточно большим ... Это похоже на 1.6097e1859933-ишские цифры, которые явно больше, чем 3.154e1016число наносекунд во вселенной, но я должен признать, что понятия не имею, как можно выяснить реальные времена этих вещей.

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

C 63 56 символов

f(x,y){return x?f(x-1,y?f(x,y-1):1):y+1;}main(){f(9,9);}

Это основано на идее парня по имени Вильгельм. Мой единственный вклад - сжатие кода до этой короткой (и нечитаемой) части.

Доказательство того, что это заканчивается, делается по индукции.

• Если х равен 0, он немедленно завершается.
• Если это заканчивается для x-1 и любого y, это также заканчивается для x, это само может быть показано индукцией.

Доказательство шага индукции индукцией:

• Если y равен 0, существует только один рекурсивный вызов с x-1, который завершается в предположении индукции.
• Если f (x, y-1) завершается, то f (x, y) также завершается, потому что самый внутренний вызов f в точности равен f (x, y-1), а самый внешний вызов завершается в соответствии с гипотезой индукции.

Ожидаемое время работы A (9,9) / 11837 секунд. Это число имеет больше цифр, чем число кварков в наблюдаемой вселенной.

Matlab ( 10 8 символов)

1:9e1016

ИМХО, большинство записей слишком стараются, вычисляя большие, сложные вещи. Этот код просто инициализирует массив 9x10 ¹⁰¹⁶ double с, считая с 1, что занимает 7,2x10 ^ ¹⁰¹⁷ байт. На современном процессоре с максимальной пропускной способностью памяти 21 ГБ / с или 6,63x10 ^ ¹⁷ байт / год даже инициализация массива займет не менее 1,09x10 ¹⁰⁰⁰ лет, не говоря уже о том, чтобы попытаться напечатать его, поскольку я не беспокоился подавление вывода завершающей точкой с запятой. (;

старое решение

nan(3e508)

альтернативно

inf(3e508)

Этот код просто создаст квадратную матрицу из NaNs / бесконечностей размером 3e508x 3e508 = 9e10168-байтовых двойных или байтовых значений 7.2e1017.

Perl, 16 символов

/$_^/for'.*'x1e9

Это создает строку, повторяющую «. *» Миллиард раз, а затем использует ее как иглу и стог сена в совпадении с регулярным выражением. Это, в свою очередь, заставляет механизм регулярных выражений пытаться выполнить каждый возможный раздел строки длиной два миллиарда символов. Согласно этой формуле из Википедии , существует около 10 ³⁵²¹⁸ таких разделов.

Вышеупомянутое решение имеет длину 16 символов, но требует только около 2 ГБ памяти, что означает, что его можно запустить на реальном компьютере. Если мы предполагаем бесконечную память и конечный размер регистра (что, вероятно, не имеет смысла), его можно сократить до 15 символов, в то же время значительно увеличив время выполнения:

/$_^/for'.*'x~0

(Я не тестировал его, но думаю, что он может работать с 32-битным Perl, построенным на 64-битной машине с не менее 6 ГБ ОЗУ.)

Примечания:

• x является оператором повтора строки
• forне является фактическим цикл; он используется только для сохранения одного символа (по сравнению с $_=".*"x1e9;/$_^/).
• финал ^в регулярном выражении гарантирует, что может совпадать только пустая строка; так как квантификаторы регулярных выражений по умолчанию жадные, это последнее, что попробует движок.
• тесты на моем компьютере для значений (1..13) показывают, что время выполнения на самом деле равно O (exp (n)), что даже больше, чем O (exp (sqrt (n))) в формуле Википедии.

J (12)

(!^:(!!9))9x

К чему это сводится в Python (при условии !работы):

a = 9 
for i in range((9!)!):
    a = a!

РЕДАКТИРОВАТЬ:

Ну, программа может занять не более 2 × 10^-1858926секунд за цикл, чтобы завершить в течение требуемого времени. Совет: это не сработает даже для первого цикла, не говоря уже о последнем;).

Кроме того: этой программе может потребоваться больше памяти, чем энтропии во вселенной ...

C # 217

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

class P{
static void Main(){for(int i=0;i<100;i++){for(int j=0;j<100;j++){Console.WriteLine(ack(i,j));}}}
static int ack(int m,int n){if (m==0) return n+1;if (n ==0) return ack(m-1,1);return ack(m-1,ack(m,n-1));}
}

Первая попытка кода гольф, но здесь идет.

VBA - 57 45

x=0
do
if rnd()*rnd()<>0 then x=0
x=x+1
while 1=1

Таким образом, X увеличится на единицу, если произойдет событие 1 в 2 ^ 128, и сбросится, если оно не произойдет. Код заканчивается, когда это событие происходит 2 ^ 64 + 1 раз подряд. Я не знаю, как начать рассчитывать время, но, думаю, оно огромно.

РЕДАКТИРОВАТЬ: Я разработал математику, и вероятность этого в каждом цикле составляет 1 в 2 ^ 128 ^ (1 + 2 ^ 64), что составляет около 20000 цифр в длину. Предполагая, что 1000000 циклов в секунду (приблизительное число), 30000000 с / год, что составляет 3 * 10 ^ 13 циклов в год, оставшееся 10 ^ 1000 лет - это 3 * 10 ^ 1013 циклов, так что это, вероятно, будет длиться примерно в 20 раз больше оставшееся время осталось во вселенной. Я рад, что моя математика поддерживает мою интуицию.

C, 30 символов

main(i){++i&&main(i)+main(i);}

При условии переполнения со знаком с комплиментом в два комплимента и 32-битных целочисленных значений это будет выполняться примерно для 2 ^{2 32} вызовов функций, что должно быть достаточно времени для завершения юниверса.

GolfScript, 13 символов

0{).`,9.?<}do

Эта программа просто считает от 0 до 10 ^{9 9 -1} = 10 ^387420488 . Предполагая, с оптимизмом, что компьютер работает на частоте 100 ГГц и может выполнять каждую итерацию программы за один цикл, программа будет работать в течение 10 ^{9 9 -12} секунд или примерно 3 × 10 ^{9 9 -20} = 3 × 10 ^387420469 года.

Чтобы протестировать программу, вы можете заменить ее на 9a 2, что остановит ее на 10 ^{2 2 −1} = 10 ³ = 1000. (Использование 3вместо a 2остановит ее на 10 ^{3 3 −1} = 10 ²⁶ , что даже с оптимистическими предположениями, изложенными выше, оно не достигнет хотя бы нескольких миллионов лет.)

Autohotkey 37

loop {
if (x+=1)>10^100000000
break
}

Хаскелл, 23

main=interact$take$2^30

Эта программа завершает работу после прочтения 1073741824 символов из stdin. Если он выполняется без передачи данных stdin, вам нужно будет набрать это количество символов на клавиатуре. Предполагая, что ваша клавиатура имеет 105 клавиш, каждая из которых рассчитана на 100 тыс. Механических циклов и запрограммирована для генерации не мертвых нажатий клавиш, автоповтор отключен, а гнездо для клавиатуры допускает 100 циклов подключения, что дает максимальное количество нажатий клавиш на один компьютер во время безотказной работы 1050000000, что составляет недостаточно для завершения программы.

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

~ ATH, 56

На вымышленном языке ~ ATH :

import universe U;
~ATH(U) {
} EXECUTE(NULL);
THIS.DIE()

~ ATH - невыносимый язык для работы. Его логика состоит из ничего, кроме бесконечных циклов или, в лучшем случае, циклов эффективно бесконечной конструкции.

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

Я прошу прощения за нарушения границы лазейки; Я думал, что это было слишком актуально, чтобы отказаться.

Если кого-то это действительно позабавило, подробности: (1) , (2) , (3) , (4)

Рубин (34)

Линия ([0]*9).permutation.each{print}занимает около 2,47 секунды на 9! печатает на моей машине, в то время как линия ([0]*10).permutation.each{print}занимает около 24,7 секунд на 10! печатает, так что я думаю, что я могу экстраполировать здесь и вычислить, (24.7/10!)*470! seconds in yearsчто составляет 6,87 * 10 ^ 1040, что должно быть время выполнения:

([0]*470).permutation.each{print}

JavaScript 68 62 символа

(function a(m,n){return m==0?n+1:a(m-1,n==0?1:a(m,n-1))})(5,1)

При этом используется функция Аккермана, которая может быть записана как

function ackermann(a, b) {
  if (a == 0) return b + 1;
  if (b == 0) return ackermann(a-1, 1);
  else return ackermann(a-1, ackermann(a, b-1));
}

Его время выполнения увеличивается в геометрической прогрессии и поэтому очень долго вычисляется. Даже если это не английское здесь вы можете получить обзор возвращаемых значений. Согласно таблице ackermann(5,1)равно 2↑↑(65533)-3что, вы знаете, очень большой.

Befunge '93 - 40 байт

(Программа 20х2)

v<<<<<<<<<<<<<<<<<<<
>??????????????????@

Эта программа полагается на случайные числа, чтобы дать ей задержку. Поскольку переводчики Befunge работают довольно медленно, эта программа должна отвечать всем требованиям. И если это не так, мы всегда можем расширить его по горизонтали. Я не совсем уверен, как рассчитать ожидаемое время выполнения этой программы, но я знаю, что каждый? имеет шанс 50/50 либо начать сначала, либо изменить горизонтальное положение на 1. Есть 18? Я думаю, что это должно быть что-то вроде (18 ^ 2) !, который Google Calculator говорит, что "Бесконечность"

РЕДАКТИРОВАТЬ: Ой, я не заметил другой ответ Befunge, это мой первый пост здесь. Сожалею.

APL, 10

Я не думаю, что это правильный ответ (так как он не является детерминированным), но в любом случае ......

{?⍨1e9}⍣≡1

Эта программа вычисляет случайную перестановку чисел 1e9 ( ?⍨1e9) и повторяет до тех пор, пока два последовательных выхода не будут равны ( ⍣≡)

Таким образом, каждый раз, когда вычисляется перестановка, она имеет 1 в 1000000000! шанс прекратить. И 1000000000! составляет не менее 10 ^{10 8} .

Время, необходимое для вычисления перестановки, не имеет значения из-за массивности 1000000000 !. Но некоторые тесты показывают, что это так, O(n)и экстраполяция дает около 30 секунд.

Однако мой интерпретатор отказывается принимать входные данные для случайной функции, превышающей 2 ³¹ -1 (поэтому я использовал 1e9), и генерация перестановок чисел 1000000000 дала ошибку полной рабочей области. Однако концептуально это можно сделать с помощью идеального интерпретатора APL с бесконечной памятью.

Это приводит нас к возможности использования 2 ⁶³ -1 вместо 1e9, чтобы увеличить время работы по крайней мере до 10 ^{10 20} , предполагая 64-битную архитектуру.

Но подождите, уместна ли архитектура в идеальном интерпретаторе? Черт, нет, поэтому на самом деле нет верхней границы времени выполнения !!

R, 45 байт

(f=function(x)if(x)f(x-1)+f(x-1)else 0)(9999)

Это старая ветка, но я не вижу ответа R, и мы не можем этого иметь!

Время выполнения для меня было около 1 с, когда х было 20, предлагая время выполнения 2 ^ 9979 секунд.

Если вы замените ноль на единицу, то результат будет 2 ^ x, но, как он есть, выход равен нулю, каким бы x ни был (избегает проблем переполнения).

Javascript, 120 байт

a=[0];while(a.length<1e4)(function(){var b=0;while(b<a.length){a[b]=(a[b]+1)%9;if(a[b])return;b++}a.push(1)})();alert(a)

Может быть сделано с минимальным объемом памяти (вероятно, менее половины мегабайта), но (вероятно) занимает около 10 ^{8 750} лет, чтобы остановиться.

Многократно увеличивает BigInteger с начальным порядком байтов до 9, пока не достигнет 9 ^{10 4 -1} .

Python 3, 191 байт

from random import*
r=randint
f=lambda n:2if n<2else f(n-1)
x=9E999
s=x**x
for i in range(f(x)**f(s)):
 while exec(("r(0,f(x**i))+"*int(f(x)))+"r(0,f(x**i))")!=0:
  s=f(x**s)
  print(s)

Во-первых, f является рекурсивной факториальной функцией и является очень медленной. Затем существует 9 * 10⁹⁹⁹, наделенная собой, которая генерирует OverflowError, но этого не происходит на этом компьютере Unobtanium. For-Loop повторяет 9E999! ^ (9E999 ^ 9E999)! раз и переходят к следующей итерации, только если 9E999! +1 случайные числа между 0 и 9E99 * ^ i! все равны 0 и в каждой итерации цикла while устанавливается значение (9E999 ^ s) !. Ну, я забыл, что печать s занимает много времени ...
Я знаю, что это не самое короткое решение, но я думаю, что это действительно эффективно. Может ли кто-нибудь помочь мне рассчитать время работы?

Машина Тьюринга, но гораздо хуже , 167 байтов

0 0 1 1 2 0 0
1 0 1 0 4 0 0
0 1 1 1 2 0 0
1 1 1 1 5 0 0
0 2 1 0 3 0 0
1 2 0 1 1 0 0
0 3 1 1 4 0 0
1 3 0 0 2 0 0
0 4 1 0 0 0 0
1 4 0 1 3 0 0
0 5 1 0 6 0 1
1 5 1 1 2 0 0

Попробуйте онлайн!

Следует запустить Busy Beaver из 6 символов с двумя состояниями со страницы Википедии .

Как сказано на странице Википедии, он работает в $7.412 \times 10^{36534}$шаги. Это намного больше, чем тепловая смерть, при условии, что она выполняет каждую команду более чем на одну наносекунду или равна ей.