{"id":5496,"date":"2026-05-13T00:48:15","date_gmt":"2026-05-13T04:48:15","guid":{"rendered":"https:\/\/ikriv.com\/blog\/?p=5496"},"modified":"2026-05-13T00:55:45","modified_gmt":"2026-05-13T04:55:45","slug":"whats-the-shortest-program-for-which-we-cant-tell-if-it-stops","status":"publish","type":"post","link":"https:\/\/ikriv.com\/blog\/?p=5496","title":{"rendered":"What’s the shortest program for which we can’t tell if it stops?"},"content":{"rendered":"

Here’s a 10-line Python program. Nobody on Earth currently knows whether it ever stops.<\/p>\n

\r\nf = lambda n: 3*n+1 if n%2 else n\/\/2\r\nstop = seed = 0\r\nwhile not stop:\r\n    fast = slow = seed = seed + 1\r\n    while True:\r\n        fast = f(f(fast))\r\n        slow = f(slow)\r\n        if fast == slow:\r\n            stop = fast not in (1,2,4)\r\n            break\r\n<\/pre>\n
The halting problem<\/a> is the question of whether, given a program, we can tell if it will eventually halt or run forever. Theoretically, there must exist programs for which we can’t tell whether they halt. But can we actually build such a program in practice? How short can we make it?<\/p>\n
How it works<\/h1>\n
The program uses the Collatz conjecture<\/a>, also known as the 3n+1 problem. Starting with some positive integer n, we build a sequence in which the next member is 3n+1 if n is odd, and n\/2 if n is even. Every starting value tried so far eventually leads to the “trivial” loop 1 \u2192 4 \u2192 2 \u2192 1 \u2192 … The open question is whether there exists a starting value whose sequence leads to a different loop (or escapes to infinity, but our program won’t catch that case).<\/p>\n
To detect a loop without remembering every value in the path, the program uses the “tortoise and hare<\/a>” algorithm: one pointer, fast<\/code>, advances 2 steps at a time, while the other, slow<\/code>, advances 1 step at a time. If they ever meet, we’ve found a loop.<\/p>\n
If that meeting point is none of 1, 2, or 4, it means we’ve detected a non-trivial loop, and the program halts. If no non-trivial loop exists, the program runs forever.<\/p>\n
Unbounded memory<\/h1>\n
It’s worth noting that unbounded memory, in this case the ability to work with arbitrarily large numbers, is essential for the halting problem. If a program runs on a computer with finite memory, we can always figure out whether it halts by running it on a computer with more memory and recording every state it reaches. Since there is only a finite number of states, we just wait for one to repeat. Repeating states means no halting. It’s the unbounded memory that makes the halting problem undecidable in general.<\/p>\n
Python is therefore an ideal language for the job, because its integers don’t have a fixed number of bits and can grow indefinitely. In practice, we will<\/em> eventually run out of memory, of course. But in principle, if we assume arbitrarily large numbers, no one knows whether this program halts.<\/p>\n
So if you ever see it stop, congratulations: you’ve just resolved one of the oldest open problems in mathematics.<\/p>\n","protected":false},"excerpt":{"rendered":"
Here’s a 10-line Python program. Nobody on Earth currently knows whether it ever stops. f = lambda n: 3*n+1 if n%2 else n\/\/2 stop = seed = 0 while not […]<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"Layout":"","footnotes":""},"categories":[26,5],"tags":[],"class_list":["entry","author-ikriv","post-5496","post","type-post","status-publish","format-standard","category-python","category-dev"],"_links":{"self":[{"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5496","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5496"}],"version-history":[{"count":4,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5496\/revisions"}],"predecessor-version":[{"id":5500,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5496\/revisions\/5500"}],"wp:attachment":[{"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5496"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5496"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5496"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}