101
\$\begingroup\$

It's time to face the truth: We will not be here forever, but at least we can write a program that will outlive the human race even if it struggles till the end of time.

Your task is to write a program that has a expected running time greater than the remaining time till the end of the universe.

You may assume that:

  • The universe will die from entropy in 101000 years.
  • Your computer:
    • Will outlive the universe, because it is made of Unobtainium.
    • Has infinite memory/stack/recursion limit.
    • Its processor has limited speed.

You must show that your program terminates (sorry, no infinite loops) and calculate its expected running time.

The standard loopholes apply.

This is a code golf challenge, so the shortest code satisfying the criteria wins.

EDIT:

Unfortunately, it was found (30min later) that the improbability field of Unobtainium interferes with the internal clock of the computer, rendering it useless. So time based programs halt immediately. (Who would leave a program that just waits as its living legacy, anyway?).

The computer processor is similar to the Intel i7-4578U, so one way to measure the running time is to run your program in a similar computer with a smaller input (I hope) and extrapolate its running time.


Podium

#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 on 31/08

\$\endgroup\$
  • 40
    \$\begingroup\$ I was tempted to create a [slowest-code] tag for this question. :P \$\endgroup\$ – Doorknob Aug 24 '14 at 22:08
  • 5
    \$\begingroup\$ A Bogosort wouldn't work because while it's infinitely improbable that it would never finish, it may require an infinite amount of time to finish. There are, however many awful NFA-based regular expressions that could satisfy the "will finish, but not before the universe is dead" criteria. \$\endgroup\$ – DavidO Aug 24 '14 at 22:16
  • 49
    \$\begingroup\$ Your title should be a tshirt \$\endgroup\$ – user-2147482637 Aug 25 '14 at 2:54
  • 4
    \$\begingroup\$ Nice question, but shouldn't it be popularity contest ? \$\endgroup\$ – IazertyuiopI Aug 25 '14 at 6:38
  • 12
    \$\begingroup\$ I think Isaac Asimov wrote a story about this. \$\endgroup\$ – David Conrad Aug 25 '14 at 17:02

31 Answers 31

1
2
0
\$\begingroup\$

Runic Enchantments, ~1823 bytes

\DB͍R"000000000000000000000000000000000000001"$
.{ww;'''''''''''''''''''''''''''''''''''''''
.10{BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
a+'0000000000000000000000000000000000000000
kk0~111111111111111111111111111111111111111
$:{~+++++++++++++++++++++++++++++++++++++++
1'~}567890123456789012345678901234567890123
J://XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
.=? 000001111111112222222222333333333344444
/\/v\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Try it online!

Or rather, some arbitrarily large variation thereof. Taken from this answer where an explanation on how it works can be found. Additionally, running this "in perpetuity" would require a version of the interpreter which does not self-halt after 1,000,000 execution steps, but I will assume this as true as the unobtaining machine the code is running on as it only requires an adjustment to one line of code.

According to TIO this can print numbers out to 100 in about 0.141s (the flux here is almost irrelevant in terms of the final result: +/- ~10 bytes for being 10 times faster or slower for needing an extra digit of precision). So reaching 99999999999999999999999999999 should take about 4,471,080,669,710,806,697 (1018) years...and ten of its most significant decimals would still be 0, which bumps things to 1028 years. Depicted code only has 39 digits worth of precision in base-10 and we can go bigger.

Only one byte different takes it to an effective base 78 (with a maximum value around 6x1073). Tweaking the "0" down to the lowest allowable character ("#") brings that to base 92 (with a maximum value around 4x1076).

That brings us to needing a 515 digit base 92 number, which is also doable using the ´ command to need only n+1 cells to represent a base 10 number with n digits (for the purposes of write location offsets), e.g. this program changes the 4X3+ to 4´3, and as long as an empty row of cells is supplied between the column value (~1 byte per digit for all the spaces in order to allow for 3 digit numbers) and the 10B command any value can be expressed and needing approximately 5722 bytes.

However, we can still raise the integer base a bit more. ˿ is the last non-combining Unicode value accessible without performing any additional logic checks, allowing for a base 733 number which means that we only need 353 digits of precision, reducing the program size of about 3940 bytes.

But we can still go smaller still.

35-767 is not the largest unicode block usable without needing additional logic. If we instead use Unicode values 880 to 6831 (inclusive) we have an effective base of 5953, requiring only 268 digits of precision. Accounting for the two bytes needed to represent the initial characters, that gives a program size of approximately 3275 bytes.

Adding in the additional logic would allow for a maximum base of 64654, requiring only 211 digits of precision and costing only another 79 bytes or so based on this answer.

But we can still golf a few bytes. Remember the ´ command? We don't really need it. Now that we're down to only a 211 digit number, all the values needed (up to 216) can be represented with only 2-3 bytes (instead of 5): char values implicitly convert to integers when required in any command that expects integers and nearly all the chars needed (from 5 to 216) can be utilized in this manner. Only 10, 60, 62, 94 and 118 are problematic. And all of them can still be expressed in 4 bytes or less:

10  -> a
60  -> 6X
62  -> 6X2+
94  -> 9x4+
118 -> bX8+

For 62, 94, and 118 it ends up being easier to just not use those columns. Increases program size by 8 bytes each (24 bytes) in order to not need the spaces to align the commands out to 118 (236 bytes).

Final score: 1823 bytes.

211 digit number      -  1 byte per digit of initial value
Programmatic overhead -  56 bytes (roughly, the left 4 columns and right 3 columns)
Digit processing      -  7 bytes * digits (1477 bytes)
Bad Character logic   -  ~79 bytes (some additional control flow is likely required)

(Intermediate values were approximated at 10 bytes (original program height) per digit of initial value +57 +unicode penalty where appropriate: eg. 1 byte per digit of initial value +1 or +2 for representation in programmatic overhead).

Final thoughts:

It may be possible to turn this answer into a self-repeating execution instead of a quine, but I have so far not had success getting it to Eval properly. I suspect that it attempts to Eval the string and the parser throws an error for some reason. If that were fixed, a shorter solution to the "take forever" problem would be possible: push the quine, duplicate, Eval, compare with original (lossless). If not the same: loop, else terminate. The number of Eval attempts (i.e. the original period count) is already near the number of years required by this challenge, so increasing the number of loops by a factor of ~32 billion (iteration -> years) seems relatively doable in less than 1300 bytes. Increasing the program length from 387 "digits" to 485 "digits" looks like it would be enough.

| improve this answer | |
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.