Timeline for What are the most attractive Turing undecidable problems in mathematics?
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 1, 2023 at 12:28 | comment | added | Ville Salo | Anyway, I disagree with my old self. Actually, just saying "rule 110" is much less ambiguous than just saying "integers", since there is so little literature on rule 110 (that I'm aware of). | |
| Oct 1, 2023 at 12:25 | comment | added | Ville Salo | 6) No, I'm referring to the ring of integers. It's a mathematical object. You can ask many problems about it, some are decidable, some are not. Same as with 110. | |
| Oct 1, 2023 at 12:15 | comment | added | Lucas K. | 6) About "The integers are a fun example!". That is not a clear description of a system, while Rule 110 is. Are you referring to First Order Logic with Peano Axioms, that Godel used for his incompleteness theorem? Which actually proofs Turing Completeness, while that term was not invented yet? | |
| Oct 1, 2023 at 12:12 | comment | added | Ville Salo | 5) Yes, and here by "problem" i mean a language (of encodings of instances to a problem). | |
| Oct 1, 2023 at 12:08 | comment | added | Lucas K. | 5) You wrote "Now, over a decade later, no one knows a good undecidable problem about it." Undecidability is about a class of problems, not a single problem. | |
| Oct 1, 2023 at 12:07 | comment | added | Lucas K. | @VilleSalo 1) I think your comments are valuable for people that want to know more about this. 2). The original question did not ask about proofs, but about 'attractive'. I think Rule 110 because of its simplicity. 3) If something is Turin complete, then it means that you can simulate a Turing machine in it and that means you can encode a Turing Halting problem in it. 4) However, there I agree with you, then you have to translate the problem back to the orginal construction. I didn't do that properly. | |
| Sep 29, 2023 at 5:22 | comment | added | Ville Salo | I'll add an explicit statement here, the following was stated in arxiv.org/pdf/1201.1039.pdf (my own recollection of what Cook proved is slightly different, but it's a long time since I read it). Given four finite words $u, v, w, t \in \{0,1\}^*$, it is undecidable whether there exist $n \in \mathbb{N}$, $m \in \mathbb{Z}$ such that $\sigma^m(f^n(...uuuwvvv...)) \in [t]$ where $f$ is rule 110, and $[t]$ denotes a cylinder. | |
| Sep 29, 2023 at 3:49 | comment | added | Ville Salo | 3) I would say your answer is like answering this with "The integers are a fun example!" Or it seems your answer is actually worse because if you search "integers undecidable problem", you will find an explicit statement on the first page (I tried it), while if you search "rule 110 undecidable problem", you will have to guess the right link to click on and browse for some time. Cook's papers have no theorems, so those are not the right guess unless you want to actually read the entire proof. | |
| Sep 29, 2023 at 3:47 | comment | added | Ville Salo | 2) You say that if something has been shown to be "Turing complete", then some problem is undecidable. Probably. But I cannot help but be reminded of Wolfram's "(2,3) Turing machine". Alex Smith showed it's Turing complete. I read the proof (to a degree), and was convinced. Now, over a decade later, no one knows a good undecidable problem about it. Alex was a brilliant guy (and probably still is) and spent some effort trying to formalize the initial conditions, but it's not easy. Very weak CA/TM can lead to undecidable problems when your initial conditions are not eventually periodic. | |
| Sep 29, 2023 at 3:47 | comment | added | Ville Salo | Why shouldn't one answer a precise mathematical question with an imprecise answer on MathOverflow? Do I really need to answer that? I will give three answers: 1) The danger with having to guess what Turing complete means in each specific case is that you can guess wrong. In this case, it is not hard to guess what the right answer is, but it's not trivial either. Your guess is wrong, or at least I have never seen this stated. It might be provable, or could just be false; certainly for some CA, the prediction problem is decidable on finite configurations, but not on eventually periodic ones. | |
| Sep 28, 2023 at 18:39 | comment | added | Lucas K. | @VilleSalo I don't see the problem. If you have any Turing Complete system, then you can make an undecidable problem out of it. For the initial state, I assume (but I didn't researched it), that it is finite. So, that at a certain point to the left and right you only have zeros. | |
| Sep 28, 2023 at 10:36 | comment | added | Ville Salo | (The downvote is not mine, and I'd love to see a precise version of this answer here.) | |
| Sep 28, 2023 at 10:32 | comment | added | Ville Salo | And how do you restrict the initial state? If you just have arbitrary computable sequences, then this problem is undecidable for the shift map. Is 110 more Turing complete than a shift map? Just to clarify, I know at least one useful answer to this question, and am just pointing out that this answer is not very good as it stands. (And yes technically I could fix it, but this would take much longer than complaining.) | |
| Sep 28, 2023 at 8:16 | comment | added | Lucas K. | @VilleSalo It is of course decidable what the state will be after n steps. The Wikipedia tells that it is 'Turing Complete'. This implies that it is undecidable whether a cell will flip eventually to 1 given a certain begin state (so, not knowing the number of steps). | |
| Sep 27, 2023 at 6:40 | comment | added | Ville Salo | "Rule 110" is not an "undecidable problem", and the Wikipedia page does not clearly state what is an undecidable problem related to it. | |
| Feb 18, 2020 at 14:07 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question has been bumped anyway)
|
| Jun 6, 2011 at 4:27 | comment | added | Selene Routley | As well as for its own sake, I find this one intensely interesting from the non-mathematical standpoint: it's simple enough that it is quite plausible that lone molecules / simple groups of such could be working as universal Turing machines. Even more plausible when you consider that there are many such rules that are Turing complete. Mind boggling implications for biology. | |
| May 24, 2010 at 19:59 | history | answered | Lucas K. | CC BY-SA 2.5 |