Timeline for Hard-to-compute real numbers
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 21, 2016 at 16:02 | comment | added | Wojowu | @MohammadAl-Turkistany First let me second a comment which Noah Schweber made above - if we want, for every $n$, a machine which outputs the $n$th digit of our number, where for every $n$ this machine can be different, then we can always choose one of two suitable machines and be happy with polynomial time. If we want a single machine which works for all $n$, then, as Chaitin's constant is uncomputable, there is no such machine, let alone a polynomial time one! | |
| Oct 21, 2016 at 15:58 | comment | added | Mohammad Al-Turkistany | I know about $\Omega$ but I have not seen any proof that computing the $n$-th digit needs more than a polynomial function in $n$. | |
| Oct 21, 2016 at 14:18 | history | edited | T. Amdeberhan | CC BY-SA 3.0 |
deleted 3 characters in body
|
| Oct 21, 2016 at 13:51 | history | answered | T. Amdeberhan | CC BY-SA 3.0 |