# Halt with 50% non-Halting

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.

• I mean that it should have an exactly 50% probability to halt on every run. – ike Jan 1 '14 at 12:41
• 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 '14 at 12:43
• 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 '14 at 12:44
• Who keeps upvoting these poor questions? – Gareth Jan 2 '14 at 11:04
• 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 '14 at 4:45

### Perl

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


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

• Schrodinger's halt – scrblnrd3 Jan 17 '14 at 17:08

## 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.) • +1 for maths. This would make a good "what is the behavior of this code" test problem. – primo Jan 2 '14 at 5:49 • 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 supports Monica Jan 2 '14 at 9:43 • 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 '14 at 12:29 • start with p=0.3078458 to get 50.00002% :) – ejrb Jan 2 '14 at 12:48 • My bad. Probability is hard. – Keith Randall Jan 2 '14 at 17:04 # 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;  • @Jan Oops, sorry, fixed. (I'm answering from my phone right now so I can't test) – Doorknob Jan 1 '14 at 13:49 • looks good now (I still like my answer better ;-) ) – John Dvorak Jan 1 '14 at 13:50 • Doesn't work on ie8/ff3 (compatibility troll) – Tyzoid Jan 2 '14 at 4:08 • @Tyzoid who uses FF3 anyways? And it does work in IE8. – John Dvorak Jan 2 '14 at 7:29 • This doesn't fit the challenge anymore, because it is predictable. – The Guy with The Hat Jan 17 '14 at 17:59 # 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. ## 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. # 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. 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) # 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. # C #include <unistd.h> main() { while (getpid()&2); }  • -1: Not Exactly 50% – recursion.ninja Jan 2 '14 at 22:09 • It's exactly 50% on my operating system. It might not be on yours... – Pseudonym Jan 3 '14 at 4:27 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}\$$. # 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. # ><>, 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. • it's not called <>< tho, it's called ><> lol (unless there's one called <>< I haven't heard of) – Sagittarius Sep 11 '19 at 17:17 • 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: – Sagittarius Sep 11 '19 at 17:18 # C int main() { char i; while(i&1); }  • @JanDvorak Shhhhh, don't tell everyone! – meiamsome Jan 2 '14 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). – Konrad Borowski Jan 2 '14 at 13:29 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) # 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 im sorry if it breaks o-h no  Try it online! ## TI-Basic :Lbl 1:If round(rand):Pause:Goto 1  • The syntax for round( is round(value,# of decimal places), and the second argument defaults to 9. – lirtosiast Jun 8 '15 at 18:12 ## Python, 48 import random a=random.randrange(2) while a:pass  # 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. # 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. # Java import java.util.Random; class Halt50 { public static void main(String[] args){ if(new Random().nextInt(2)==0)for(;;); } }  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]; } }  # 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  ## 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  ## GTB [@r;p;]  I know this isn't code-golf but I decided to golf it anyway. # 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. ## 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]  # Math++ _($rand*2)+2>$2>$
1


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