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

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.
• 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

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

• I was tempted to create a [slowest-code] tag for this question. :P – Doorknob Aug 24 '14 at 22:08
• 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. – DavidO Aug 24 '14 at 22:16
• Your title should be a tshirt – user-2147482637 Aug 25 '14 at 2:54
• Nice question, but shouldn't it be popularity contest ? – IazertyuiopI Aug 25 '14 at 6:38
• – David Conrad Aug 25 '14 at 17:02

# 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 2x, we have to count up to 28 × 4,179,623,936 = 233,436,991,488. With one increment per clock cycle and my Core i7-3770 (3.9 GHz with turbo), this will take 233,436,991,488 ÷ 3,400,000,000 > 1010,065,537,393 seconds, which is over 1010,065,537,385 years.

• I don't think you can rely on finite resources, as the question states "Your computer has infinite memory/stack/recursion limit". – Greg Hewgill Aug 25 '14 at 1:10
• Infinite memory != infinite data types. If I have a terabyte of RAM, an unsigned 8-bit integer still only goes up to 255. – wchargin Aug 25 '14 at 1:13
• @GregHewgill: With unlimited resources, you can increase the maximum Java heap size to any arbitrary value, but it will always be finite. – Dennis Aug 25 '14 at 1:46
• @Dennis, but then just add a line every time thru the loop to double the heap size. It's a funny thing about infinities :-) – Carl Witthoft Aug 25 '14 at 13:19
• @CarlWitthoft: You can't do that from inside the program. – Dennis Aug 25 '14 at 13:33

# 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 101000 * 150,000.

EDIT: As noted in the comments, Fib(9007199254740992) is approximately 4.4092*101882393317509686, which is indeed large enough.

• Since fib(n) can be approximated by phi^n, we can use log((sqrt(5) + 1)/2)*9007199254740992 to calculate how many digits fib(9007199254740992) turns out it's about 1.8823933*10^15. – overactor Aug 25 '14 at 11:26
• @overactor, According to Wolfram Alpha, Fib(9007199254740992) (using continuous form with phi) is approximately 4.4092... * 10^1882393317509686. Calculation – Brian S Aug 25 '14 at 22:26
• growing stack does not reduce CPU speed... unless you take the limited memory address line width / unlimited address width into account (in which case the slowdown is still linear in address length assuming reasonable encoding) or even the physical limitations in memory storage and the speed of light (in which case the slowdown is cbrtic in address value assuming spatial storage; even DNA levels of data density eventually start adding up, even if you manage space-efficient random access) – John Dvorak Aug 29 '14 at 8:12
• @JamesKhoury No, the function you just wrote is equivalent to for(x=0;x!=++x;) and only iterates 9007199254740992 times. – Peter Olson Sep 1 '14 at 15:34
• @SylvainLeroux an architecture with infinite amounts of RAM would probably just interleave the heap and stack and have them both grow upwards. – John Dvorak Sep 2 '14 at 5:01

# 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.

• OverflowError: (34, 'Result too large') – apple16 Aug 25 '14 at 4:30
• @apple16 Maybe on your computer, but mine has an "infinite memory/stack/recursion limit". – xnor Aug 25 '14 at 4:46
• It's OK, guys. I ran it last universe and got ...82528057365719799011536835265979955007740933949599830498796942400000000009 (2.6*10^954242509 digits omitted to avoid black hole collapse). You should really upgrade to Unobtanium. – xnor Aug 25 '14 at 22:53
• Exponentiation is right-associative, so you can drop the parentheses. – user2357112 supports Monica Aug 26 '14 at 1:52
• It's worth noting that 9**9**9e9 is just as short and takes slightly more universe-lengths to compute, as well as looking a little nicer. – abarnert Aug 29 '14 at 19:31

## 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.

• But it will halt long before that with a "printer out of paper" message... – Floris Aug 26 '14 at 22:17
• @Floris who the hell uses physical media in these days? – John Dvorak Aug 29 '14 at 8:13
• @JanDvorak, I just assumed that Floris and the 7 people who upvoted him are from my grandad's generation, when all output was to continuous feed paper. – Peter Taylor Aug 29 '14 at 8:21
• @PeterTaylor - maybe not quite that old, but I am old enough to recall submitting "batch jobs" to "the computer" (in the days when there was no doubt, in a student population of 20k, which computer you meant), and collecting the printout the following day. You (and 7 others) correctly surmised this was an attempt at humor, not a serious critique of your excellent and ridiculously short script. – Floris Aug 29 '14 at 11:49

# Marbelous68 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.

• Great explanation, thanks! – Beta Decay Aug 25 '14 at 9:24
• Wow, this is a brilliant idea! The Marbelous language is so fun! – rubik Sep 1 '14 at 8:46
• +1 Just what I wanted to see. A crazier language than BrainFuck :) Is there a website with tutorial and more info about it? (The title link seem to have less doc than your answer) – Sylwester Sep 1 '14 at 22:06
• @Sylwester, I'm glad you like it, Marbelous is currently still in development but we expect to have it in a more stable condition in the near future, at which point tutorials, more extensive documentation, standard libraries and hopefully an online interpreter will follow. – overactor Sep 2 '14 at 9:33

# 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.

• +1 ... I was trying to find a language with a built-in Ackermann function, but failed to do so before my patience ran out. :D – Martin Ender Aug 24 '14 at 23:36
• $n?A($m-1,A($m,$n-1)):A($m-1,1) admits an easy 8-char saving by pushing in the ternary operator. – Peter Taylor Aug 25 '14 at 16:04 • I am pretty sure the number of digits in A(9,9) is larger than the volume of the observable universe measured in cubic Planck lengths. – kasperd Aug 28 '14 at 6:51 • @kasperd That's a pretty massive understatement. The volume of the observable universe is only on the order of 10^184 planck volumes. By comparison, there are something like 10^19700 digits in the number describing the number of digits in A(4,4), which in turn is incomprehensibly tiny compared to A(9,9). – user19057 Aug 28 '14 at 22:02 • @user19057 It sounds like calling Kasperd's claim a "massive understatement" is a massive understatement. :P – Nicu Stiurca Sep 2 '14 at 23:25 # 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. • +1 Took a while for me to see what you are doing there. Nice! – Fixed Point Aug 25 '14 at 1:17 • +1 CRT, isn't it? – flawr Aug 25 '14 at 8:08 • Nice, I think some chars can be saved like so: y=ones(1,999);while y*y',y=mod(y+1,primes(7910));end – Dennis Jaheruddin Aug 25 '14 at 9:47 • @DennisJaheruddin: Brilliant shortening. I'll update. – COTO Aug 25 '14 at 12:53 • Though it is not the same solution anymore, this should still be similar enough, and again a bit shorter: p=1:9e9;y=p;while+y*y',y=mod(y+1,p),end – Dennis Jaheruddin Aug 25 '14 at 14:48 ## 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 107 seconds in a year, so waiting 1010000 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. • Love it! This answer made me actually laugh out loud with a big smile on my face. – Todd Lehman Aug 24 '14 at 23:28 • Sorry, for creativity sake, I had to cut out time based solutions (like your first one). Please don't hate me. :) – kb_sou Aug 24 '14 at 23:39 • @kbsou Well, I've beaten it with my other one, so I don't really care. But otherwise disqualifying answers retrospectively for rule changes isn't cool though. ;) – Martin Ender Aug 24 '14 at 23:40 • Is Mathematica really so slow, that computing 9^9^9 takes more than 10^1000 years? I estimate that computing 9^9^9 on my 1.3GHz U7300 using bc would take less than 6 months. (Based on extrapolating the time to compute 9^200000 and 9^400000.) – kasperd Aug 27 '14 at 22:40 • @ArtOfCode Mathematica uses arbitrary-precision types so it will actually try to determine the correct value. – Martin Ender Aug 31 '14 at 20:32 # 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)])  # 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. • it terminates once it reaches the end of the range @Philipp. yes it terminates, eventually. – Malachi Aug 25 '14 at 13:17 • 1000**1000 is 1e3000, not 1e2000. – Cornstalks Aug 25 '14 at 13:56 • @Cornstalks Thanks, I didn't have a calculator good enough to find that so I made a guess based on the fact that 100**100=1E200. – Beta Decay Aug 25 '14 at 17:10 • @BetaDecay: I might suggest Wolfram|Alpha as an online calculator. If you haven't ever used it, it's pretty awesome! – Cornstalks Aug 25 '14 at 17:13 • @anyoneinterested Or 1000^1000 = (10^3)^1000 = (10*10*10)*(10*10*10)*...*(10*10*10) [1000 times] = 10^3000 – IazertyuiopI Aug 26 '14 at 5:37 # 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. • To get it down to 71 you can replace continue with pass – Beta Decay Aug 27 '14 at 15:44 • @BetaDecay Nice catch – KSab Aug 27 '14 at 18:21 • I think since the question asks for the expected running time, it's not a problem that this might terminate early. The larger issue is that it can't be proven to terminate at all. – user19057 Aug 28 '14 at 22:08 • @user19057 Assuming what KSab said, the expected running time is finite and the program terminates with 100% probability. Of course the random module actually uses a PRNG, which is cyclic, so most likely this will never terminate. – Jerome Baum Aug 31 '14 at 16:56 • I think you can cut off 3 characters by replacing 'pass' with '0'. – daboross Aug 31 '14 at 20:08 # 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. # 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. • (Ab)use the preprocessor and define m=main, r=return, and z=99999, then rewrite your program as, f(x,y){r x?f(x-1,y?f(x,y-1):1):y+1;}m(){f(z,z);} which will take an amazingly long time :-) – ChuckCottrill Aug 30 '14 at 0:15 • @ChuckCottrill If the rules allowed programs, which require specific preprocessor macros, and those did not count towards program length, then any task can be solved in one character. – kasperd Aug 30 '14 at 9:46 # 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 9x101016 doubles counting up from 1, which takes 7.2x10^1017 bytes. On a modern CPU with a maximum memory bandwidth of 21 GB/s or 6.63x10^17 bytes/year, it will take at least 1.09x101000 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. • What's that? 1016? That must be 9999! (Or did I misunderstand something?) – Mega Man Jul 17 '16 at 11:05 • @MegaMan The problem prompt asks for runtime lower bound of 10^1000 years. This being golf, I didn't want to be wasteful and compute too much longer than that, so I tried to get it to stop as soon after reaching the threshold as possible. :) – Nicu Stiurca Jul 18 '16 at 22:33 • ah, ok, didn't know this rule – Mega Man Jul 20 '16 at 17:15 # 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 1035218 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. # 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... • "might need more memory than there is entropy in the universe" - You can cut down on that with xrange() ;) – Stefan Majewsky Aug 25 '14 at 22:04 • Also, ! doesn't work in Python. You need import math and math.factorial(). – daviewales Aug 27 '14 at 1:04 # 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));} }  • You can save 10 bytes by renaming the ack function to a single-character name like a. – pppery Sep 2 '19 at 17:59 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. • I think that the last line should be While x=1, right? (otherwise its an infinite loop). Also, you can shave off 12 chars if you substitute Dim x As Double with x=0 (VBA doesn't require to declare variables unless you specify Option Explicit) – kb_sou Aug 29 '14 at 16:15 • I don't look at it as an infinite loop as it breaks when x overflows which is eventually. – Myles Horne Aug 29 '14 at 17:15 • It definitely doesn't work with while x=1 as this would generally prevent the loop from running. – Myles Horne Aug 29 '14 at 17:17 • If breaking the in this way loop doesn't meet the "no infinite loops" criteria the WHILE 1=1 could change to WHILE ISNUMERIC(X). – Myles Horne Aug 29 '14 at 17:31 # 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 2232 function calls, which should be plenty of time for the universe to end. • You'll run out of stack long before then, though. – Sparr Aug 30 '14 at 0:08 • @Sparr One of the rules is to assume infinite stack and heap size. – scragar Sep 26 '14 at 9:29 # GolfScript, 13 chars 0{).,9.?<}do  This program just counts up from 0 to 1099−1 = 10387420488. 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 1099−12 seconds, or about 3 × 1099−20 = 3 × 10387420469 years. To test the program, you can replace the 9 with a 2, which will make it stop at 1022−1 = 103 = 1000. (Using a 3 instead of a 2 will make it stop at 1033−1 = 1026, which, even with the optimistic assumptions above, it will not reach for at least a few million years.) # Autohotkey 37 loop { if (x+=1)>10^100000000 break }  # 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.

• What if you hot-swap keyboards as you go? – Thomas Aug 29 '14 at 9:55
• That's covered by the 100 connection cycles of the keyboard socket. – TheSpanishInquisition Aug 29 '14 at 11:52
• But the point of the problem is that the program does terminate, somewhere after the heat death of the universe. This program can't possibly ever terminate; once entropy gets high enough, you will never have another keyboard to plug in. – abarnert Aug 29 '14 at 19:40
• I am still not convinced. If you run the program remotely (or in a VM), then you aren't limited by the hardware capabilities of a single computer, and 1 billion strokes really isn't that much. Besides, the problem says the computer is made of unobtainium, and so the keyboard should also be, hence, it can handle 2^30 keystrokes... – Thomas Aug 30 '14 at 6:32

# ~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)

## 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 10108.

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 231-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 263-1 in place of 1e9 to bump the running time up to at least 101020, 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!!

# 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).

• Equivalent 38 byte version. – Robin Ryder Oct 27 '19 at 18:21
• I'm not sure yours is equivalent — it doesn't fork the calls in the same way, and indeed your TIO example runs for argument 9999 in under a second (I think a pair of brackets would fix that, though). – JDL Oct 28 '19 at 8:37
• My bad, I included an extra !. This is equivalent (and 37 bytes). You can also shave off another byte with 1e4 instead of 9999. – Robin Ryder Oct 28 '19 at 10:55

# 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}


# 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.

• This can benefit from some of the same optimisations as the earlier Perl Ackermann function implementation. – Peter Taylor Aug 26 '14 at 22:23
• I must have overlooked the perl solution. Thanks for pointing that out. – henje Aug 27 '14 at 7:57
• instead of n==0?X:Y, you can always do n?Y:X – Cyoce Oct 5 '16 at 5:04

# 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.

• Hey, don't worry about the other befubnge answer, or, or in general, using the same language as someone else. I mean, nobody is going to beat the mathlab one, so all other submissions are about fun. Mine was. – AndoDaan Aug 29 '14 at 18: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 108,750 years to halt.

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

## 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?

# 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!

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.