composing quantitative predictions generating intelligent understanding composing precise contingencies aggregating critical futures composing precise contingencies mapping the future predicting probable contingencies mapping intelligent forecasts mapping quantitative insights modeling accurate estimations composing quantitative understanding modeling precise forecasts calculating critical futures computing contingent estimations

Question

Metaculus Help: Spread the word

If you like Metaculus, tell your friends! Share this question via Facebook, Twitter, or Reddit.

When will the halting problem for the Collatz Program be resolved?

In related questions, we asked whether the Collatz Conjecture is true, when it will be resolved one way or the other, and whether a corresponding halting problem for the Collatz Program is computable.

For completeness and symmetry, this question asks when the halting problem will be resolved.

We can write 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.

Possible inputs to collatz() are divided into three sets:

  • Set 1: Inputs for which collatz() halts, after eventually encountering a power of 2
  • Set 2: Inputs for which collatz() eventually encounters a number twice, and then cycles forever
  • Set 3: Inputs that cause collatz() to forever avoid both repetition and powers of 2, exploring larger and larger numbers

The Conjecture is that all integers belong to Set 1, and that Sets 2 and 3 are empty.

The halting problem for the Collatz Program asks whether there can exist a program that takes as input an integer n, always halts itself, and returns 1 if collatz(n) halts and 0 if it does not halt.

It is possible that the Conjecture is false, and also that the halting problem for the Collatz Problem is not computable, in the same sense that the more general Halting Problem is not computable.

There are a number of ways in which it could turn out that the halting problem for the Collatz Program is computable.

  • If the Conjecture is true (and collatz()) always halts) then the halt-checking program is trivial: always return 1.
  • If the Conjecture is false, but Sets 2 and 3 are finite, then a halt-checking program could check a finite list of inputs for which to return 0, and return 1 otherwise.
  • If all inputs are either in Set 1 (halts) or Set 2 (cycles), then a modified version of collatz() could run until it either halts (returning 1) or detects a cycle (returning 0). Similarly, if Set 3 is finite, then a combination of checking a finite list and checking for cycles would suffice.
  • Possibly all three sets are infinite, but there is still some simple (or at least computable) rule that can determine membership without running collatz() forever.

When will this halting problem be resolved? It could be:

  • At exactly the same time that the Collatz Conjecture is resolved, especially if the Conjecture is shown to be true.
  • Later than the Conjecture is shown to be false. It could be that no algorithm is found for separating Set 1 from Sets 2 and 3, but also no proof is found that such an algorithm cannot exist.
  • Earlier than the Conjecture is resolved (as was pointed out in a comment on a related question). It could be proven, for example, that only a finite number of inputs cause collatz() to not halt, without resolving whether that number is zero.

This question will resolve with the date of publication in a major mathematics journal of an article that either 1) proves the Conjecture to be true (with the halting problem as a trivial implication), or 2) explicitly resolves the halting problem.


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. With tachyons you'll even be able to go back in time and backdate your prediction to maximize your points.

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.