Timeline for Is the set of undecidable problems decidable?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 6, 2020 at 23:46 | comment | added | Vladimir Reshetnikov | @Eric If I understand your metaphor correctly, you are saying there is essentially only one non-recursively enumerable set (all others can be obtained from it using recursive procedures). This is not the case. There is a very complicated and fascinating hierarchy of different kinds of non-recursively enumerable sets: en.wikipedia.org/wiki/Turing_degree | |
| May 5, 2020 at 7:20 | comment | added | Eric | I guess a succinct summarization of this situation is this: In a non recursively enumerable set there hides an Achilles heels for every recursive theory. One set catches them all - once you find it, you're done. But hard work lies in identifying such a set and proving that it's indeed non recursively enumerable. | |
| May 5, 2020 at 7:14 | comment | added | Eric | Interesting example. This is a concrete case for a set $S$ (the set of $K$'s for which your equation has no solutions over non-negative integers) that is not recursively enumerable but nevertheless is explicitly definable in all (sufficiently strong) recursive theories. Being non recursively enumerable dictates $\exists k\in S$ that can't be proved to be in $S$ in the theory $T$, because otherwise enumeration of all such proofs is an effective way to generate $S$, contradicting $S$ being non recursively enumerable. | |
| Nov 29, 2011 at 4:05 | history | answered | Vladimir Reshetnikov | CC BY-SA 3.0 |