Someone is *WRONG* on the Internet!

Oh no, someone is *wrong* on the internet again!

I was quietly browsing Wikipedia the other day when I came across this small piece of code in the Termination analysis page:

void f(int n) {
   while (n > 1)
      if (n % 2 == 0)
          n = n / 2;
      else
          n = 3 * n + 1;
}

Seems innocuous enough, right? It’s a little implementation¹ of the Collatz conjecture.

The *issue* arises when I read the description:

As of 2021, it is still unknown whether this C-program terminates for every input

That can’t be right! How come such a simple program can’t be proven to terminate?! What a tragedy for computer scientists all around the world! Surely a 32 bit int is small enough to even brute force a solution here, no?

At first I thought “the problem space must be huge then, right?” but after a couple minutes thinking, it doesn’t seem to be the case - the state is a single int! This means there’s only about 4294967296 states to check!

Surely enough, we can write a little Rust program to check whether or not this dangerous little piece of seemingly logic-defying piece of C code does in fact terminates. The idea is simply to create a big vector with one entry per input state, initialize the state for 1 as we known the program terminates then and link all other states to the next until they eventually hit 1. Or in the case of this specific implementation, \( \le 1 \).

const MAX_C_INT: i32 = i32::MAX;

#[derive(Clone)]
enum State {
    Terminates,
    SameAs(usize),
}

fn main() {
    let mut graph: Vec<State> = vec![State::Terminates; MAX_C_INT as usize + 1];

    // Initialize the termination state for all numbers
    for n in 2..=MAX_C_INT {
        graph[n as usize] = if n % 2 == 0 {
            State::SameAs(n.wrapping_div(2).max(1) as usize)
        } else {
            State::SameAs(n.wrapping_mul(3).wrapping_add(1).max(1) as usize)
        }
    }

    // Follow the termination paths
    let mut unknown_termination: usize = 1;
    while unknown_termination > 0 {
        unknown_termination = 0;

        for n in 2..=MAX_C_INT {
            graph[n as usize] = match graph[n as usize] {
                State::Terminates => State::Terminates,
                State::SameAs(dst) => {
                    unknown_termination += 1;
                    graph[dst as usize].clone()
                }
            }
        }

        println!("{}", unknown_termination);
    }
}

And surely enough, consuming just a little bargain of 37GB of RAM, we have our answer:

❯ cargo run --release
    Finished release [optimized] target(s) in 0.00s
     Running `target/release/collatz-termination-rs`
2147483646
1550960379
1317017077
1136939144
762200279
128062193
565753
45
0

Which means that we linked all states back to \(\le 1\) and our program does in fact terminate for every single possible input. So we can say that as of 2023, we know the program terminates².