If a program terminates and there is no one to see it, does it halt?

Question

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 10¹⁰⁰⁰ 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

#	Chars	Language	Upvotes	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}

Answer 1

JavaScript, 39

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

Explanation

Since JavaScript does not precisely represent large integers, the loop for(;x!=++x;) terminates once x hits 9007199254740992.

The body of the for loop will be executed Fib(9007199254740992) - 1 times, where Fib(n) is the nth fibonacci number.

From testing, I know my computer will do less than 150,000 iterations per second. In reality, it would run much slower because the stack would grow very large.

Thus, the program will take at least (Fib(9007199254740992) - 1) / 150000 seconds to run. I have not been able to calculate Fib(9007199254740992) because it is so large, but I know that it is much larger than 10¹⁰⁰⁰ * 150,000.

EDIT: As noted in the comments, Fib(9007199254740992) is approximately 4.4092*10^{1882393317509686}, which is indeed large enough.

Answer 2

Python (9)

9**9**1e9

This has more than 10**10000000 bits, so computing it should take us far past heat death.

I checked that this takes more and more time for larger but still reasonable values, so it's not just being optimized out by the interpreter.

Edit: Golfed two chars by removing parens thanks to @user2357112. TIL that Python treats successive exponents as a power tower.

Answer 3

CJam, 5 bytes

0{)}h

How it works

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

This program will halt when the heap cannot store the Big Integer anymore, which won't happen anytime soon on a modern desktop computer.

The default heap size is 4,179,623,936 bytes on my computer (Java 8 on Fedora). It can be increased to an arbitrary value with -Xmx, so the only real limit is the available main memory.

Time of Death

Assuming that the interpreter needs x bits of memory to store a non-negative Big Integer less than 2^x, we have to count up to 2^{8 × 4,179,623,936} = 2^{33,436,991,488}. With one increment per clock cycle and my Core i7-3770 (3.9 GHz with turbo), this will take 2^{33,436,991,488} ÷ 3,400,000,000 > 10^{10,065,537,393} seconds, which is over 10^{10,065,537,385} years.

Answer 4

Marbelous 68 66 bytes

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

Marbelous is an 8 bit language with values only represented by marbles in a Rube Goldberg-like machine, so this wasn't very easy. This approach is roughly equivalent to the following pseudo-code:

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

since the maximum value is 256, (represented by 0 in the Marbleous program, which is handled differently in different places) recursiveFunction(1) will get called a total of 256!*512^256 which equals about 10^1200, easily enough to outlive the universe.

Marbelous doesn't have a very fast interpreter, it seems like it can run about 10^11 calls of this function per year, which means we're looking at a runtime of 10^1189 years.

Further explanation of the Marbelous board

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

00 is a language literal (or a marble), represented in hexadecimal (so 0). This marble falls down onto the --, which decrements any marble by 1 (00 wraps around and turns into FF or 255 in decimal). The Marble with now the value FF falls down onto the \\ which shoves it one column to the right, onto the lower @0. This is a portal and teleports the marble to the other @0 device. There, the marble lands on the /\ device, which is a duplicator, it puts one copy of the marble on the -- to its left (this marble will keep looping between the portals and get decremented on every loop) and one on the =0 to its right. =0 compares the marble to the value zero and lets teh marble fall trough if it's equal and pushes it to the right if not. If the marble has teh value 0, it lands on &0, a synchonizer, which I will explain further, later.

All in all, this just starts with a 0 value marble in a loop and decrements it until it reaches 0 again, it then puts this 0 value marble in a synchronizer and keeps looping at the same time.

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

}0 is an input device, initially the nth (base 0) command line input when calling the program gets placed in every }n device. So if you call this program with command line input 2, a 02 value marble will replace this }0. This marble then falls down into the &0 device, another synchronizer, &n synchronizers hold marbles until all other corresponding &n's are filed as well. The marble then gets decremented, teleported and duplicated much like in the previously explained loop. The right copy then get checked for inequality with zero (>0) if it's not 0, it falls through. If it is 0, it gets pushed to the right and lands on !!, which terminates the board.

Okay, so far we have a loop that continuously counts down from 255 to 0 and lets another, similar loop (fed by the command line input) run once every time it hits 0. When this second loop has run n times (maximum being 256) the program terminates. So that's a maximum of 65536 runs of the loop. Not nearly enough to outlive the universe.

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

This should start looking familiar, the input gets decremented once, then this value loops around and get copied (note that the marble only gets decremented once, not on every run of the loop). It then gets checked for equality to 0 and if it's not zero lands on MB. This is a function in Marbelous, every file can contain several boards and each board is a function, every function has to be named by preceding the grid by :[name]. Every function except for the first function in the file, which has a standard name: MB. So this loop continuously calls the main board again with a value of n - 1 where n is teh value with which this instance of teh function was called.

So why n*512?

Well, the first loop runs in 4 ticks (and 256 times) and the second loop runs n times before the board terminates. This means the board runs for about n*4*256 ticks. The last loop (which does the recursive function calling) is compacter and runs in 2 ticks, which means it manages to call the function n*4*256/2 = n*512 times.

What are the symbols you didn't mention?

\/ is a trash bin, which removes marbles from the board, this makes sure discarted marbles don't interfere with other marbles that are looping a round and prevent the program from terminating.

Bonus

Since marbles that fall off the bottom of a marbelous board get output to STDOUT, this program prints a plethora of ASCII characters while it runs.

Answer 5

GolfScript (12 7 chars)

9,{\?}*

This computes and prints 8^7^6^5^4^3^2 ~= 10^10^10^10^183230. To print it (never mind the computation) in 10^1000 years ~= 10^1007.5 seconds, it needs to print about 10^(10^10^10^183230 - 10^3) digits per second.

Answer 6

Perl, 66 58 characters

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

The above is an implementation of the Ackermann–Péter function. I have no idea how large A(9,9) is but I am fairly certain it will take an astoundingly long time to evaluate.

Answer 7

MATLAB, 58 52 characters

We need at least one finite-precision arithmetic solution, hence:

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

x=ones(1,999);y=x;while any(y),y=mod(y+x,primes(7910));end

(with thanks to @DennisJaheruddin for knocking off 6 chars)

The number of cycles needed to complete is given by the product of the first 999 primes. Since the vast majority of these are well over 10, the time needed to realize convergence would be hundreds or thousands of orders of magnitude greater than the minimum time limit.

Answer 8

Mathematica, 25 19 bytes

This solution was posted before time functions were disqualified.

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

TimeUsed[] returns the seconds since the session started, and Mathematica uses arbitrary-precision types. There are some 10⁷ seconds in a year, so waiting 10¹⁰⁰⁰⁰ seconds should be enough.

Shorter/simpler(/valid) alternative:

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

Let's just count instead. We'll have to count a bit further, because we can do a quite a lot of increments in a second, but the higher limit doesn't actually cost characters.

Technically, in both solutions, I could use a much lower limit because the problem doesn't specify a minimum processor speed.

Answer 9

Python 3 - 49

This does something useful: calculates Pi to unprecedented accuracy using the Gregory-Leibniz infinite series.

Just in case you were wondering, this program loops 10**10**10**2.004302604952323 times.

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

Arbitrary precision: 78

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

Image source

The Terminal Breath

Due to the huge calculations taking place, 1e99**1e99 iterations takes just under 1e99**1e99 years. Now, (1e99**1e99)-1e1000 makes barely any difference. That means that this program will run on far longer than the death of our universe.

Rebirth

Now, scientists propose that in 10**10**56 years, the universe will be reborn due to quantum fluctuations or tunnelling. So if each universe is exactly the same, how many universe will my program live through?

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

Assuming that the universe will always live 1e10+1e1000 years and then take 10**10**56 years to 'reboot', my program will live through 1e9701 universes. This is assuming, of course, that unobtainium can live through the Big Bang.

Answer 10

Python 59 (works most of the time)

I couldn't resist

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

While its true that this could theoritically terminate in under a millisecond, the average runtime is well over 10^400 times the specified lifespan of the universe. Thanks to @BetaDecay, @undergroundmonorail, and @DaboRoss for getting it down a 17 characters or so.

Answer 11

J - 5 chars, I think

Note that all of the following is in arbitrary precision arithmetic, because the number 9 always has a little x beside it.

In seven characters, we have !^:!!9x, which is kinda like running

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

in arbitrary precision arithmetic. This is definitely over the limit because Synthetica said so, so we have an upper bound.

In six chars, we can also write ^/i.9x, which calculates every intermediate result of 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8. Wolfram|Alpha says 2^3^4^5^6^7^8 is approximately 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 6.65185, which probably also clears inspection.

We also have the five char !!!9x, which is just ((9!)!)!. W|A says it's 10 ^ 10 ^ 10 ^ 6.2695, which should still be big enough... That's like 1.6097e1859933-ish digits, which is decidedly larger than 3.154e1016, the number of nanoseconds in the universe, but I'm gonna admit I have no idea how one might figure out the real runtimes of these things.

The printing alone should take long enough to last longer than the universe, though, so it should be fine.

Answer 12

C, 63 56 chars

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

This is based on an idea by a guy named Wilhelm. My only contribution is condensing the code down to this short (and unreadable) piece.

Proving that it terminates is done by induction.

• If x is 0, it terminates immediately.
• If it terminates for x-1 and any y, it also terminates for x, this itself can be shown by induction.

Proving the induction step by induction:

• If y is 0 there is only one recursive call with x-1, which terminates by induction assumption.
• If f(x, y-1) terminates then f(x, y) also terminates because the innermost call of f is exactly f(x, y-1) and the outermost call terminates according to the induction hypthesis.

The expected running time is A(9,9) / 11837 seconds. This number has more digits than the number of quarks in the observable universe.

Answer 13

Matlab (10 8 chars)

1:9e1016

IMHO, most entries are trying too hard by computing large, complicated things. This code will simply initialize an array of 9x10¹⁰¹⁶ doubles counting up from 1, which takes 7.2x10^¹⁰¹⁷ bytes. On a modern CPU with a maximum memory bandwidth of 21 GB/s or 6.63x10^¹⁷ bytes/year, it will take at least 1.09x10¹⁰⁰⁰ years to even initialize the array, let alone try to print it since I didn't bother suppressing the output with a trailing semicolon. (;

---

old solution(s)

nan(3e508)

Alternatively

inf(3e508)

This code will simply create a square matrix of NaNs/infinities of size 3e508x3e508 = 9e1016 8-byte doubles or 7.2e1017 bytes.

Answer 14

Perl, 16 chars

/$_^/for'.*'x1e9

This builds a string repeating ".*" a billion times, then uses it as both the needle and the haystack in a regex match. This, in turn, causes the regex engine to attempt every possible partition of a string two billion characters long. According to this formula from Wikipedia, there are about 10³⁵²¹⁸ such partitions.

The above solution is 16 characters long, but only requires about 2Gb of memory, which means it can be run on a real computer. If we assume infinite memory and finite register size (which probably doesn’t make sense), it can be shortened to 15 characters while dramatically increasing the runtime:

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

(I haven’t tested it, but I think it could work with a 32-bit Perl built on a 64-bit machine with at least 6Gb of RAM.)

Notes:

• x is the string repeat operator.
• the for isn’t an actual loop; it is only used to save one character (compared to $_=".*"x1e9;/$_^/).
• the final ^ in the regex ensures that only the empty string can match; since regex quantifiers are greedy by default, this is the last thing the engine will try.
• benchmarks on my computer for values (1..13) suggest that the running time is actually O(exp(n)), which is even more than the O(exp(sqrt(n))) in the Wikipedia formula.

Answer 15

J (12)

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

What this comes down to in Python (assuming ! works):

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

EDIT:

Well, the program can take, at most, 2 × 10^-1858926 seconds per cycle, to complete within the required time. Tip: this won't even work for the first cycle, never mind the last one ;).

Also: this program might need more memory than there is entropy in the universe...

Answer 16

C# 217

I'm not much of a golfer, but I couldn't resist Ackerman's function. I also don't really know how to calculate the runtime, but it will definitely halt, and it will definitely run longer than this version.

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));}
}

Answer 17

First attempt at code golf but here goes.

VBA - 57 45

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

So X will go up by one if a 1 in 2^128 event occurs and reset if it does not occur. The code ends when this event happens 2^64+1 times in a row. I don't know how to begin calculating the time but I'm guessing it is huge.

EDIT: I worked out the math and the probability of this happening in each loop is 1 in 2^128^(1+2^64) which is about 20000 digits long. Assuming 1000000 loops/sec (ballpark out of thin air number) and 30000000 s/yr that's 3*10^13 cycles per year time 10^1000 years left is 3*10^1013 cycles, so this would likely last around 20 times the remaining time left in the universe. I'm glad my math backs up my intuition.

Answer 18

C, 30 characters

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

Assuming two's compliment signed overflow and 32-bit ints, this will run for about 2²³² function calls, which should be plenty of time for the universe to end.

Answer 19

R, 45 bytes

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

It's an old thread but I see no R answer, and we can't be having that!

The runtime for me was about 1s when x was 20, suggesting a runtime of 2^9979 seconds.

If you replace the zero with a one, then the output would be 2^x, but as it stands the output is zero whatever x was (avoids overflow problems).

Answer 20

GolfScript, 13 chars

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

This program just counts up from 0 to 10⁹⁹⁻¹ = 10^387420488. Assuming, optimistically, that the computer runs at 100 GHz and can execute each iteration of the program in a single cycle, the program will run for 10⁹⁹⁻¹² seconds, or about 3 × 10⁹⁹⁻²⁰ = 3 × 10^387420469 years.

To test the program, you can replace the 9 with a 2, which will make it stop at 10²²⁻¹ = 10³ = 1000. (Using a 3 instead of a 2 will make it stop at 10³³⁻¹ = 10²⁶, which, even with the optimistic assumptions above, it will not reach for at least a few million years.)

Answer 21

Autohotkey 37

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

Answer 22

Haskell, 23

main=interact$take$2^30

This program terminates after reading 1073741824 characters from stdin. If it's run without piping any data to stdin, you will have to type this number of characters on your keyboard. Assuming your keyboard has 105 keys, each rated for 100k mechanical cycles and programmed to generate non-dead keystrokes, autorepeat is off, and your keyboard socket allows 100 connection cycles, this gives the maximum number of keystrokes per computer uptime of 1050000000, which is not enough for the program to terminate.

Therefore, the program will only terminate when better hardware becomes available in terms of number of cycles, which is effectively never in this running universe. Maybe next time, when quality has higher priority than quantity. Until then, this program terminates in principle but not in practice.

Answer 23

~ATH, 56

In the fictional language ~ATH:

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

~ATH is an insufferable language to work with. Its logic is composed of nothing but infinite loops, or at best, loops of effectively interminable construction.

What many ~ATH coders do is import finite constructs and bind the loops to their lifespan. For instance the main loop here will terminate on the death of the universe, labeled U. That way you only have to wait billions of years for it to end instead of forever.

I apologize for the borderline loophole violations; I thought it was too relevant to pass up.

If anyone was actually amused by this, more details: (1), (2), (3), (4)

Answer 24

APL, 10

I don't think this is a valid answer (as it is non-deterministic), but anyway......

{?⍨1e9}⍣≡1

This program calculates a random permutation of 1e9 numbers (?⍨1e9) and repeats until two consecutive outputs are equal (⍣≡)

So, every time a permutation is calculated, it has a 1 in 1000000000! chance of terminating. And 1000000000! is at least 10¹⁰⁸.

The time it takes to calculate a permutation is rendered irrelevant by the massiveness of 1000000000!. But some testing show this is O(n) and extrapolating gives about 30 seconds.

However, my interpreter refuses to take inputs to the random function larger than 2³¹-1 (so I used 1e9), and generating permutations of 1000000000 numbers gave a workspace full error. However, conceptually it can be done with a ideal APL interpreter with infinite memory.

This leads us to the possibility of using 2⁶³-1 in place of 1e9 to bump the running time up to at least 10¹⁰²⁰, assuming a 64-bit architecture.

But wait, is architecture relevant in an ideal interpreter? Hell no so there is actually no upper bound on running time!!

Answer 25

Ruby(34)

The line ([0]*9).permutation.each{print} takes about 2.47 seconds for 9! prints on my machine, while the line ([0]*10).permutation.each{print} takes about 24.7 seconds for 10! prints, so I guess I can extrapolate here and calculate (24.7/10!)*470! seconds in years which is 6.87 * 10^1040, which should be the run time of:

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

Answer 26

JavaScript 68 62 chars

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

This uses the Ackermann-function which can be written as

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));
}

Its runtime time increases over exponentially and takes therefore very long to calculate. Even though it is not english here you can get an overview of its return values. According to the table ackermann(5,1) equals 2↑↑(65533)-3 which is, you know, very big.

Answer 27

Befunge '93 - 40 bytes

(20x2 program)

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

This program relies on random numbers to give it delay. Since Befunge interpreters are quite slow, this program should fit the bill. And if it doesn't, we can always expand it horizontally. Im not exactly sure how to go about calculating the expected running time of this program, but I know that each ? has a 50/50 chance of either starting over or changing its horizontal position by 1. There are 18 ?'s. I think it should be something along the lines of (18^2)!, which google calculator says is "Infinity"

EDIT: Whoops I did not notice the other Befunge answer, this is my first post here. Sorry.

Answer 28

Python 3, 191 Bytes

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)

First, f is a recursive factorial function and ultra slow. Then, there is 9*10⁹⁹⁹ powed with itself, which generates an OverflowError, but this doesn't happen on this Unobtanium computer. The For-Loop iterates 9E999! ^ (9E999^9E999)! times and it only goes to the next iteration, if 9E999!+1 random ints between 0 and 9E99*^i! are all 0 and in every iteration of the while-loop s gets set to (9E999^s)!. Uh, I forgot that the printing of s takes muuuuccchhhh time...
I know it's not the shortest soloution, but I think it's really effective. Can someone help me calculating the running time?

Answer 29

Javascript, 120 bytes

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)

Can be done with minimal memory (probably less than half a megabyte) but takes (probably) about 10^8,750 years to halt.

Repeatedly increments a little-endian base-9 BigInteger until it reaches 9^104-1.

Answer 30

Turing Machine But Way Worse, 167 bytes

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

Try it online!

Should run the 6-state 2-symbol Busy Beaver from the Wikipedia page.

As said in the Wikipedia page, it runs in \$7.412 \times 10^{36534}\$ steps. This is way more than the heat death, assuming it executes each command in more than or equal to a nanosecond.