Timeline for Can a problem be simultaneously polynomial time and undecidable?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 28, 2011 at 13:13 | comment | added | John Sidles | @Joel, a link to this fine answer has been added to the TCS StackExchange question "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?" ... I wish to thank Alex ten Brink for drawing attention to this answer. | |
| Dec 3, 2010 at 4:10 | comment | added | Taylor Sutton | This reminds me of a very similar problem on a problem set I once did regarding the definition of decidability of a language. The problem was this: Let L = {0} if there is life in the universe outside our solar system, and L = {1} if the only life in the universe is inside our solar system. Then the question is: is L decidable? | |
| Dec 3, 2010 at 1:48 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
Added bit about uniformity
|
| Dec 2, 2010 at 17:03 | comment | added | Joel David Hamkins | Frank, I had the interpretation that if you have fifteen consecutive $7$s, then the first eleven of them would count as eleven consecutive $7$s. So the function really would be as I describe it. Otherwise, I suppose, one should speak of *maximal* consecutive sequences of $7$s, and I believe that it is an open question whether the corresponding function is computable. (Although if $\pi$ is normal, then this function also would be identically $1$.) | |
| Dec 2, 2010 at 16:04 | comment | added | Qiaochu Yuan | @Frank: doesn't that mean the same thing? | |
| Dec 2, 2010 at 13:58 | comment | added | Mariano Suárez-Álvarez | This is like the ${\sqrt 2}^{\sqrt 2}$ example. | |
| Dec 2, 2010 at 11:00 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |