Timeline for Is the set of undecidable problems decidable?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 29, 2011 at 4:05 | answer | added | Vladimir Reshetnikov | timeline score: 8 | |
| Nov 24, 2011 at 7:15 | vote | accept | Abel Molina | ||
| Nov 20, 2011 at 22:20 | answer | added | François G. Dorais | timeline score: 13 | |
| Nov 20, 2011 at 20:11 | answer | added | David Feldman | timeline score: 2 | |
| Nov 20, 2011 at 17:04 | comment | added | boumol | This set in non-computable. Why? Let us suppose that the set of independent statements is computable. Then, so is its complement, i.e., the set of formulas $\varphi$ such that either $ZFC \vdash \varphi$ or $ZFC \vdash \neg \varphi$. Using this it easily follows that the set of consequences of ZFC is decidable, which is well-known to be false. | |
| Nov 20, 2011 at 16:59 | comment | added | boumol | Perhaps it is worth clarifying that the term "undecidable" refers to "independece in ZFC", while the term "decidable" refers to "computable (also called recursive)" | |
| Nov 20, 2011 at 16:27 | comment | added | Asaf Karagila♦ | I think that this was addressed somewhere on math.stackexchange.com however, I cannot find it. | |
| Nov 20, 2011 at 15:23 | history | asked | Abel Molina | CC BY-SA 3.0 |