1
$\begingroup$

A real $r$ is computable if given any $i\in \mathbb{N}$, the $i$th bit can be outputed by a Turing Machine or an algorithm. So, what is computational complexity or complexity measure of computing the real? Since there is just a Turing Machine or a program without input,

what is the computational complexity or complexity measure of computing reals?

Any definition and result? Intuitively, the computational complexity or complexity measure may be defined in terms of the size of output, like length of the binary sequence of the outputed real.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Computable_number $\endgroup$
    – Victor
    Commented Oct 30, 2014 at 6:57
  • 1
    $\begingroup$ According to your definition it sounds like different Turing machines could be picked for different $i$, and then every real would be "computable". The above link to wikipedia says: "A computable number [is] one for which there is a Turing machine which, given n on its initial tape, terminates with the n-th digit of that number [encoded on its tape]." So the same Turing machine should work for that $r$, and given $i$ that Turing machine would tell you the first $i$ digits. $\endgroup$
    – Mirko
    Commented Oct 30, 2014 at 9:44
  • 3
    $\begingroup$ I did not interpret XL's definition differently from Minsky's definition. Note that Wikipedia correctly goes on to say that this is not the definition that is most commonly used today. $\endgroup$
    – Timothy Chow
    Commented Oct 30, 2014 at 15:29

1 Answer 1

Reset to default
3
$\begingroup$

This is interesting. I think a number could be of low complexity in terms of approximating it to within smaller and smaller $\epsilon $, while of high complexity in terms of finding its binary representation. Just imagine that its binary representation has extremely long stretches of 0s (and/or 1s) so the number is unusually close to dyadic rationals in a sense.

You may find something about this in Chapter 7 of Weihrauch's book Computable Analysis.

Improve this answer
$\endgroup$
10
  • 3
    $\begingroup$ Yes. Many people's first instinct is to use XL's definition, but it has rather nasty properties. For example, even to show that $\pi$ is computable is difficult with XL's definition, because you have to prove a computable bound on the length of a stretch of 1's, and that requires some nontrivial diophantine analysis. In contrast, approximating $\pi$ to within $\epsilon$ is a much easier problem. So that is the definition that is usually used, and there are many results about that; Weihrauch's book is a fine reference. However, if XL really wants $i$ bits, then much less is known. $\endgroup$
    – Timothy Chow
    Commented Oct 30, 2014 at 15:25
  • 2
    $\begingroup$ To add to Timothy Chow’s comment: I believe that for typical numbers known to be efficiently approximable (e.g., numbers expressible using elementary functions and polynomial roots), we expect bits of the number can be computed in asymptotically the same time bound, as stretches of 1’s can’t get overwhelmingly long. The problem is that apart from a handful of simple cases, we don’t know how to prove that. So in a sense, the distinction doesn’t affect much algorithmic complexity per se, but rather the difficulty of analyzing the algorithms, which may be one reason to avoid XL’s definition. $\endgroup$
    – Emil Jeřábek
    Commented Oct 30, 2014 at 17:21
  • $\begingroup$ The definition is relevant to Kolmogorov complexity,since the precondition of the definition requires that the length of the program or the description of the Turing Machine is finite. If we don't require such a precondition,every number is computable. so, we have to have some requirements on the length of the finite program or $TM$, since there are variant length of programs or algorithms to compute the same number .Comparing this with the approximation definition, we know we have to have requirements on the length of the approximation algorithm or length of representation [to be cont] $\endgroup$
    – XL _At_Here_There
    Commented Oct 31, 2014 at 1:03
  • $\begingroup$ [cont]For example, we know algebraic irrational number can computed by different representations like it's continued fraction or formula in term of modular function, only when we prove all different representations are irrelevant to computational complexity or other complexity measure,can we define the computational complexity or other complexity as the complexity of the algorithm, otherwise we have different complexity of the same computing algorithm for same computed number. That is irrational. $\endgroup$
    – XL _At_Here_There
    Commented Oct 31, 2014 at 1:18
  • 1
    $\begingroup$ @EmilJeřábek, if I think you have misunderstood what I say in the comment at you. the classic computational complexity is about ,say, language or defined in term of language. definition of complexity in approximation is defined in the term of approximation like $\leq \epsilon$, How could the results or problem of the classic computational complexity like $P = NP$ be link to definition of complexity in approximation? I mean translation of interpretation of each other, it has no thing to do with Kolmogorov complexity. $\endgroup$
    – XL _At_Here_There
    Commented Nov 2, 2014 at 1:09

Not the answer you're looking for? Browse other questions tagged .