Mathematics is full of difficult problems, most of which correspondingly seem difficult to solve. However, within the domain of difficult problems also exist those that seem easy to solve, or at the very least, easy to understand. The P vs. NP problem may be the most famous problem in this category, but another interesting (and even more simple) example is the 3x+1 problem (also known as the Collatz conjecture). This problem asks whether all positive integers will eventually reach 1 (or, analogously, the loop of 4, 2, 1) when repeatedly subjected to the following rules:
- If x is odd, the next number equals 3x + 1.
- If x is even, the next number equals x / 2.
For example, starting at 5, the sequence proceeds: 5 → 16 (3 * 5 + 1) → 8 (16 / 2) → 4 (8 / 2) → 2 (4 / 2) → 1 (2 / 2) → 4 (3 * 1 + 1) → 2 (4 / 2) → 1 (2 / 2) → … Veritasium has an interesting video (worth watching before proceeding) diving further into some examples and ways to visualize the nature of the problem, and he calls out the fact that, while we’ve tested the problem for numbers up to 268 and found they all reach 1, we still have not been able to prove the conjecture.
It seems the difficulty with this problem lies in its modal / discrete nature. Many (discrete) applications of the rules are required, with each involving a check to see which (modal) operation to apply (based on whether the number is odd or even). These separate, sequential checks mean that we aren’t able to treat the problem analytically, and instead must rely on brute force methods. To put it differently, there’s no single operation (that we’ve found) which can be applied to a number to determine whether it will reach 1; instead, we must go step by step, so that at each step it can be determined which operation to next apply. For any given number, all the math can “see” is that first number and the resulting first operation (and result), and this opaqueness has thus far prevented a proof.
This type of difficulty with modal / discrete problems is not limited to 3x+1. The Game of Life, for example, is similarly difficult to analyze, with behavior involving a series of discrete steps with multiple options. For those unfamiliar, this game involves a grid with many cells, each either on or off, with specific rules for how to update each cell at each time step. Similar to 3x+1, we’re reliant on brute force to determine the evolution in time – the only way to figure out the state at a particular time step is to run the game. We’re unable to look at a specific cell in a grid (and the states of its neighbors) and directly calculate its future state (i.e., skip the intermediary states), at least in a general way (certain states do lend themselves to prediction – for example, if all cells are off to start, they’ll all remain off).
At first glance, both 3x+1 and the Game of Life feel like they should be possible to analyze further – after all, the rules are fixed and exceedingly simple. Interestingly, however, for the Game of Life it can be proven that, in the general case, there’s no way to do better than simply running the game (i.e., applying the update rules to each cell). This proof relies on the fact that the Game of Life is Turing-complete (which means a computer can be built in it, as demonstrated here!), and is therefore subject to the halting problem (a proof that no general approach can exist for identifying whether a specified program will halt or run forever).
With that knowledge, it becomes less clear what we should expect for 3x+1. It’s certainly the simpler of the two problems (and seems far less likely to be Turing-complete), but the nature of the difficulty seems analogous to that present in the Game of Life. Additionally, as 268 represents 0% of all possible inputs, it’s not clear that we can lean too heavily on the fact that all numbers tested so far have exhibited the same behavior. Though some in the academic community view this problem as not worth spending time on, I hope more people like Prof. Kontorovich disregard that advice – as he points out, perhaps we’ve simply been looking in the wrong places.