8
\$\begingroup\$

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.

\$\endgroup\$
  • 8
    \$\begingroup\$ I mean that it should have an exactly 50% probability to halt on every run. \$\endgroup\$ – ike Jan 1 '14 at 12:41
  • 3
    \$\begingroup\$ But then it won't be Halt, Don't Halt, Halt, Don't Halt because with a 50% prob you get runs. \$\endgroup\$ – Paul Jan 1 '14 at 12:43
  • 5
    \$\begingroup\$ 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...) \$\endgroup\$ – Paul Jan 1 '14 at 12:44
  • 7
    \$\begingroup\$ Who keeps upvoting these poor questions? \$\endgroup\$ – Gareth Jan 2 '14 at 11:04
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Keith Randall Jan 3 '14 at 4:45

26 Answers 26

33
\$\begingroup\$

Perl

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

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

\$\endgroup\$
  • 10
    \$\begingroup\$ Schrodinger's halt \$\endgroup\$ – scrblnrd3 Jan 17 '14 at 17:08
13
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ @Jan Oops, sorry, fixed. (I'm answering from my phone right now so I can't test) \$\endgroup\$ – Doorknob Jan 1 '14 at 13:49
  • \$\begingroup\$ looks good now (I still like my answer better ;-) ) \$\endgroup\$ – John Dvorak Jan 1 '14 at 13:50
  • 1
    \$\begingroup\$ Doesn't work on ie8/ff3 (compatibility troll) \$\endgroup\$ – Tyzoid Jan 2 '14 at 4:08
  • \$\begingroup\$ @Tyzoid who uses FF3 anyways? And it does work in IE8. \$\endgroup\$ – John Dvorak Jan 2 '14 at 7:29
  • \$\begingroup\$ This doesn't fit the challenge anymore, because it is predictable. \$\endgroup\$ – The Guy with The Hat Jan 17 '14 at 17:59
13
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ +1 for maths. This would make a good "what is the behavior of this code" test problem. \$\endgroup\$ – primo Jan 2 '14 at 5:49
  • 1
    \$\begingroup\$ 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%. \$\endgroup\$ – user2357112 supports Monica Jan 2 '14 at 9:43
  • 1
    \$\begingroup\$ 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/… \$\endgroup\$ – ejrb Jan 2 '14 at 12:29
  • 2
    \$\begingroup\$ start with p=0.3078458 to get 50.00002% :) \$\endgroup\$ – ejrb Jan 2 '14 at 12:48
  • 2
    \$\begingroup\$ My bad. Probability is hard. \$\endgroup\$ – Keith Randall Jan 2 '14 at 17:04
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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)

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Geometry Dash 2.2 Editor Glitch - 2 objects

enter image description here

Explanation:

The random trigger randomly toggles (disables) Group ID 1 or 2 with a 50% chance.

The purple pad is on reverse mode (meaning that if the cube touches it, the cube moves backward, which goes to the left forever and ever.).

Since the purple pad has Group ID 2, it has a 50% chance of being disabled, which means that the cube can pass through it to the end of the level, which will halt.

How to reproduce this:

Purple pad is on reverse mode and has Group ID 1.

enter image description here

Inside the random trigger.

enter image description here

\$\endgroup\$
2
\$\begingroup\$

C

#include <unistd.h>
main() { while (getpid()&2); }
\$\endgroup\$
  • \$\begingroup\$ -1: Not Exactly 50% \$\endgroup\$ – recursion.ninja Jan 2 '14 at 22:09
  • \$\begingroup\$ It's exactly 50% on my operating system. It might not be on yours... \$\endgroup\$ – Pseudonym Jan 3 '14 at 4:27
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

INTERCAL, 59 bytes

DO %50 (1) NEXT
DO COME FROM COMING FROM
(1) PLEASE GIVE UP

Try it online!

COME FROM COMING FROM makes an endless loop, but there is a 50% chance to skip to the end of the program.

\$\endgroup\$
1
\$\begingroup\$

TI-Basic

:Lbl 1:If round(rand):Pause:Goto 1
\$\endgroup\$
  • 1
    \$\begingroup\$ The syntax for round( is round(value,# of decimal places), and the second argument defaults to 9. \$\endgroup\$ – lirtosiast Jun 8 '15 at 18:12
1
\$\begingroup\$

C

int main() {
    char i;
    while(i&1);
}
\$\endgroup\$
  • \$\begingroup\$ @JanDvorak Shhhhh, don't tell everyone! \$\endgroup\$ – meiamsome Jan 2 '14 at 7:22
  • \$\begingroup\$ 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). \$\endgroup\$ – Konrad Borowski Jan 2 '14 at 13:29
1
\$\begingroup\$

Python, 48

import random
a=random.randrange(2)
while a:pass
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

<><, 5 bytes and a beautiful 2x2 square

x;
><

x sends the instruction pointer in a random direction; If it sends left or right the IP will hit ; and terminate. If it goes up or down the IP will get stuck in the infinite >< loop, being sent back and forth between the two.

\$\endgroup\$
  • \$\begingroup\$ it's not called <>< tho, it's called ><> lol (unless there's one called <>< I haven't heard of) \$\endgroup\$ – Sagittarius Sep 11 at 17:17
  • \$\begingroup\$ also you can save 1 byte by removing the < (because the pointer wraps around); it won't be a 2x2 square anymore but it'll be nicely golfed c: \$\endgroup\$ – Sagittarius Sep 11 at 17:18
1
\$\begingroup\$

Java

import java.io.*;

public class HaltNoHalt {
    public static void main(String[] args) throws Exception {
        RandomAccessFile f = new RandomAccessFile("HaltNoHalt.java", "rw");
        f.seek(372);
        int b = f.read();
        f.seek(372);
        f.write(b ^ 1);
        Runtime.getRuntime().exec("javac HaltNoHalt.java");

        while ((args.length & 1) == 1);
    }
}

This self-modifies the code to toggle the == 1 to == 0 and back, every time it's run. Save the code with newlines only or the offset will be wrong.

The args.length is just to prevent compiler optimizations.

\$\endgroup\$
0
\$\begingroup\$

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];
    }
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

GTB

[@r;p;]

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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]
\$\endgroup\$
0
\$\begingroup\$

Java

import java.util.Random;

class Halt50 {
    public static void main(String[] args){
        if(new Random().nextInt(2)==0)for(;;);
    }
}
\$\endgroup\$
0
\$\begingroup\$

Math++

_($rand*2)+2>$
2>$
1
\$\endgroup\$
0
\$\begingroup\$

Python 2, 54 bytes

import time;H=[time.time()%2]
for h in H:H+=[h]*int(h)

Try it online!

Halting behaviour is dependent on current time.

\$\endgroup\$

Your Answer

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

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