Timeline for Hard-to-compute real numbers
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 21, 2016 at 19:49 | vote | accept | Mohammad Al-Turkistany | ||
| Oct 21, 2016 at 18:36 | comment | added | Mohammad Al-Turkistany | I think you answered the original question in my post. | |
| Oct 21, 2016 at 17:44 | comment | added | Noah Schweber | @MohammadAl-Turkistany I'm not sure what "a polynomial bound on the number of incorrectly computed bits" means. We have one function, and one real - if the real is incomputable, the function gets infinitely many bits wrong: is that polynomial or not? (Are you asking something about the proportion of bits $f$ guesses correctly?) | |
| Oct 21, 2016 at 17:02 | comment | added | Mohammad Al-Turkistany | Oops. I suggest a polynomial bound on the number of incorrectly computed bits. Is that still trivial? | |
| Oct 21, 2016 at 16:58 | comment | added | Noah Schweber | @MohammadAl-Turkistany If you allow it to compute some bits incorrectly, then - as I wrote in my answer above - every real is easily computed. So you need to give some more restriction in order for that question to not be trivial. | |
| Oct 21, 2016 at 16:57 | comment | added | Mohammad Al-Turkistany | I mean it may compute some of the bits incorrectly. | |
| Oct 21, 2016 at 16:54 | comment | added | Noah Schweber | @MohammadAl-Turkistany What do you mean by "compute it's digits", if you're not asking to compute all the digits? As I wrote in my answer, you have to be very precise here, otherwise the question trivializes. Are you asking for a natural real with high (polytime) Kolmogorov complexity, or something else? | |
| Oct 21, 2016 at 16:51 | comment | added | Mohammad Al-Turkistany | Are you aware of any natural real number that is very hard to compute its digits ( not necessarily all the digits)? | |
| Oct 21, 2016 at 16:38 | comment | added | Noah Schweber | Note that this trick does not allow me to tell if a given TM runs in polynomial time: rather, it just gives me a list of new TMs $\psi_i$, each of which runs in polynomial time, such that every polytime $\varphi_m$ is equivalent to some $\psi_i$. It's these that I diagonalize against. Note that this same trick works for much broader classes - e.g. it lets me diagonalize against all the exponential-time computable functions. | |
| Oct 21, 2016 at 16:37 | comment | added | Noah Schweber | @MohammadAl-Turkistany That's true - which is why that's not what I did. I listed all TMs, as well as all polynomials, and looked at "cut-off TMs": the $\langle i, j\rangle$th "cut-off TIM" is the TM you get by taking the $i$th TM and forcing it to halt in $p_j$-many steps (where $p_j$ is the $j$th polynomial). Recall the definition of $r$: "the $n$th bit of the binary expansion of $r$ is a $1$ iff $\varphi_i(n)$ does not halt and output $1$ in $\le p_j(n)$ steps". At no point do I need to know if a machine runs in polytime - I just look at the first few steps of the computation. | |
| Oct 21, 2016 at 16:35 | comment | added | Mohammad Al-Turkistany | This post shows that deciding whether a TM runs in polynomial time is undecidable. So a list of all polynomial time computable TM's does not exist. Right.? cstheory.stackexchange.com/questions/5004/… | |
| Oct 21, 2016 at 16:28 | comment | added | Noah Schweber | @MohammadAl-Turkistany I have edited my answer to comment on the different versions of the question you ask (see the beginning and end sections). | |
| Oct 21, 2016 at 16:27 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 2490 characters in body
|
| Oct 21, 2016 at 15:05 | comment | added | Noah Schweber | @MohammadAl-Turkistany See my last paragraph before the line. No algorithm running in polynomial time correctly computes every bit of this real - in particular, if the $i$th algorithm runs in time bounded by the $j$th polynomial, then it gets the $\langle i, j\rangle$th bit wrong. This is an instance of a very general and powerful technique - diagonalization. | |
| Oct 21, 2016 at 15:04 | comment | added | Mohammad Al-Turkistany | May be I am missing something but I don't see why your real number is hard to compute? | |
| Oct 21, 2016 at 14:44 | history | answered | Noah Schweber | CC BY-SA 3.0 |