Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

share|improve this question
28  
I was tempted to create a [slowest-code] tag for this question. :P –  Doorknob 冰 Aug 24 at 22:08
3  
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 at 22:16
38  
Your title should be a tshirt –  user1938107 Aug 25 at 2:54
4  
Nice question, but shouldn't it be popularity contest ? –  IazertyuiopI Aug 25 at 6:38
9  
I think Isaac Asimov wrote a story about this. –  David Conrad Aug 25 at 17:02

31 Answers 31

up vote 23 down vote accepted

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.

share|improve this answer
11  
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 at 1:10
1  
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 at 1:13
3  
@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 at 1:46
1  
@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 at 13:19
7  
@CarlWitthoft: You can't do that from inside the program. –  Dennis Aug 25 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.

share|improve this answer
9  
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 at 11:26
9  
@overactor, According to Wolfram Alpha, Fib(9007199254740992) (using continuous form with phi) is approximately 4.4092... * 10^1882393317509686. Calculation –  Brian S Aug 25 at 22:26
1  
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) –  Jan Dvorak Aug 29 at 8:12
1  
@JamesKhoury No, the function you just wrote is equivalent to for(x=0;x!=++x;) and only iterates 9007199254740992 times. –  Peter Olson Sep 1 at 15:34
1  
@SylvainLeroux an architecture with infinite amounts of RAM would probably just interleave the heap and stack and have them both grow upwards. –  Jan Dvorak Sep 2 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.

share|improve this answer
4  
OverflowError: (34, 'Result too large') –  apple16 Aug 25 at 4:30
80  
@apple16 Maybe on your computer, but mine has an "infinite memory/stack/recursion limit". –  xnor Aug 25 at 4:46
44  
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 at 22:53
10  
Exponentiation is right-associative, so you can drop the parentheses. –  user2357112 Aug 26 at 1:52
4  
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 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.

share|improve this answer
14  
But it will halt long before that with a "printer out of paper" message... –  Floris Aug 26 at 22:17
1  
@Floris who the hell uses physical media in these days? –  Jan Dvorak Aug 29 at 8:13
2  
@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 at 8:21
2  
@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 at 11:49

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.

share|improve this answer
2  
Great explanation, thanks! –  Beta Decay Aug 25 at 9:24
2  
Wow, this is a brilliant idea! The Marbelous language is so fun! –  rubik Sep 1 at 8:46
1  
+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 at 22:06
1  
@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 at 9:33

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.

share|improve this answer
    
Love it! This answer made me actually laugh out loud with a big smile on my face. –  Todd Lehman Aug 24 at 23:28
1  
Sorry, for creativity sake, I had to cut out time based solutions (like your first one). Please don't hate me. :) –  kbsou Aug 24 at 23:39
5  
@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 Büttner Aug 24 at 23:40
1  
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 at 22:40
2  
@ArtOfCode Mathematica uses arbitrary-precision types so it will actually try to determine the correct value. –  Martin Büttner Aug 31 at 20:32

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.

share|improve this answer
    
+1 Took a while for me to see what you are doing there. Nice! –  Fixed Point Aug 25 at 1:17
    
+1 CRT, isn't it? –  flawr Aug 25 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 at 9:47
    
@DennisJaheruddin: Brilliant shortening. I'll update. –  COTO Aug 25 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 at 14:48

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.

share|improve this answer
4  
+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 Büttner Aug 24 at 23:36
3  
$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 at 16:04
2  
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 at 6:51
4  
@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 at 22:02
2  
@user19057 It sounds like calling Kasperd's claim a "massive understatement" is a massive understatement. :P –  SchighSchagh Sep 2 at 23:25

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.

share|improve this answer
    
But does it terminate? –  Philipp Aug 25 at 10:15
3  
it terminates once it reaches the end of the range @Philipp. yes it terminates, eventually. –  Malachi Aug 25 at 13:17
1  
1000**1000 is 1e3000, not 1e2000. –  Cornstalks Aug 25 at 13:56
1  
@BetaDecay: I might suggest Wolfram|Alpha as an online calculator. If you haven't ever used it, it's pretty awesome! –  Cornstalks Aug 25 at 17:13
2  
@anyoneinterested Or 1000^1000 = (10^3)^1000 = (10*10*10)*(10*10*10)*...*(10*10*10) [1000 times] = 10^3000 –  IazertyuiopI Aug 26 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.

share|improve this answer
    
To get it down to 71 you can replace continue with pass –  Beta Decay Aug 27 at 15:44
    
@BetaDecay Nice catch –  KSab Aug 27 at 18:21
2  
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 at 22:08
2  
@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 at 16:56
1  
I think you can cut off 3 characters by replacing 'pass' with '0'. –  DaboRoss Aug 31 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.

share|improve this answer

Not the shortest, but perhaps a novel way of creating a delay...

void main(void)
{
    int i = 0;
    int j = 0;
    while(j < (INT_MAX - 1))
    {
        if (i != 0)
        {
            j++;
            i = 0;
        }
    }
}

Counts the number of times i is not zero. i appears to never change, but as Google discovered DRAM is randomly corrupted by cosmic rays and other random events. The rate of corruption will be rather low since we are only looking at one int (4 bytes on an i7 style CPU). I'm going to assume that the program itself is somehow protected from corruption since it must run for such a long time.

share|improve this answer
4  
Shouldn't cosmic rays stop corrupting DRAM before the heat death of the universe? –  overactor Aug 26 at 9:48
    
Even after heat death there will be random corruptions, it's just that they will get further and further apart (i.e. less and less probable). –  MoJo Aug 26 at 14:24
5  
If they get further and further apart, it is quite possible that the total number is finite even over an infinite period of time. Besides, Unobtanium is rather good at shielding comic rays. –  MSalters Aug 26 at 14:42
4  
Any sane compiler will compile this to an infinite loop with no i or j in it. Of course you could still talk about cosmic rays flipping the program counter register bits or something, but that's rather outside the scope of what the program does, rather what happens to the machine. –  R.. Aug 27 at 3:49
9  
Just disable optimization. It's not like we are trying to get this done on a deadline. –  MoJo Aug 27 at 7:41

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.

share|improve this answer
    
(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 at 0:15
5  
@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 at 9:46

Befunge 93 - 80x25

Not a serious contender or submission (when do I ever?). I just liked the idea of it. All the little guy (the pointer) has to do is stay the path into the spiral 'til the @ terminating instruction. Unfortunately ? makes him jittery:

v@v<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
v#?############################################################################^
v# <?? ???????????????????????????????????????????????????????????????????? ??#^
v#?#?#^####################################################################^#?#^
v#?# <?? ???????????????????????????????????????????????????????????????? ??> #^
v#?#?#?#^################################################################^#?#?#^
v#?#?# <?? ???????????????????????????????????????????????????????????? ??> #?#^
v#?#?#?#?#^############################################################^#?#?#?#^
v#?#?#?# <?? ???????????????????????????????????????????????????????? ??> #?#?#^
v#?#?#?#?#?#^########################################################^#?#?#?#?#^
v#?#?#?#?# <??????????????????????????????????????????????????????????> #?#?#?#^
v#?#?#?#?#?#?########################################################?#?#?#?#?#^
v#?#?#?#?# <???????????????????????????????????????????????????????@#?#?#?#?#?#^
v#?#?#?#?#?#v########################################################?#?#?#?#?#^
v#?#?#?# <?? ?????????????????????????????????????????????????????????> #?#?#?#^
v#?#?#?#?#v##########################################################v#?#?#?#?#^
v#?#?# <?? ?????????????????????????????????????????????????????????? ??> #?#?#^
v#?#?#?#v##############################################################v#?#?#?#^
v#?# <?? ?????????????????????????????????????????????????????????????? ??> #?#^
v#?#?#v##################################################################v#?#?#^
v# <?? ?????????????????????????????????????????????????????????????????? ??> #^
v#?#v######################################################################v#?#^
v#?? ?????????????????????????????????????????????????????????????????????? ??#^
v##############################################################################^
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>^

Those 'wall' wont help him either, they keep people out, but bump into one from the inside... and. you're out again. So time wise, it's a probability here, round about 750 ? (randomly directs the pointer up, down, left or right) in the maze that each have one good direction, 2 bad (into a wall) and one neutral (a simple step back) will make it about a 1 in 3^750 odds that he gets to the center each time he attempts it. Anyway...

It's easier to watch it than explain it, so: Copy and paste it to Here.

share|improve this answer

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.

share|improve this answer

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.
share|improve this answer

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

share|improve this answer
3  
"might need more memory than there is entropy in the universe" - You can cut down on that with xrange() ;) –  Stefan Majewsky Aug 25 at 22:04
1  
Also, ! doesn't work in Python. You need import math and math.factorial(). –  daviewales Aug 27 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));}
}
share|improve this answer

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.

share|improve this answer
    
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) –  kbsou Aug 29 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 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 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 at 17:31

C, with the right compiler, 18 characters:

main(){INT_MAX+1;}

Signed integer overflow is undefined behavior. The C standard explicitly says this means the compiler can do anything it wants in this case. So, assuming a multiverse, among all of the universes where the C language exists, there must be one with a C compiler that generates code that immediately destroys the universe and then wraps around to INT_MIN. So, in that universe, this program outlives the rest of the universe.

share|improve this answer
    
What's the right compiler? –  Beta Decay Aug 29 at 19:53
1  
+1 for the most lateral thinking on the page. And there's already a ridiculous amount of it here. –  COTO Aug 30 at 19:23

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

share|improve this answer

Autohotkey 37

loop {
if (x+=1)>10^100000000
break
}
share|improve this answer

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.

share|improve this answer
    
What if you hot-swap keyboards as you go? –  Thomas Aug 29 at 9:55
    
That's covered by the 100 connection cycles of the keyboard socket. –  TheSpanishInquisition Aug 29 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 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 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)

share|improve this answer

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}
share|improve this answer

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.

share|improve this answer
2  
This can benefit from some of the same optimisations as the earlier Perl Ackermann function implementation. –  Peter Taylor Aug 26 at 22:23
    
I must have overlooked the perl solution. Thanks for pointing that out. –  henje Aug 27 at 7:57

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.

share|improve this answer
    
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 at 18:29

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.

share|improve this answer
    
You'll run out of stack long before then, though. –  Sparr Aug 30 at 0:08
    
@Sparr One of the rules is to assume infinite stack and heap size. –  scragar Sep 26 at 9:29

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

share|improve this answer

C 59 chars, x64 GCC only, compile with -O0 or it won't work.

Counting to int32 takes about a minute. Therefore we may estimate 2^48 minutes for the inner loop and therefore 128^(2^48) for the outer.

main(){for(__int128 i=0;++i!=0;)for(__int128 j=0;++j!=0;);}

EDIT: Not long enough. My math skills proved hazy.

share|improve this answer
2  
Since this is code golf, can you post the character count? –  Beta Decay Aug 25 at 16:35
1  
No, the outer loop takes 2^(48+128) minutes. Blink of an eye, really. Just 10^53 years. About 10^5000 years shorter than necessary. –  MSalters Aug 26 at 14:46
    
This program takes infinite time. ++i is never equal to zero since i has signed integer type and starts at 0. Changing it to unsigned __int128 would make it terminate. –  R.. Aug 27 at 3:50
    
This won't take you past the end of the universe unless you use really big numbers –  Beta Decay Aug 27 at 9:11
    
R..: Had you tried it with -O0 you would find otherwise. –  Joshua Aug 27 at 15:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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