15
\$\begingroup\$

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

\$\endgroup\$
17
  • 9
    \$\begingroup\$ I mean that it should have an exactly 50% probability to halt on every run. \$\endgroup\$
    – ike
    Commented Jan 1, 2014 at 12:41
  • 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
    Commented Jan 1, 2014 at 12:44
  • 8
    \$\begingroup\$ Who keeps upvoting these poor questions? \$\endgroup\$
    – Gareth
    Commented Jan 2, 2014 at 11:04
  • 6
    \$\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\$ Commented Jan 3, 2014 at 4:45
  • 4
    \$\begingroup\$ I found it perfectly clear. Create a program that has a 50% chance of halting (or, equivalently a 50% chance of falling into an infinite loop), and you cannot know which will occur before every runtime. \$\endgroup\$
    – ejrb
    Commented Jan 3, 2014 at 9:25

42 Answers 42

45
\$\begingroup\$

Perl

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

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

\$\endgroup\$
1
  • 16
    \$\begingroup\$ Schrodinger's halt \$\endgroup\$
    – scrblnrd3
    Commented Jan 17, 2014 at 17:08
20
\$\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-\frac{p}{2})(1-\frac{p}{4})...\$ which is \$\frac{1}{2}\$. (Obligatory comment about floating point not being exact.)

\$\endgroup\$
5
  • \$\begingroup\$ +1 for maths. This would make a good "what is the behavior of this code" test problem. \$\endgroup\$
    – primo
    Commented Jan 2, 2014 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\$ Commented Jan 2, 2014 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
    Commented Jan 2, 2014 at 12:29
  • 3
    \$\begingroup\$ start with p=0.3078458 to get 50.00002% :) \$\endgroup\$
    – ejrb
    Commented Jan 2, 2014 at 12:48
  • 2
    \$\begingroup\$ My bad. Probability is hard. \$\endgroup\$ Commented Jan 2, 2014 at 17:04
12
\$\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\$
5
  • \$\begingroup\$ @Jan Oops, sorry, fixed. (I'm answering from my phone right now so I can't test) \$\endgroup\$
    – Doorknob
    Commented Jan 1, 2014 at 13:49
  • \$\begingroup\$ looks good now (I still like my answer better ;-) ) \$\endgroup\$ Commented Jan 1, 2014 at 13:50
  • 1
    \$\begingroup\$ Doesn't work on ie8/ff3 (compatibility troll) \$\endgroup\$
    – Tyzoid
    Commented Jan 2, 2014 at 4:08
  • \$\begingroup\$ @Tyzoid who uses FF3 anyways? And it does work in IE8. \$\endgroup\$ Commented Jan 2, 2014 at 7:29
  • 1
    \$\begingroup\$ This doesn't fit the challenge anymore, because it is predictable. \$\endgroup\$ Commented Jan 17, 2014 at 17:59
10
\$\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\$
3
  • \$\begingroup\$ Wow GD in code golf \$\endgroup\$ Commented Feb 9, 2023 at 22:12
  • \$\begingroup\$ @Jacob yes!! its a shame 2.2 still hasn't been released even though this leaked editor was usable, even in 2018 \$\endgroup\$
    – MilkyWay90
    Commented May 27, 2023 at 2:46
  • \$\begingroup\$ Well, with all of the leaks in the past week it looks like it might be out pretty soon. I wonder what possibilities there are for code-golf with all the new triggers \$\endgroup\$ Commented May 27, 2023 at 13:40
7
\$\begingroup\$

C

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

Random Brainfuck, 5 bytes

?[--]

Try it online!

Random BF extends BF's set of primitives with the ?, which generates a random byte and stores it in the current cell. That is, it generates an integer from 0-255. Given that there are an equal amount of odds and evens in that range, there is a 50% chance that the current cell is set to an even number after the first step.

The [--] endlessly decrements the current cell by two, as long as the current cell is not zero. Therefore, all even numbers will terminate. On the other hand, since parity is invariant mod 256, all odd numbers will loop forever, never quite reaching zero.

\$\endgroup\$
7
\$\begingroup\$

Lost, 2 bytes

%@

Try it online!

Although this is apparently a popcon, I figure the language itself is adequately interesting!

Lost is a fairly standard toroidal 2D language, with the caveat that the instruction pointer's initial position and direction are completely random. Additionally, in order to make it possible to write deterministic programs, there's a piece of global state called the safety which doesn't allow the program to halt by reaching @ until it's been turned off by %. So, this program has three cases:

  • 50% of the time, the IP starts moving left or right. It eventually reaches both instructions, and the program halts.
  • 25% of the time, the IP starts moving up or down on %. The safety is turned off, but it never reaches @, so the program does not halt.
  • 25% of the time, the IP starts moving up or down on @. The safety is never turned off, so the program does not halt.
\$\endgroup\$
2
  • \$\begingroup\$ Simply brillant! \$\endgroup\$
    – gildux
    Commented Jan 21, 2023 at 23:32
  • 1
    \$\begingroup\$ @gildux I'm pretty sure this is also the shortest program that can halt at all \$\endgroup\$ Commented Jan 22, 2023 at 5:14
6
\$\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
  • 1
    \$\begingroup\$ 21 bytes if you use syntax error. \$\endgroup\$
    – user100411
    Commented Sep 15, 2021 at 3:59
5
\$\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\$
5
\$\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\$
5
\$\begingroup\$

><>, 3 bytes

x;v

Try it online!

I... don't actually know ><>, but this should work on the same principle as the existing answers, just by "rerolling" vertical travel and looping if it goes left rather than down.

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

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\$
1
  • \$\begingroup\$ I think ?v@ also works. \$\endgroup\$
    – user101133
    Commented Jun 13, 2021 at 8:14
4
\$\begingroup\$

Poetic, 113 bytes

sometimes i,i think i get a choice
if its a thing i know i do affect,i bet i do win
i`m sorry if it breaks
o-h no

Try it online!

\$\endgroup\$
3
\$\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 product \$\Pi(1-p^{-2})\$ converges to \$\frac{6}{\pi^2}\$. This is because \$\zeta(2)=\Pi(\frac{1}{1-p^{-2}})\$ converges to \$\frac{\pi^2}{6}\$.

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

Pyt, 3 bytes

ɹ`ł

Try it online!

ɹ          get a random bit (0 or 1 with equal probability)
 `ł        loop while top of stack is truthy (1 is truthy; 0 is not)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I knew these answers would start flowing in once I revived it XD. Our golflangs and tarpits really didn't compare for these kinds of problems back then. \$\endgroup\$
    – AviFS
    Commented Jan 10, 2023 at 3:30
3
\$\begingroup\$

><>, 4 bytes

x;
>

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Oh, I did NOT see the existing ><> answer... whoops. \$\endgroup\$
    – hakr14
    Commented Apr 4, 2021 at 5:24
2
\$\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\$
2
  • \$\begingroup\$ it's not called <>< tho, it's called ><> lol (unless there's one called <>< I haven't heard of) \$\endgroup\$ Commented Sep 11, 2019 at 17:17
  • 1
    \$\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\$ Commented Sep 11, 2019 at 17:18
2
\$\begingroup\$

C

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

Scala

object HaltOrNot extends App {
  val x = scala.util.Random.nextLong
  while (((scala.util.Random.nextLong & 0xFFFFFFFFFFFFFFFEL) ^ x) != 0) {}
}

If x is odd positive or even negative, this program will never halt. If x is even positive or odd negative, this program will definitely halt... someday... after thousands of years... (e.g., if your machine can test 100 Mio loops per second it will terminate after 2924 years in expectation)

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

TI-Basic

:Lbl 1:If round(rand):Pause:Goto 1
\$\endgroup\$
1
  • 2
    \$\begingroup\$ The syntax for round( is round(value,# of decimal places), and the second argument defaults to 9. \$\endgroup\$
    – lirtosiast
    Commented Jun 8, 2015 at 18:12
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\$

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\$
1
\$\begingroup\$

Java

import java.util.Random;

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

JavaScript (Node.js), 24 bytes

It was incorrect, but somehow correcting it removed 2 bytes, thanks Roman Czyborra for pointing out it was incorrect

And another -2 because I forgot how to JS

if(Date.now()%2)for(;;);

Date.now() returns the amount of milliseconds since the Unix time epoch, which has a 50% chance to be even at the moment of running the program.

\$\endgroup\$
3
  • \$\begingroup\$ Isn't this missing a final ||for(;;); to prevent 100% halting? \$\endgroup\$ Commented Jan 22, 2023 at 1:38
  • \$\begingroup\$ I was stupid and didn't think of differences the REPL introduces... \$\endgroup\$
    – Leaf
    Commented Jan 24, 2023 at 15:15
  • \$\begingroup\$ Can we please stop feeling stupid? \$\endgroup\$ Commented Feb 10, 2023 at 4:42
1
\$\begingroup\$

Alice, 5 bytes

2U$v@

Try it online!

2          Pushes the number 2 on the stack
 U         Pops 2, pushes a random number in the range [0,2) on the stack
  $        Pops the random number, if 0 skip the next instruction
   v       Now moves vertically forever
    @      Halt
\$\endgroup\$
1
\$\begingroup\$

Fortran (GFortran), 19 bytes

1 if(i>0)goto 1
end

Try it online!. Since the lazy programmer did not initialise i, it is a random 32 bit integer, populated from whatever bits were floating around in that memory space before.

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

Javascript

JS has these Object URL things, which are generated when you create a file. The hex is all meaningless nonsense, but not in this case! Therefore, something like this works:

var blob = URL.createObjectURL(new Blob([""]))
// The blob looks something like "blob:null/01234567-1234-1234-1234-0123456789ab" and is hex, which can be exploited, really, any character works!
while (TextEncoder && new TextEncoder().encode(blob)[10] > 56) {
// Forever!
}
\$\endgroup\$
1
\$\begingroup\$

Python, 19 bytes

while id(1)>>17&1:1

Run online

This gets the address of the constant 1 in memory, and gets the 17th bit from the right. It then loops forever if the bit is 1.

I can't use a later bit to save a byte, because those bits seem to be constant between runs. The last bits are always 0011110000.

Some debug code:

print(bin(id(1)))
print(bin(id(1)>>17))
print(id(1)>>17&1)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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