<p>Consider the function $T: \mathbb N \rightarrow \mathbb N$, where $T(n)=n/2$ when $n$ is even and $T(n)=n+1$ when $n$ is odd. Then it is known that for any $n \in \mathbb N$, there exists a $k \in \mathbb N$ such that $T^{(k)}(n)=1$.</p>

<p>If instead of $T(n)=n+1$ when $n$ is odd, we had defined $T(n)=3n+1$ when $n$ is odd, we would have the Collatz Conjecture, so I think this is the nearest problem to the Collatz Conjecture that has ever been resolved.</p>

CC BY-SA 3.0
2015-07-14T22:17:31.780Z
I don't think this satisfies the "most complex" part of the question, as a motivated grade school student can identify the key idea behind the proof of your statement with a bit of thought.
Yonatan N
CC BY-SA 3.0
2015-07-15T14:25:02.100Z
But if it is more complex and still resolved, it won't resemble the Collatz Conjecture anymore. Furthermore, the title of his question indicates that he gives priority to "nearest" over "most complex".
Craig Feinstein
CC BY-SA 3.0
2015-07-14T15:32:41.750Z
2015-07-14T15:32:41.750Z
Craig Feinstein
<p>An extended comment:</p>
<p>Collatz-like sequences can be computed by <em>small</em> Turing machines having few symbols and states.  In &quot;<a href="https://webusers.imj-prg.fr/%7Epascal.michel/paperpm1.pdf" rel="nofollow noreferrer">Small Turing machines and generalized busy beaver competition</a>&quot; by P. Michel (2004) (<a href="https://doi.org/10.1016/j.tcs.2004.05.008" rel="nofollow noreferrer">doi</a> and <a href="https://arxiv.org/abs/0906.3749" rel="nofollow noreferrer">closely related 2019 preprint update</a>), there is a nice table that positions Collatz-like problems between decidable TMs (for which the halting problem is decidable) and Universal TMs.</p>
<p><img src="https://i.sstatic.net/DlnUG.jpg" alt="enter image description here" /></p>
<p>There are TMs that compute Collatz-like sequences for which the decidability is still an open problem: <span class="math-container">$TM(5,2)$</span>, <span class="math-container">$TM(3,3)$</span> and <span class="math-container">$TM(2,4)$</span> (where <span class="math-container">$TM(k,l)$</span> is the set of Turing Machine with <span class="math-container">$k$</span> states and <span class="math-container">$l$</span> symbols). I don't know if the results have been inproved.</p>
<p>From the conclusion of the paper:</p>
<p><em>... The present Collatz-like line is already on its lowest possible level, with the possible exception of <span class="math-container">$TM(4,2)$</span>, but we conjecture that all machines in this set can be proved to be decidable...</em></p>
<p>See also &quot;<a href="https://arxiv.org/abs/1110.2230" rel="nofollow noreferrer">The complexity of small universal Turing machines: a survey</a>&quot; by D. Woods and T. Neary (2007) (<a href="https://doi.org/10.1016/j.tcs.2008.09.051" rel="nofollow noreferrer">doi</a>)</p>
<p>Another example of Collatz-like problem for which decidability is an open problem is the Post's tag system: <span class="math-container">$\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$</span>; for a recent analysis see &quot;<a href="http://arxiv.org/abs/0906.3329" rel="nofollow noreferrer">On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results</a>&quot; by L. De Mol (2009).</p>

CC BY-SA 3.0
2012-06-02T16:23:39.253Z
to complement the answer: Conway showed that there are Collatz-like sequences which are undecidable http://www.ams.org/mathscinet-getitem?mr=392904. i.e. a collatz-like sequence can itself simulate a universal turing machine.
Sasho Nikolov
CC BY-SA 3.0
2012-06-02T16:23:53.370Z
thx! the mitchell survey/results are very cool! fyi clarification in the table, a "T" in a cell indicates a TM(k,l) has been shown to exist that is equivalent to the collatz conjecture. the perspective also suggests that the collatz conjecture is not merely an isolated theoretical curiosity but possibly a surface phenomenon of something deeper in computability theory. ps also very interested if any once-open "collatz like problems" have ever been solved...?
vzn
CC BY-SA 4.0
2023-09-23T10:28:49.347Z
The TM(19, 2) Universal entry of the table has (since?) fallen to  TM(15, 2) as per image at: https://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine/10390#10390
Ciro Santilli OurBigBook.com
CC BY-SA 4.0
2024-08-01T20:37:02.860Z
Here is a wiki with the latest info (as of 1 Aug 2024) on busy beavers and Cryptids (essentially: Collatz-like machines) - it contains several updates compared to the above table: https://wiki.bbchallenge.org/wiki/Main_Page
Joshua Grochow
CC BY-SA 4.0
2012-06-02T09:55:11.443Z
2024-08-01T18:46:17.320Z
2024-08-01T18:46:17.320Z
Marzio De Biasi
<p>I am interested in the &quot;nearest&quot; (and &quot;most complex&quot;) problem to the <a href="http://en.wikipedia.org/wiki/Collatz_conjecture" rel="noreferrer">Collatz conjecture</a> 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 <a href="http://en.wikipedia.org/wiki/MU_puzzle" rel="noreferrer">Hofstadter's MIU game</a> (resolved, but admittedly more of a toy problem) are indeed decidable or have been solved.</p>
<h3>Related questions</h3>
<p><a href="https://cstheory.stackexchange.com/questions/5675/collatz-conjecture-grammars-automata">Collatz Conjecture &amp; Grammars / Automata</a></p>

CC BY-SA 3.0
2013-09-19T16:53:13.743Z
[TCS/empirical angles on collatz/refs](http://vzn1.wordpress.com/code/collatz-conjecture-experiments/)
vzn
CC BY-SA 3.0
2014-06-21T15:54:20.187Z
fyi here is a new paper by Michel that nicely surveys the area connecting undecidability to a general number theoretic framework, [problems in number theory from busy beaver competition](http://arxiv.org/pdf/1311.1029v1.pdf)
vzn
<reference-request><open-problem><nt.number-theory><halting-problem><computability>
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
vzn
# What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?

(Asked by: username_0 on 2012-06-02)

I am interested in the "nearest" (and "most complex") problem to the [Collatz conjecture](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/MU_puzzle) (resolved, but admittedly more of a toy problem) are indeed decidable or have been solved.

### Related questions

[Collatz Conjecture & Grammars / Automata](https://cstheory.stackexchange.com/questions/5675/collatz-conjecture-grammars-automata)

**Tags:** reference-request, open-problem, nt.number-theory, halting-problem, computability

> **Comments:**
> **username_0**: [TCS/empirical angles on collatz/refs](http://username_01.wordpress.com/code/collatz-conjecture-experiments/)  
> **username_0**: fyi here is a new paper by Michel that nicely surveys the area connecting undecidability to a general number theoretic framework, [problems in number theory from busy beaver competition](http://arxiv.org/pdf/1311.1029v1.pdf)  

---

## 2 answers

### Answer by username_3 on 2012-06-02. Score: 27 | Accepted answer

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](https://webusers.imj-prg.fr/%7Epascal.michel/paperpm1.pdf)" by P. Michel (2004) ([doi](https://doi.org/10.1016/j.tcs.2004.05.008) and [closely related 2019 preprint update](https://arxiv.org/abs/0906.3749)), there is a nice table that positions Collatz-like problems between decidable TMs (for which the halting problem is decidable) and Universal TMs.

![enter image description here](https://i.sstatic.net/DlnUG.jpg)

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 conclusion 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](https://arxiv.org/abs/1110.2230)" by D. Woods and T. Neary (2007) ([doi](https://doi.org/10.1016/j.tcs.2008.09.051))

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](http://arxiv.org/abs/0906.3329)" by L. De Mol (2009).

> **Comments:**
> **username_4**: to complement the answer: Conway showed that there are Collatz-like sequences which are undecidable http://www.ams.org/mathscinet-getitem?mr=392904. i.e. a collatz-like sequence can itself simulate a universal turing machine.  
> **username_0**: thx! the mitchell survey/results are very cool! fyi clarification in the table, a "T" in a cell indicates a TM(k,l) has been shown to exist that is equivalent to the collatz conjecture. the perspective also suggests that the collatz conjecture is not merely an isolated theoretical curiosity but possibly a surface phenomenon of something deeper in computability theory. ps also very interested if any once-open "collatz like problems" have ever been solved...?  
> **username_5**: The TM(19, 2) Universal entry of the table has (since?) fallen to  TM(15, 2) as per image at: https://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine/10390#10390  
> **username_6**: Here is a wiki with the latest info (as of 1 Aug 2024) on busy beavers and Cryptids (essentially: Collatz-like machines) - it contains several updates compared to the above table: https://wiki.bbchallenge.org/wiki/Main_Page  

---

### Answer by username_1 on 2015-07-14. Score: 6

Consider the function $T: \mathbb N \rightarrow \mathbb N$, where $T(n)=n/2$ when $n$ is even and $T(n)=n+1$ when $n$ is odd. Then it is known that for any $n \in \mathbb N$, there exists a $k \in \mathbb N$ such that $T^{(k)}(n)=1$.

If instead of $T(n)=n+1$ when $n$ is odd, we had defined $T(n)=3n+1$ when $n$ is odd, we would have the Collatz Conjecture, so I think this is the nearest problem to the Collatz Conjecture that has ever been resolved.

> **Comments:**
> **username_2**: I don't think this satisfies the "most complex" part of the question, as a motivated grade school student can identify the key idea behind the proof of your statement with a bit of thought.  
> **username_1**: But if it is more complex and still resolved, it won't resemble the Collatz Conjecture anymore. Furthermore, the title of his question indicates that he gives priority to "nearest" over "most complex".  

---

