Halt with 50% non-Halting

Question

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.

Answer 1

Perl

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

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

Answer 2

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

Answer 3

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;

Answer 4

Geometry Dash 2.2 Editor Glitch - 2 objects

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.

Inside the random trigger.

Answer 5

C

#include <unistd.h>
main() { while (getpid()&2); }

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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

Answer 11

GolfScript

2rand{.}do

I know this isn't a code-golf 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.

Answer 12

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.

Answer 13

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)

Answer 14

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!

Answer 15

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}\$.

Answer 16

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)

Answer 17

><>, 4 bytes

x;
>

Try it online!

Answer 18

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

Answer 19

C

int main() {
    char i;
    while(i&1);
}

Answer 20

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)

Answer 21

TI-Basic

:Lbl 1:If round(rand):Pause:Goto 1

Answer 22

Python, 48

import random
a=random.randrange(2)
while a:pass

Answer 23

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.

Answer 24

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.

Answer 25

Java

import java.util.Random;

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

Answer 26

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.

Answer 27

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

Answer 28

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.

Answer 29

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

Answer 30

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)