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.

Create a program that halts exactly 50% of the time. Be original. Highest voted question wins. By exactly I mean that on each run there is a 50% chance of it halting.

share|improve this question
8  
I mean that it should have an exactly 50% probability to halt on every run. –  ike Jan 1 at 12:41
3  
But then it won't be Halt, Don't Halt, Halt, Don't Halt because with a 50% prob you get runs. –  Paul Jan 1 at 12:43
5  
If the program doesn't halt, does that mean it runs forever? It'll sure as hell halt when I turn the PC off. (Unless it is NSA code, then who knows...) –  Paul Jan 1 at 12:44
5  
Who keeps upvoting these poor questions? –  Gareth Jan 2 at 11:04
4  
This is a fine question. Only those who don't understand probability are confused by it. The original title was perhaps a bit misleading, but no worse than the New York Times. –  Keith Randall Jan 3 at 4:45
show 12 more comments

21 Answers

up vote 23 down vote accepted

Perl

fork || do {sleep(1) while(1)}

Each time you run this program, it halts and doesn't halt.

share|improve this answer
5  
Schrodinger's halt –  scrblnrd3 Jan 17 at 17:08
add comment

JavaScript

Alternatives halting and not halting. (halts on first run, doesn't halt on second, ...)

var h = localStorage.halt;
while (h) localStorage.halt = false;
localStorage.halt = true;
share|improve this answer
    
@Jan Oops, sorry, fixed. (I'm answering from my phone right now so I can't test) –  Doorknob Jan 1 at 13:49
    
looks good now (I still like my answer better ;-) ) –  Jan Dvorak Jan 1 at 13:50
1  
Doesn't work on ie8/ff3 (compatibility troll) –  Tyzoid Jan 2 at 4:08
    
@Tyzoid who uses FF3 anyways? And it does work in IE8. –  Jan Dvorak Jan 2 at 7:29
    
This doesn't fit the challenge anymore, because it is predictable. –  The Guy with The Hat Jan 17 at 17:59
add comment

Python

import random
p=.3078458
while random.random()>=p:p/=2

Each time around the loop it breaks with exponentially decreasing probability. The chance of never breaking is the product (1-p)(1-p/2)(1-p/4)... which is ~ 1/2. (Obligatory comment about floating point not being exact.)

share|improve this answer
1  
Doesn't work. You can't add up the probabilities like that; the actual probability of halting is 1-3/4*7/8*15/16..., which works out to about 42%. –  user2357112 Jan 2 at 9:43
1  
nice but the comment above is right: the probability of not halting is P(not halting on first)*P(not halting on second)*P(not on third)*... which tends to ~58%. See here for exact: wolframalpha.com/input/… –  ejrb Jan 2 at 12:29
2  
start with p=0.3078458 to get 50.00002% :) –  ejrb Jan 2 at 12:48
2  
My bad. Probability is hard. –  Keith Randall Jan 2 at 17:04
2  
+1 for the creative approach! –  awashburn Jan 2 at 22:08
show 1 more comment

Ruby

n = 2*rand(1...49)+1; divisors = (1...100).select{|x|n % x == 0}.count until divisors == 2
print n

There are exactly 24 odd primes between 0..100, the largest being 97. This algorithm chooses a random odd number within the range and repeats until it finds a prime:

This particular implementation has two bugs:

  • an exclusive range is used, meaning that 99 is never tested, meaning there are only 48 possible values for n, of which 24 are primes.
  • while n was meant to be redrawn at each iteration, only the primality testing is executed in the loop. If at first it doesn't succeed, it will try again - but with the same number.
share|improve this answer
add comment

BASH

#!/bin/bash
set -e
sed -i 's/true\;/false\;/' $0
while false; do echo -n ''; done;
sed -i 's/false\;/true\;/' $0

Just a fun self-modifying script.

Note: the empty quoted string on echo -n '' are just for clarity. They can be removed without loss of functionality.

share|improve this answer
add comment

C

#include <unistd.h>
main() { while (getpid()&2); }
share|improve this answer
    
-1: Not Exactly 50% –  awashburn Jan 2 at 22:09
    
It's exactly 50% on my operating system. It might not be on yours... –  Pseudonym Jan 3 at 4:27
add comment

GolfScript

2rand{.}do

I know this isn't a challenge, but I golfed it anyway. :)


Alternatively, here's a GolfScript implementation of Keith Randall's solution:

2{2*.rand}do

In theory, this will have an exactly 1/4 + 1/8 + 1/16 + ... = 1/2 probability of halting. In practice, though, it will always eventually run out of memory and halt, because the denominator keeps getting longer and longer.

share|improve this answer
add comment

TI-Basic

:Lbl 1:If round(rand):Pause:Goto 1
share|improve this answer
add comment

C

int main() {
    char i;
    while(i&1);
}
share|improve this answer
    
@JanDvorak Shhhhh, don't tell everyone! –  meiamsome Jan 2 at 7:22
    
This abuses undefined behavior that compilers already break to optimize the code. Therefore, for this to have any chances of working, you cannot optimize this code (not that this will work even then, because in main, the registers are initialized to 0 for security reasons). –  xfix Jan 2 at 13:29
add comment

Perl

BEGIN {
    # Do the following block 50% of time.
    if (int rand 2) {
        # Create a function that doubles values.
        *double = sub {
            2 * shift;
        };
    }
}
double / 3 while 1; # Calculates double divided using /

Not code golf, so I could avoid unreadable code (because what it does is more important). It randomly declares a function during compilation phase. If it gets declared, double gets regular expression as an argument. If it doesn't get declared, double is a bareword, and Perl divides it by 3 endlessly. This abuses Perl's bareword parsing, in order to get parser parse the same code two different ways.

share|improve this answer
add comment

I felt like golfing this one:

Befunge - 5 chars

?><
@

(I'm not sure whether this actually works as I don't have a befunge compiler on me)

share|improve this answer
add comment

Exactly 50% of the time?

OBJ-C

- (void)applicationDidFinishLaunching:(NSNotification*)aNotification {
    BOOL haltedLastRun = [(NSNumber*)[[NSUserDefaults standardUserDefaults] objectForKey:@"halted"] boolValue];
    if (!haltedLastRun) {
        [[NSUserDefaults standardUserDefaults] setObject:[NSNumber numberWithBool:YES] forKey:@"halted"];
        [[NSApplication sharedApplication] terminate:nil];
    }
}
share|improve this answer
add comment

Haskell

Runs for two intervals, each one 1 second long (chosen because 1 second is the SI unit for time). Halts inside 50% of the intervals. So 50% of the running seconds it will not halt, the other 50% it will. Works in GHC only.

import Control.Concurrent (threadDelay)
main = threadDelay 1990000
share|improve this answer
add comment

Shell Script

this script will clobber .md5sum files in the current and child directories.

#!/bin/sh
echo *.md5sum|xargs -n1|head -n1|xargs test -e && exec rm *.md5sum
while ! find . -name '*.md5sum' -print0 |xargs -0r grep 00000000000000
do {
    find . -type f -print|sed -e 's!^\(.*\)$!md5sum "\1" > "\1".md5sum!e'
}
done
share|improve this answer
add comment

Python


import random
try:
        a=1/random.randint(0,1)
        print 'not halted..'
except:
        print 'halt....... '

share|improve this answer
1  
except this won't actually halt....... . –  Jan Dvorak Jan 2 at 7:24
add comment

Python, 48

import random
a=random.randrange(2)
while a:pass
share|improve this answer
add comment

GTB

[@r;p;]

I know this isn't code-golf but I decided to golf it anyway.

share|improve this answer
add comment

C++

#include <fstream>
main () {
    int c;
    std::fstream fs;
    fs.open ("myfile.txt", std::fstream::in);
    fs>>c;
    fs.close ();
    fs.open ("myfile.txt", std::fstream::out);
    fs<<c+1;
    fs.close ();
    while (c%2);
    return 0;
}

Each run will halt iff the run before didn't.

share|improve this answer
add comment

Somewhat obfuscated solution:

Haskell

import Control.Monad
import Control.Monad.Random         -- package MonadRandom
import Control.Monad.Trans.Maybe
import Data.Numbers.Primes          -- package primes

-- | Continue the computation with a given probability.
contWithProb :: (MonadRandom m, MonadPlus m) => Double -> m ()
contWithProb x = getRandomR (0, 1) >>= guard . (<= x)

loop :: MonadRandom m => MaybeT m ()
loop = contWithProb (pi^2/12) >> mapM_ (contWithProb . f) primes
  where
    f p = 1 - (fromIntegral p)^^(-2)

main = evalRandIO . runMaybeT $ loop

Python

The same solution expressed in Python:

import itertools as it
import random as rnd
from math import pi

# An infinite prime number generator
# Copied from http://stackoverflow.com/a/3796442/1333025
def primes():
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

def contWithProb(p):
    if rnd.random() >= p:
        raise Exception()

if __name__ == "__main__":
    rnd.seed()
    contWithProb(pi**2 / 12)
    for p in primes():
        contWithProb(1 - p**(-2))

Explanation

This solution makes use of the fact that the infinite produt Π(1-p^(-2)) converges to 6/π^2. This is because ζ(2)=Π (1/(1-p^(-2))) converges to π^2/6.

share|improve this answer
add comment

Windows Command Script

This script will append code to itself which ultimately alternates 'x' on each run.

call :last
if %x%==1 (
    echo>>%0 set x=0
    exit /b 0
) else (
    echo>>%0 set x=1
)
:nohalt
goto :nohalt
:last
set x=1
[newline here]
share|improve this answer
add comment

Java

import java.util.Random;

class Halt50 {
    public static void main(String[] args){
        if(new Random().nextInt(2)==0)for(;;);
    }
}
share|improve this answer
add comment

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.