What is the "nearest" problem to the Collatz conjecture that has been successfully resolved? I am interested in the &quot;nearest&quot; (and &quot;most complex&quot;) problem to the Collatz conjecture that has been successfully solved (which Erdos famously said &quot;mathematics is not yet ripe for such problems&quot;). It has been proven that a class of &quot;Collatz-like&quot; problems is undecidable. However, problems that are vaguely similar such as Hofstadter's MIU game (resolved, but admittedly more of a toy problem) are indeed decidable or have been solved.
Related questions
Collatz Conjecture &amp; Grammars / Automata
An extended comment:

Collatz-like sequences can be computed by small Turing machines having few symbols and states.  In "Small Turing machines and generalized busy beaver competition" by P. Michel (2004), there is a nice table that positions Collatz-like problems between decidable TMs (for which the halting problem is decidable) and Universal TMs.



There are TMs that compute Collatz-like sequences for which the decidability is still an open problem: $TM(5,2)$, $TM(3,3)$ and $TM(2,4)$ (where $TM(k,l)$ is the set of Turing Machine with $k$ states and $l$ symbols). I don't know if the results have been inproved.

From the comclusion of the paper:

... The present Collatz-like line is already on its lowest possible level, with the possible exception of $TM(4,2)$, but we conjecture that all machines in this set can be proved to be decidable...

See also "The complexity of small universal Turing machines: a survey" by D. Woods and T. Neary (2007).

Another example of Collatz-like problem for which decidability is an open problem is the Post's tag system: $\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$; for a recent analysis see "On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results" by L. De Mol (2009).