Timeline for Existence of unknowable algorithms ?
Current License: CC BY-SA 3.0
31 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 22 at 21:47 | history | edited | Joel David Hamkins |
edited tags
|
|
| May 26, 2023 at 15:42 | comment | added | The Amplitwist | Reposting some links mentioned in a couple of comments above, so that they appear in the "Linked" questions list: (1) Joel David Hamkins's answer to "Can a problem be simultaneously polynomial time and undecidable?"; (2) "The generalized word problem vs. the uniform generalized word problem". | |
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Jan 24, 2019 at 16:45 | comment | added | Qfwfq | Probably related: mathoverflow.net/questions/74941/… (Even though, when I asked the question, I mistakingly used the term "undecidable" to actually mean "independent from the axioms of ZFC"). | |
| Jan 24, 2019 at 10:01 | answer | added | j.p. | timeline score: 0 | |
| Jan 24, 2019 at 5:38 | answer | added | Christopher King | timeline score: 1 | |
| Apr 10, 2013 at 2:26 | comment | added | Andreas Blass | I conjecture you haven't understood Goldstern's example, because you wrote "Either Q is indecidable in ZFC and we cannot prove, in ZFC, the existence of an algorithm answering it ..." Even if ZFC neither proves nor refutes Q, it still proves that one of Goldstern's two proposed algorithms works. Since ZFC is based on classical logic, it proves "either 'yes' is a correct answer to Q or 'no' is", even when it cannot decide between the two alternatives. | |
| Apr 9, 2013 at 7:42 | vote | accept | Loïc Teyssier | ||
| Apr 8, 2013 at 15:07 | answer | added | Timothy Chow | timeline score: 0 | |
| Apr 8, 2013 at 8:03 | history | edited | Loïc Teyssier | CC BY-SA 3.0 |
added 2810 characters in body; added 2 characters in body
|
| Apr 8, 2013 at 6:38 | comment | added | Loïc Teyssier | @Joel: I think giving an explicit example of a random real number (in the sense of Martin-Löf) might be such an example. The generic real number is random, while at the same time it is impossible by definition to express it in finite terms. | |
| Apr 7, 2013 at 4:27 | answer | added | Timothy Chow | timeline score: 14 | |
| Apr 7, 2013 at 2:02 | comment | added | Benjamin Steinberg | Perhaps what he wants is an example of a problem with both a uniform version and a non-uniform version where the non-uniform version is solvable in every instance but the uniform problem is undecidable. This is what Peter Shor does. See also my old question mathoverflow.net/questions/72197/… | |
| Apr 6, 2013 at 17:41 | comment | added | François G. Dorais | This is a question for which an answer is obvious once it is made sufficiently precise, but every answer feels like a cheat if one hasn't gone through the process of clarifying the question. I guess that means that there is an algorithm to answer this question but there is no way to recognize this algorithm? | |
| Apr 6, 2013 at 16:53 | answer | added | Peter Shor | timeline score: 12 | |
| Apr 6, 2013 at 15:18 | comment | added | Andreas Blass | I agree with Joel that we need to know more precisely what you intend by "intrinsic formal impossibility" to know something. If it just means undecidability in ZFC (or ZFC plus some specific large cardinals), then Goldstern's answer works if we take the question Q to be something like CH that is undecidable in such theories. But if you intend the possibilities for knowledge to extend beyond provability in such formal systems, then it's not so clear what those possibilities are, nor even whether there would be anything at all that is intrinsically unknowable. | |
| Apr 6, 2013 at 15:08 | comment | added | Kaveh | See cstheory.stackexchange.com/questions/12162/… | |
| Apr 6, 2013 at 14:47 | comment | added | Joel David Hamkins | Regarding your edit, could you give us any example of the kind of situation you are describing, a context for which there is a definite fact of the matter which we are unable in principle to know? Your question is asking for such an example in the context of algorithms---you want that one program among many is definitely the right one, but we are unable in principle to say which one---but it seems not so easy to give truly convincing examples of this phenomenon at all, even apart from algorithms. | |
| Apr 6, 2013 at 14:43 | history | edited | Loïc Teyssier | CC BY-SA 3.0 |
edited body
|
| Apr 6, 2013 at 14:37 | history | edited | Loïc Teyssier | CC BY-SA 3.0 |
added 605 characters in body
|
| Apr 6, 2013 at 13:26 | comment | added | Benjamin Steinberg | The rough answer that all the answers have in common is that if some piece of information is guaranteed to be finite then there is a Turing machine that has this information preprocessed and can do anything algorithmic with this information. But if you don't know explicitly this information then you will not be able to explicitly write down the Turing Machine. | |
| Apr 6, 2013 at 9:06 | vote | accept | Loïc Teyssier | ||
| Apr 6, 2013 at 9:07 | |||||
| Apr 6, 2013 at 9:01 | comment | added | Loïc Teyssier | I'm sorry not to have found those threads when I looked up for related questions. As I said I miss the standard vocabulary and didn't realize those items would answer my question. | |
| Apr 5, 2013 at 22:49 | comment | added | Quinn Culver | A keyword here is uniformity. | |
| Apr 5, 2013 at 16:46 | comment | added | Joel David Hamkins | See also mathoverflow.net/questions/48014/…. | |
| Apr 5, 2013 at 16:44 | answer | added | Joel David Hamkins | timeline score: 16 | |
| Apr 5, 2013 at 16:23 | comment | added | Emil Jeřábek | This question largely duplicates mathoverflow.net/questions/14918/… . | |
| Apr 5, 2013 at 15:20 | answer | added | Goldstern | timeline score: 11 | |
| Apr 5, 2013 at 14:53 | answer | added | Noah Stein | timeline score: 10 | |
| Apr 5, 2013 at 14:52 | answer | added | user6976 | timeline score: 15 | |
| Apr 5, 2013 at 14:35 | history | asked | Loïc Teyssier | CC BY-SA 3.0 |