Timeline for What are the most attractive Turing undecidable problems in mathematics?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 18, 2020 at 14:09 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
minor typos
|
| Jun 18, 2013 at 20:47 | comment | added | usul | @Christoph - no, Rice's theorem says we cannot decide nontrivial things about a the language of a program, but #1,3,4 do not deal with the program's language and #2 does not get programs as input. | |
| Mar 7, 2013 at 21:41 | comment | added | Christoph-Simon Senjak | Aren't these just special cases of Rice's Theorem? | |
| Jan 13, 2010 at 13:18 | comment | added | Joel David Hamkins | I don't find it a flaw to be close to or equivalent to the halting problem. After all, in a robust sense I think all the answers posted here so far are equivalent to the Halting problem, in the sense of Turing equivalence. Undecidability in the cases of the answers is established ultimately by reducing the Halting problem to the given problem, and conversely, for each problem one can reduce it to the Halting problem. So all the posted problems have the same Turing degree as the Halting Problem. | |
| Jan 12, 2010 at 19:43 | history | answered | Mark Biggar | CC BY-SA 2.5 |