logoalt Hacker News

7373737373 • 07/31/2025 • 4 replies • view on HN

Interesting new contender for simplest to state unsolved problem: The Antihydra

Does this program halt?

  a = 8
  b = 0
  while b != -1:
      if a % 2 == 0:
          b += 2
      else:
          b -= 1
      a += a//2
(// being integer division, equivalently a binary shift one to the right: >> 1)

https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html

https://bbchallenge.org/antihydra

Replies

tombert • 07/31/2025

Interesting, I hadn't heard this one.

I should see if I can model this in Isabelle or something and see what happens.

➕ show 1 reply
gowld • 08/01/2025

Is that also the simplest unsolved state problem?

ygritte • 08/01/2025

How does overflow behave?

➕ show 1 reply
fragmede • 08/01/2025

Fwiw, ChatGPT is able to say that it doesn't. I wonder what other classes of programs it's able to state if it halts?

➕ show 5 replies