Metaculus
 Questions
 Categories
 Rankings
 Log in Sign Up

Dark Mode
Help
Question
Metaculus Help: Spread the word
If you like Metaculus, tell your friends! Share this question via Facebook, Twitter, or Reddit.
Is the halting problem for the Collatz Program computable?
In related questions, we asked whether the Collatz Conjecture is true and when it will be resolved one way or another. Here we ask more specifically whether we can predict the behavior of the corresponding program.
Let's define the Collatz Program in pseudocode as
collatz(n) =
if (n is 1) return 1
else if (n is even) return collatz(n/2)
else return collatz(3n + 1)
where input n is a positive integer.
The Collatz Conjecture is that this program halts (and returns 1) for all integer inputs.
Let's imagine a companion program called collatz_halts(), which takes an integer input n, always halts, and returns 1 if collatz() halts, and 0 otherwise.
Does collatz_halts() exist? If collatz() always halts, then collatz_halts() definitely exists, because the answer is 1 for all inputs. If collatz_program() only halts for some n, then collatz_halts() might or might not exist.
Note that if the Collatz Conjecture is false for only a finite number of inputs, then collatz_halts() exists, since the program could test against an enumeration of the the inputs for which collatz() does not halt. Also note that if collatz() always either halts or encounters a cycle, then collatz_halts() exists by modifying collatz() to check for cycles.
Resolution:

This question will resolve positively if it is demonstrated that a program must exist that always halts and tests whether the Collatz program halts with a given input.

It will resolve negatively if the Conjecture is proven to be false and such a haltingtest program is proven not to exist.

Both of these resolutions will be via publication in a major mathematics journal.
If no such proof is published before June 21, 2520, then the question will resolve as ambiguous.
Other questions on the Collatz Conjecture:
{{qctrl.predictionString()}}
Metaculus help: Predicting
Predictions are the heart of Metaculus. Predicting is how you contribute to the wisdom of the crowd, and how you earn points and build up your personal Metaculus track record.
The basics of predicting are very simple: move the slider to best match the likelihood of the outcome, and click predict. You can predict as often as you want, and you're encouraged to change your mind when new information becomes available.
The displayed score is split into current points and total points. Current points show how much your prediction is worth now, whereas total points show the combined worth of all of your predictions over the lifetime of the question. The scoring details are available on the FAQ.
Note: this question resolved before its original close time. All of your predictions came after the resolution, so you did not gain (or lose) any points for it.
Note: this question resolved before its original close time. You earned points up until the question resolution, but not afterwards.
This question is not yet open for predictions.
Thanks for predicting!
Your prediction has been recorded anonymously.
Want to track your predictions, earn points, and hone your forecasting skills? Create an account today!
Track your predictions
Continue exploring the site
Community Stats
Metaculus help: Community Stats
Use the community stats to get a better sense of the community consensus (or lack thereof) for this question. Sometimes people have wildly different ideas about the likely outcomes, and sometimes people are in close agreement. There are even times when the community seems very certain of uncertainty, like when everyone agrees that event is only 50% likely to happen.
When you make a prediction, check the community stats to see where you land. If your prediction is an outlier, might there be something you're overlooking that others have seen? Or do you have special insight that others are lacking? Either way, it might be a good idea to join the discussion in the comments.