Timeline for Does P contain incomprehensible languages? (TCS community wiki)
Current License: CC BY-SA 3.0
47 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2020 at 9:38 | history | edited | CommunityBot |
Commonmark migration
|
|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Jun 28, 2012 at 14:43 | history | edited | John Sidles | CC BY-SA 3.0 |
Updated link to new wiki
|
| Jun 11, 2012 at 16:00 | history | edited | John Sidles | CC BY-SA 3.0 |
Link to "Does P contain languages whose existence is independent of PA or ZFC?"
|
| May 31, 2012 at 19:57 | history | edited | John Sidles | CC BY-SA 3.0 |
"(TCS community wiki)" appended to title
|
| May 31, 2012 at 19:47 | history | edited | John Sidles | CC BY-SA 3.0 |
Dang. decide -> accept throughout (for disambiguation)
|
| May 31, 2012 at 19:34 | history | edited | John Sidles | CC BY-SA 3.0 |
Addressing a last-minute comment from Philip White. Over and out! ; Post Made Community Wiki
|
| May 31, 2012 at 19:09 | history | edited | John Sidles | CC BY-SA 3.0 |
Summary of comments, and request for conversion to a community wiki.
|
| May 31, 2012 at 15:49 | comment | added | John Sidles | A new answer by Philip White has clarified (for me) a trivial "polylimiting" reduction incomprehensible -> comprehensible that was noted too by Sasho Nikolov and Peter Shor. In light of this trivial reduction, the definition of "strongly incomprehensible" has been suitably amended with a view to preserving the naturality of Q1–Q3. To bring closure to this question, I'll wait until the weekend for further answers / comments, and if the question remains open (as seems likely) it will be converted to a community wiki. Many thanks to all! | |
| May 31, 2012 at 10:13 | history | edited | John Sidles | CC BY-SA 3.0 |
Definitional tuning per Philip White's valuable answer.
|
| May 30, 2012 at 21:59 | answer | added | Philip White | timeline score: 1 | |
| May 30, 2012 at 16:37 | comment | added | John Sidles | The question is now finalized and Sasho Nikolov's answer is "accepted" because it provided a formulation that captured the intent of the question: the answer to the question itself is (apparently) not known. Regarding game-theoretic (or even cryptographic) applications of strong incomprehensibility (if it exists), see the Gödel's Lost Letter weblog topic "Beyond Las Vegas And Monte Carlo Algorithms." My thanks are extended to everyone for their comments and suggestions. | |
| May 30, 2012 at 12:56 | history | edited | John Sidles | CC BY-SA 3.0 |
Sasho Nikolov's answer rated "accepted" -- final adjustments to definitions
|
| May 30, 2012 at 12:52 | vote | accept | John Sidles | ||
| May 30, 2012 at 12:51 | history | edited | John Sidles | CC BY-SA 3.0 |
Sasho Nikolov's answer rated "accepted" -- final adjustments to definitions
|
| May 30, 2012 at 12:50 | vote | accept | John Sidles | ||
| May 30, 2012 at 12:50 | |||||
| May 29, 2012 at 20:15 | history | tweeted | twitter.com/#!/StackCSTheory/status/207565766814478338 | ||
| May 29, 2012 at 16:25 | comment | added | vzn | think there is a big connection between compressibility & class separations incl P vs NP that is not well researched/formulated so far, and not nec exactly using the kolmogorov sense of compressibility. here is an early formulation of this problem, compression of a TM run sequence | |
| May 29, 2012 at 16:14 | comment | added | John Sidles | Also addressing Peter's (excellent) point is Sasho Nikolov's amended answer (below). Like Sasho, further responses on my part with regard to these many tough-but-rich comments and answers will have to wait until tomorrow ... it simply takes a considerable time to understand and integrate them. Thanks again, to everyone. | |
| May 29, 2012 at 16:04 | comment | added | John Sidles | @Peter Shor, your method for (incomprehensible) -> (comprehensible) reduction is intriguing. Since the reduction method requires an non-realizable oracle (to specify k), I will contemplate blocking oracle-dependent reductions by substituting in the definition (promised to halt) -> (provably halts). Needless to say (as noted in my response to Marzio De Biasi) clarifying the definitions associated to this question has been 10X++ more arduous than I originally anticipated ... which qualifies as a valuable lesson-learned ... and that is why I am very grateful to all who are helping. | |
| May 29, 2012 at 15:32 | comment | added | Peter Shor | Your definition is still bad. Given an incomprehensible Turing machine in P, you can turn it into a comprehensible Turing machine in P by putting a timer on it which counts $Cn^k$ steps, and if it doesn't halt by then, stops it and rejects. For any incomprehensible Turing machine in P, there is a $C$ and $k$ which will turn it into a comprehensible Turing machine accepting the same language. Of course, you can't prove that it accepts the same language, and you can't find the right values of C and k, but I don't see how you can incorporate this into your definition. | |
| May 29, 2012 at 14:18 | comment | added | John Sidles | @ Marzio De Biasi, your suggestion is excellent, and so I have added it to the queue of amendments for tomorrow's edited version of the question, which (hopefully) will be the final, rigorous posing of the question. Many thanks to everyone, for help in posing the question rigorously and clearly. | |
| May 29, 2012 at 13:55 | comment | added | Marzio De Biasi | @JohnSidles: reading the last version of your question: why don't you get rid of the word "question" and use something like this: "... M is called incomprehensible in T iff the following statement is neither provable nor refutable in T for at least one positive semidefinite real number r: "$M$'s runtime is $O(n^r)$" (Gödel's First Incompleteness Theorem is completely unconcerned with the question of truth). | |
| May 29, 2012 at 13:24 | answer | added | Marzio De Biasi | timeline score: 2 | |
| May 29, 2012 at 13:04 | history | edited | John Sidles | CC BY-SA 3.0 |
Tightened notation, more references, "neither provable nor refutable" substituted for "decidable".
|
| May 29, 2012 at 11:49 | comment | added | John Sidles | Per Sasho's answer (below), and in accord with Wikipedia conventions, another edit in the queue will disambiguate the word "undecidable" with respect to its proof-theoretic versus computability-theoretic senses, via the substitution (undecidable) -> (independent). | |
| May 29, 2012 at 5:43 | answer | added | Sasho Nikolov | timeline score: 11 | |
| May 29, 2012 at 3:18 | comment | added | John Sidles | @Huck Bennett, per your post and Raphael's example, everyone is clear that the question at the focus of the definition---namely "Is M's runtime O(n^r) with respect to input length n?"---has a computable answer (that answer being either "yes" or "no", both of which are computable). But the definition is not concerned with the answer's computability, but rather the answer's decidability. And as I read Viola's construction, instances of an (undecidable) halting problem are uniformly reduceable to instances of a runtime exponent problem (hence also undecidable). | |
| May 29, 2012 at 3:12 | comment | added | user6973 | Since "Is $M$'s runtime $O\left(n^r\right)$ with respect to input length $n$ ?" binds $n$ and its decidability is being asked about separately for each $M$ and $r$, that question will be automatically always decidable. $\:$ Accordingly, there will be no incomprehensible Turing machines under the definition given in the OP (as mentioned by Tsuyoshi). $\:$ Since I don't find this question interesting enough to read Viola's paper to find out what he actually said, I probably won't be making another comment here. $\;\;$ | |
| May 29, 2012 at 2:44 | comment | added | Huck Bennett | @JohnSidles: I think (referencing Rafael's revision) the reduction shows that the language P (not the best letter choice) is undecidable, and does not give an explicit TM for which "run time bounds in P" is undecidable. M* (not fixed) is part of the input. | |
| May 29, 2012 at 1:31 | comment | added | John Sidles | @Sasho Nikolov, per your and Tsuyoshi Ito's remarks, tomorrow's edit of the question will note that Emmanuele Viola's method constructs an explicit TM for which the question "Is the runtime O(n^2)?" is undecidable. The TM that Viola gives is---by the definition given---incomprehensible and thus the set of incomprehensible TMs is non-empty. If you (or anyone) feels that this point requires further explanation or correction ... well ... please provide that explanation or correction as an answer! | |
| May 29, 2012 at 0:33 | comment | added | Tsuyoshi Ito | You did not address the flaw which I pointed out at all. To repeat myself: According to the current definition (revision 6), every Turing machine is “comprehensible.” Both Sasho and I already explained this. And please do not expect that I will read further comments. | |
| May 29, 2012 at 0:25 | comment | added | John Sidles | @Tsuyoshi Ito, after (1) carefully reviewing the link you provided, and (2) further reviewing Hartmanis' monograph Feasible Computations and Provable Complexity Properties (1978), and finally (3) scrupulously embracing the definitions and notational conventions of Arora and Barak's Computational Complexity: a Modern Approach (2009), it is my present impression that the questions-asked and definitions-provided reasonably satisfy all criteria of the TCS StackExchange charter. If in your opinion flaws remain, please describe them in a comment, and I will do my best to address them. | |
| May 29, 2012 at 0:09 | comment | added | John Sidles | Progress: changes in-the-pipeline for an edit tomorrow (Tuesday) are: (1) amend the notation to match Arora and Boas by substituting "recognized" -> "decided", and (2) in the sentence after Q1 substitute "incomprehensible" -> "strongly incomprehensible" so as to read: "Assuming Q1 is true, we call the languages in this subset of P strongly incomprehensible languages and similarly TMs that decide these languages are called strongly incomprehensible TMs." Then in Q2 and Q3 substitute "incomprehensible" -> "strongly incomprehensible". Further suggestions are welcome, needless to say! | |
| May 28, 2012 at 19:48 | comment | added | John Sidles | @Sasho Nikolov especially ... TCS StackExchange colleagues, we are at-risk of falling out of phase, in that I have just finished responding to Sasho's most recent comment! In particular, it appears that Sasho and I may have been speaking to mutually converse (hence mutually independent) implications---hopefully the most recent version (which features "Viola's implication") has clarified this point. It seems like a good idea to let further comments accumulate until tomorrow morning, rather than deal with them one-by-one. Please let me thank everyone for good comments. | |
| May 28, 2012 at 19:42 | history | edited | John Sidles | CC BY-SA 3.0 |
Edited yet again per Sasho's comment
|
| May 28, 2012 at 19:34 | history | edited | John Sidles | CC BY-SA 3.0 |
Edited per Sasho's comment
|
| May 28, 2012 at 19:19 | comment | added | Tsuyoshi Ito | As Sasho explained preemptively, the problem stated in the definition of “incomprehensible” in revision 4 is decidable for every M. I am afraid that you are making an elementary error here. If you still have trouble understanding it, this post by Raphael and the link in it may be helpful. I voted to close this as not a real question. | |
| May 28, 2012 at 19:15 | comment | added | John Sidles | @Ito (and Sasho), thank you for your inputs. The definitions and phrasing of the question have been amended so that it is now (hopefully) well-posed ... please suggest any further adjustments as needed. | |
| May 28, 2012 at 19:10 | history | edited | John Sidles | CC BY-SA 3.0 |
Further clarification in response to Tsuyoshi Ito's questions!
|
| May 28, 2012 at 19:09 | comment | added | Tsuyoshi Ito | @Sasho Nikolov: I agree. I guess that it is a common error to interpret the undecidability of a problem as existence of an “undecidable instance” of the problem. | |
| May 28, 2012 at 19:04 | comment | added | Sasho Nikolov | The definition makes no sense, I am afraid. Viola's reduction shows that when the Turing machine is part of the input together with $r$, its running time is undecidable. But if we take the Turing machine out of the input and fix a language for any Turing machine, then the problem becomes decidable (because we're allowed to construct a deciding TM specifically for a Turing machine $M$). | |
| May 28, 2012 at 18:49 | comment | added | Tsuyoshi Ito | In the problem stated in the definition of “incomprehensible in P,” what exactly is the input? Is the Turing machine part of the input or fixed? In addition, how is a real number specified as a string? | |
| May 28, 2012 at 18:48 | history | edited | John Sidles | CC BY-SA 3.0 |
Minor edit to improve readability
|
| May 28, 2012 at 18:43 | history | edited | John Sidles | CC BY-SA 3.0 |
Clarification as requested by Tsuyoshi Ito
|
| May 28, 2012 at 18:08 | comment | added | Tsuyoshi Ito | Please define the term “(a Turing machine) being decidably in P.” | |
| May 28, 2012 at 17:55 | history | asked | John Sidles | CC BY-SA 3.0 |