I am interested in the nearest (and most complex) problem to the Collatz conjecture that has been successfully solved (which Erdos famously said mathematics is not yet ripe for such problems). It has been proven that a class of Collatz-like 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 questionsCollatz Conjecture & Grammars / Automata
What is the nearest problem to the Collatz conjecture that has been successfully resolved?
reference request;open problem;nt.number theory;halting problem;computability
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).