Timeline for Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?
Current License: CC BY-SA 4.0
46 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 10 at 23:45 | history | edited | RobPratt |
edited tags
|
|
| Jan 10, 2023 at 10:25 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question was bumped anyway)
|
| Feb 7, 2021 at 15:45 | vote | accept | Sophie Swett | ||
| Sep 15, 2018 at 10:47 | answer | added | Bjørn Kjos-Hanssen | timeline score: 33 | |
| S Sep 14, 2018 at 19:37 | history | suggested | Robert Frost |
added open problem tag
|
|
| Sep 14, 2018 at 19:36 | review | Suggested edits | |||
| S Sep 14, 2018 at 19:37 | |||||
| Aug 26, 2018 at 12:53 | comment | added | Burak | @TannerSwett: Maybe this example will clear things up for you. Consider the Turing machine $T_1$ which looks for a counterexample of, say, Goldbach's conjecture after searching and finding a proof of 0=1 in PA, and the Turing machine $T_2$ which just looks for a counterexample of Goldbach's conjecture directly. Do you think it makes sense to ask "Do we know the equivalence $T_1$ halts iff $T_2$ halts?" without specifying a base theory? | |
| Aug 26, 2018 at 12:46 | comment | added | Burak | @TannerSwett: Please read my comment regarding termination of Goodstein sequences. The answer to your last question is YES. You can write down a Diophantine equation whose solution exists if and only if PA is inconsistent. In this case, PA would not be able to detect the non-existence of solutions whereas ZFC would. Another example this polynomial which can be proven to not have a solution in integers in ZFC+Inaccessible but you cannot do this in ZFC. In any case, even if you set your background theory to be ZFC in the OP, I believe the current answer is NO. | |
| Aug 26, 2018 at 0:27 | comment | added | Sophie Swett | @JoelDavidHamkins I understand very well how statements like "the life-on-Mars language is computable" and "the Collatz conjecture is equivalent to some Turing machine" are true; I don't have any misconceptions there that need clearing up. I don't quite disagree that my question only makes sense in the context of a particular theory... but I don't understand why you're asking "what theory?" for this particular question. If I had asked "is it known whether or not such-and-such Diophantine equation has any solutions", would you still have asked "known in which theory"? | |
| Aug 25, 2018 at 17:30 | comment | added | Burak | @TannerSwett: This is why the base theory matters. Here is a correct formulations of your question: Has someone explicitly constructed a Turing machine T for which we have that the equivalence "CC iff T does not halt" is proven in (your favorite base theory that is able to talk about Turing machines)? Since we do not know whether CC is true or not at the moment, the answer that T is the machine that always halts or never halts is not meaningful. (However, once CC is proven or disproven, we will know which equivalence can be proven.) | |
| Aug 25, 2018 at 17:25 | comment | added | Burak | @TannerSwett: Let me explain the issue with a concrete example. It is a theorem of ZFC that every Goodstein sequence terminates (let's call this statement GS.) Therefore, in ZFC, we have the equivalence "GS iff T halts" where T is the Turing machine which halts after a single step on any input. Now, it is also known that GS is not a theorem of PA. Therefore, the equivalence "GS iff T halts" cannot be proven in PA. As you can see, one theory is able to prove the equivalence whereas the other is not. This is exactly Joel's point made above. | |
| Aug 25, 2018 at 16:49 | comment | added | Joel David Hamkins | It may also be helpful to consider also the program that searches for a proof (in ZFC, say, or whatever your favorite strong theory is) that CC is false. We can easily design such a program. It follows that this particular program halts if and ony if there is provably a counterexample to CC. If it turns out that CC is independent of the theory, then it becomes a philosophical question as to whether it is true or not. | |
| Aug 25, 2018 at 15:26 | comment | added | Joel David Hamkins | Perhaps this answer and discussion help explain the point I am trying to make: mathoverflow.net/a/48031/1946. | |
| Aug 25, 2018 at 15:25 | comment | added | Joel David Hamkins | Yes, I had seen what you wrote. The "always halt" program is one single program, and we already know of it. And the "never halt" program is one single program, and we already know of it. And depending on whether the Collatz conjecture is true or false, therefore, exactly one of these is a single program, that we already know of, which halts iff CC is false. If you object to this by saying we don't know the final equivalence, then I would ask, what does it mean to know an equivalence like this, except to have a proof in a certain theory? But you haven't mentioned any theory. | |
| Aug 25, 2018 at 15:08 | vote | accept | Sophie Swett | ||
| Feb 7, 2021 at 15:45 | |||||
| Aug 25, 2018 at 15:07 | comment | added | Sophie Swett | @JoelDavidHamkins Well, I'm not asking whether or not the equivalence can be proved in any one theory; I'm asking whether or not we humans already know of "one single Turing machine M (with no input or output), such that we know that M halts if and only if the Collatz conjecture is false" (quoting from my question). To me, it the question seems clear as to what I'm asking; is there something else I could add or change to make it clearer? | |
| Aug 25, 2018 at 8:10 | review | Close votes | |||
| Aug 26, 2018 at 16:43 | |||||
| Aug 25, 2018 at 1:45 | comment | added | Joel David Hamkins | Meanwhile, I don't find the issue pedantic, since as I mentioned, this is unfortunately a very common mistake which leads to many confusions, and I find it important to get it right. I view it as fundamentally similar to the kind of mistake that beginners make in complexity theory by asking about the complexity of a problem, but being vague about what the problem is exactly, for example, by not specifying the exact input/output. | |
| Aug 25, 2018 at 1:41 | comment | added | Joel David Hamkins | Gerhard, yes, I saw the edit in the question, but it still doesn't mention any theory, which I find to be the crux of the foundational confusions here, and also, the "always halt" program is one specific program, as is the "never halt" program. Also, if one is just asking for an equivalence, then the question trivializes, since all true statements are equivalent. Rather, what I find to be at issue is whether the equivalence can be proved in a specific theory, such as PA. This is a bit closer to what Timothy's pedant is getting at, but even he doesn't mention the role of the theory. | |
| Aug 25, 2018 at 0:51 | comment | added | Timothy Chow | @TannerSwett : Your intended question is the same as the intended question in the linked MSE question. If you read the text of the MSE question, it says, "is Collatz known to be equivalent to a $\Sigma_1$ or $\Pi_1$ statement?" By the way, your suggested formulation "is Collatz equivalent to a known $\Pi_1$ statement" is also unacceptable to a pedant, because what you are hoping is known is the equivalence and not the statement. It does you no good to know a statement if you don't know that it's equivalent to Collatz. | |
| Aug 24, 2018 at 23:00 | comment | added | Todd Trimble | If everyone would please take note: the "answer" by Gerald Edgar was not an answer, but a comment: a "request" to clarify the question. (It was also flagged as rude/abusive, which partly explains the initial action of deletion.) It now appears as a comment, intact, above, where it belongs. Everyone can see it and act accordingly. (I am also being accused of overstepping my bounds, replete with a rash of exclamation points, whereas from my POV I'm just trying to carry out my duties in attending to flags. I'd like to request that people withhold accusations, and stick to math. Thank you.) | |
| Aug 24, 2018 at 22:39 | comment | added | Gerhard Paseman | @Joel, indeed, and the poster attempted to explain the question more precisely with the examples. Is there a way of phrasing it better to reveal these issues? Given the care you usually give to your posts, I imagine you have read what was posted. However, it seems from the comments that you and Gerald are responding only to the title (which could be improved, but only marginally) and not the post. Gerhard "Say It Isn't So Joel" Paseman, 2018.08.24. | |
| Aug 24, 2018 at 22:19 | answer | added | Gerry Myerson | timeline score: 17 | |
| Aug 24, 2018 at 22:15 | comment | added | Joel David Hamkins | For example, one can find many people asking such things as: is there a Turing machine that correctly states whether or not the continuum hypothesis is true? (And this is essentially the same as the current question, but with CH instead of CC.) The answer is yes, as Gerald indicated, because there are machines that say "yes" and machines that say "no", and one of these is correct. It is no good to reject this answer is "not what I meant"; rather, one must actually ask the question that is meant, and this will be a bit subtler and will require one to think harder about foundational matters. | |
| Aug 24, 2018 at 22:07 | comment | added | Joel David Hamkins | But I see that this comment is also the content of the answer posted by Gerald Edgar, and apparently deleted by a moderator. But I don't think it should have been deleted, since I think there is a kind of sloppiness in the question, which is quite a common kind of sloppiness that infects many questions of beginners in complexity theory. The question is not sensible unless one specifies a specific theory and asks for a proof of equivalence to a $\Pi^0_1$ statement. | |
| Aug 24, 2018 at 22:03 | comment | added | Joel David Hamkins | So in any case, the conjecture is equivalent to the halting of a "known" program. The actual question should be: is the Collatz conjecture provably equivalent (in PA?) to the halting of a particular program? | |
| Aug 24, 2018 at 22:03 | comment | added | Joel David Hamkins | The question suffers from a uniformity issue common to many similar questions. Namely, the answer is yes, because: if the Collatz conjecture is true, then it is equivalent to the halting of the Turing machine program that halts immediately, and this program is "known"; and if the Collatz conjecture is false, then it is equivalent to the halting of the program that never halts, and such a program is "known." | |
| Aug 24, 2018 at 20:40 | comment | added | PrimeRibeyeDeal | @YCor furthermore, we need to worry about whether the interior and exterior of a cave are well-defined notions. | |
| Aug 24, 2018 at 20:35 | comment | added | YCor | @TannerSwett I'm skeptical about the use of "it is known that" in a logical statement. What is somebody in a cave has a working proof that Collatz holds? | |
| Aug 24, 2018 at 20:30 | comment | added | Sophie Swett | The answer definitely seems to be "no, no such Turing machine is known", but it'll be hard to produce an authoritative answer based on that... | |
| Aug 24, 2018 at 20:29 | comment | added | Sophie Swett | Sounds like a matter of the order of quantifiers: I meant to ask "does there exists T such that (it is known that (T halts iff not Collatz))", and Gerald answered "is it known that (there exists T such that (T halts iff not Collatz))". In any case, I think my question and the linked MSE question are slightly different. The MSE question asks "is Collatz equivalent to either a $\Sigma_1$ statement or a $\Pi_1$" statement"; I'm asking "is Collatz equivalent to a known $\Pi_1$ statement". | |
| Aug 24, 2018 at 20:20 | comment | added | Gerhard Paseman | The suggested grouping starts with a main clause :" Is there machine T such that (T halts iff Collatz)". Gerald's answer suggests (is there T that halts) iff (Collatz). I don't mind the regrouping so much as the implicit attitude. If Gerald had suggested a clarification rather than issue a challenge, my comment would have been different. I would not call his answer spam. Neither would I call it helpful nor would I call it appropriate to the mission of the forum. Gerhard "Usually I Respect Gerald's Posts" Paseman, 2018.08.24. | |
| Aug 24, 2018 at 20:19 | comment | added | Todd Trimble | @YCor I didn't delete "as spam", but acted on a flag. I didn't mean to do so inappropriately; it's now a comment. | |
| Aug 24, 2018 at 20:14 | comment | added | Sophie Swett | Of course, if the Collatz conjecture is ever proved or disproved, then the answer that Gerald wrote will be correct! | |
| Aug 24, 2018 at 20:12 | comment | added | Burak | @YCor: Whether Gerald's answer was technically correct depends on your interpretation of the question. If the OP is interpreted as asking for a Turing machine T for which we currently have a proof of the equivalence "T halts iff CC fails" in some base system such as ZFC or PA, then Gerald's answer was not correct. If it is interpreted as asking for the existence of a Turing machine T for which it holds in the set-theoretic universe that "T halts iff CC fails", then his answer was technically correct. I believe the suitable phrasing of the question should be as in the MSE post linked above. | |
| Aug 24, 2018 at 20:12 | comment | added | Sophie Swett | @YCor I edited my question to hopefully clarify that. I'm asking for an answer which mentions one single Turing machine $M$ (with no input or output), such that we know that $M$ halts if and only if the Collatz conjecture is false. | |
| Aug 24, 2018 at 20:11 | history | edited | Sophie Swett | CC BY-SA 4.0 |
Try to clarify what I mean by "known Turing machine"
|
| Aug 24, 2018 at 20:11 | comment | added | YCor | @ToddTrimble Gerald Edgar's answer probably better fitted as a comment, and possibly relies on a misunderstanding, but I believe deleting it as spam overrides the moderator's role. | |
| Aug 24, 2018 at 20:08 | comment | added | YCor | There was a answer by Gerald Elgar, which should rather have been a comment, and deleted by a moderator as spam (!!!!), which from my (probably incorrect) understanding was technically correct, namely "if CC holds, the machine that returns no, if CC fails, the machine that returns yes". So I'd like to understand why this does not answer the question (the comment "you drew the parentheses wrong, not him" by Gerhard Paseman doesn't help me). Could it be clearly asserted what is the desired input and output of a machine as in the question? | |
| Aug 24, 2018 at 19:10 | comment | added | Gerald Edgar | YES. (1) there is a Turing machine that never halts (2) there is a Turing machine that always halts One of those is your answer. Now, try to phrase your question so that my answer no longer applies. | |
| Aug 24, 2018 at 18:39 | comment | added | Timothy Chow | Your question is basically a duplicate of the following question on Math StackExchange: math.stackexchange.com/questions/100218/… | |
| Aug 24, 2018 at 18:36 | comment | added | Noah Schweber | Put another way, you are asking whether the Collatz conjecture has a known $\Pi^0_1$ equivalent. As far as I'm aware, the answer is no. | |
| Aug 24, 2018 at 18:13 | comment | added | Anthony Quas | Oh yes. I forgot about that possibility. | |
| Aug 24, 2018 at 18:11 | comment | added | Sophie Swett | @AnthonyQuas Because the Collatz conjecture may have counterexamples where the hailstone sequence doesn't fall into a bad cycle (it may increase without bound instead). | |
| Aug 24, 2018 at 18:08 | comment | added | Anthony Quas | Why can’t you check all numbers up to $n$ and see whether they fall into a bad cycle before the $n$th step? | |
| Aug 24, 2018 at 17:11 | history | asked | Sophie Swett | CC BY-SA 4.0 |