Skip to main content
4 of 5
http -> https (the question was bumped anyway)
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?

Some of the simplest and most interesting unproved conjectures in mathematics are Goldbach's conjecture, the Riemann hypothesis, and the Collatz conjecture.

Goldbach's conjecture asserts that every even number greater than or equal to 4 can be written as the sum of two prime numbers. It's pretty straightforward how to create a computer program which halts if and only if there exists a counterexample to Goldbach's conjecture: simply loop over all integers, test if each one is a counterexample, and halt if a counterexample is found.

For the Riemann hypothesis, there's also a "known" computer program which halts if and only if there exists a counterexample.

(Given the usual statement of the Riemann hypothesis, this is not so clear, but Jeffrey C. Lagarias' paper "An Elementary Problem Equivalent to the Riemann Hypothesis" shows that the Riemann hypothesis is equivalent to the statement that a certain sequence of integers $L$ is a lower bound for a certain sequence of real numbers $R$. The sequence $L$ is computable, and $R$ is computable to arbitrary precision, so our computer program only needs to compute all elements of $R$ in parallel, and halt if any element is ever discovered to be smaller than its corresponding element in $L$.)

But how about the Collatz conjecture?

The Collatz conjecture states that for all positive integers $n$, the "hailstone sequence" $H_n$ eventually reaches $1$.

We could try to do the same thing we did with Goldbach's conjecture: loop over all positive integers $n$ and halt if a counterexample is ever found. But there's a problem here: with the Collatz conjecture, given a positive integer $n$, it's not obvious that it's even decidable whether or not $n$ is a counterexample. We can't simply "check whether or not $n$ is a counterexample" like we can with Goldbach's conjecture.

So is there a known Turing machine which halts if and only if the Collatz conjecture is false?

Of course, a "known Turing machine" doesn't have to be a Turing machine that someone has actually explicitly constructed; if it's straightforward how to write a computer program that would do this, then that counts as a "known Turing machine".

On the other hand, saying "it's either the machine which trivially halts, or it's the machine which trivially does not halt" doesn't count as a "known Turing machine"; I'm asking for an answer which mentions one single Turing machine $M$ (with no input or output), such that we know that $M$ halts if and only if the Collatz conjecture is false.

Sophie Swett
  • 1.2k
  • 8
  • 22