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.
$\begingroup$
$\endgroup$
4
-
5$\begingroup$ Since this is HTML and not LaTeX, it's easier if you inline the references where they are pertinent. $\endgroup$– Suresh VenkatJun 2, 2012 at 6:49
-
$\begingroup$ TCS/empirical angles on collatz/refs $\endgroup$– vznSep 19, 2013 at 16:53
-
$\begingroup$ There's at least one person that claims "the Collatz conjecture" is the unique answer to your question. I'm skeptical on the completeness of the linked proof, but I haven't spent enough time analyzing it, yet. $\endgroup$– Boyd Stephen Smith Jr.Feb 12, 2014 at 17:06
-
$\begingroup$ 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 $\endgroup$– vznJun 21, 2014 at 15:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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) (doi and closely related 2019 preprint update), 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) (doi)
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).
answered Jun 2, 2012 at 9:55
-
9$\begingroup$ to complement the answer: Conway showed that there are Collatz-like sequences which are undecidable ams.org/mathscinet-getitem?mr=392904. i.e. a collatz-like sequence can itself simulate a universal turing machine. $\endgroup$ Jun 2, 2012 at 16:23
-
$\begingroup$ 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...? $\endgroup$– vznJun 2, 2012 at 16:23
-
$\begingroup$ The TM(19, 2) Universal entry of the table has (since?) fallen to TM(15, 2) as per image at: cstheory.stackexchange.com/questions/10207/… $\endgroup$ Sep 23 at 10:28
$\begingroup$
$\endgroup$
2
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.
-
2$\begingroup$ 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. $\endgroup$ Jul 14, 2015 at 22:17
-
2$\begingroup$ 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". $\endgroup$ Jul 15, 2015 at 14:25