Timeline for What do you do if you believe a problem is undecidable?
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 24, 2015 at 22:37 | answer | added | Gerhard Paseman | timeline score: 4 | |
| Feb 7, 2015 at 6:00 | comment | added | Włodzimierz Holsztyński | It's hard to decide. | |
| Feb 7, 2015 at 4:40 | answer | added | Joel David Hamkins | timeline score: 37 | |
| Feb 6, 2015 at 22:36 | comment | added | François G. Dorais | @Pace "Is there any literature on making rings into Turing machines?" That's the wrong way around, you typically want to interpret Turing machines into ring structures. | |
| Feb 6, 2015 at 20:44 | comment | added | Will Jagy | $$\begin{array}{l}\text{When in danger or in doubt,}\cr \text{Run in circles, scream and shout.}\end{array}$$ | |
| Feb 6, 2015 at 19:28 | comment | added | Pace Nielsen | @EmilJeřábek, of course you are right, I should have seen that. A brute-force search to larger degrees (iterating over larger and larger initial segments of $\vec{n}$) will either produce $m$ or never halt. So the question is ultimately whether that algorithm always halts. | |
| Feb 6, 2015 at 19:18 | comment | added | Emil Jeřábek | @PaceNielsen: How do you give the infinite sequence $\vec n$ to an algorithm as input? Anyway, once you do it in such a way that generators of the ideal are enumerable, you can compute an $m$ by brute-force search (assuming it exists in the first place). | |
| Feb 6, 2015 at 19:10 | comment | added | Pace Nielsen | @EmilJeřábek, thank you for the clarification between the two meanings of undecidable. You are correct that I am most interested in (2). That said, a related question is whether given a vector $\vec{n}$ (as above) one can compute an integer $m$ so that $(a+b)^m\in I$ (or output $\infty$ if no such integer exists). So decidability/computability in the sense of (1) is also somewhat relevant! | |
| Feb 6, 2015 at 19:10 | review | Close votes | |||
| Feb 6, 2015 at 23:56 | |||||
| Feb 6, 2015 at 19:06 | comment | added | Pace Nielsen | @StefanKohl, good question. Start with the claim "the sum of two nil left ideals is nil". The only trouble here is closure under additivity. Thus, if this were false, $a+b$ would not be nilpotent while $Ra$ and $Rb$ were nil ideals. Further, if it were false somewhere, then it would be false freely. Finally, the reduction from $Rb$ being a left nil ideal to just $b$ being nilpotent is something I came up with (although I think it was found long ago by Puczylowski, and I believe it is open even for $b^2=0$!). | |
| Feb 6, 2015 at 19:00 | comment | added | Burak | @AsafKaragila: I know absoluteness results are how we prove things via forcing. Since the title suggested that the problem might be independent of ZFC, forcing will not help. On the other hand, as you have noted, if one can force this statement to be false, as Pace suspects, then it is false. | |
| Feb 6, 2015 at 19:00 | comment | added | Emil Jeřábek | @AnthonyQuas and Per Alexandersson: “Undecidable problem” means one of two different things: (1) a non-computable set of integers (or other finite objects); (2) a statement independent of a given theory. Wang tiles are an instance of (1), whereas the question asks for (2). | |
| Feb 6, 2015 at 18:54 | comment | added | Stefan Kohl♦ | @PaceNielsen: You give a nice formulation of Koethe's conjecture -- where is it from? (Lam, page 171 gives a number of equivalent formulations of this conjecture, but your version does not seem to appear there). I particularly like your formulation because it 'reduces' the problem from arbitrary rings to a particular ring. | |
| Feb 6, 2015 at 18:53 | comment | added | Asaf Karagila♦ | @Burak: This actually gives an opportunity of proving things with forcing. It suffices to show that you can always force a particular truth value in order to prove the statement. | |
| Feb 6, 2015 at 18:35 | comment | added | Pace Nielsen | @AnthonyQuas, that is an interesting idea. From the wiki, it appears this form of undecidability ultimately comes from embedding some form of Turing machines into the tiling process. Is there any literature on making rings into Turing machines? If so, does nilpotence play an important role? | |
| Feb 6, 2015 at 18:25 | comment | added | Burak | If I am not misunderstanding the problem, then it can be stated as a $\Pi_1^1$ statement. If so, this at least means that forcing technique cannot change its truth value. (see the relevant absoluteness result here) | |
| Feb 6, 2015 at 18:16 | comment | added | Per Alexandersson | I was thinking at the same type of problem as Anthony. Also, more similar maybe, given a collection of integer 3x3-matrices, determining if any product of these matrices is the zero matrix, is also undecidable. | |
| Feb 6, 2015 at 18:10 | history | edited | Ricardo Andrade |
edited tags
|
|
| Feb 6, 2015 at 18:06 | comment | added | Anthony Quas | So there are a number of graph theory results saying that problem X is undecidable by showing that a procedure to decide problem X would lead to a procedure to decide problem Y (which is known to be undecidable). One such problem Y that I have used is the problem of deciding whether the plane can be tiled with a given set of Wang tiles (en.wikipedia.org/wiki/Wang_tile). Of course I have no idea whether this is useful in your problem. | |
| Feb 6, 2015 at 17:23 | comment | added | Asaf Karagila♦ | You become a set theorist, and prove that the problem is undecidable! :-) | |
| Feb 6, 2015 at 17:13 | comment | added | Jason Rute | You said "There is always the danger of fearing that a problem one is working on is formally undecidable, just because you can't immediately solve it." The same theory that says there are undecidable problems also says there are really, really difficult problems. I think the fear that one's problem is undecidability and the fear that one's problem is the next Riemann hypothesis are not very different. (Although one can prove that a problem is undecidable. I don't know how to prove that a problem is difficult.) | |
| Feb 6, 2015 at 16:55 | history | asked | Pace Nielsen | CC BY-SA 3.0 |