# For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another

Any computable number may have different representations of finite length . For example,$\sqrt{2}$ may be represented as root of equation, or as a (shortest for a universal Turing Machine)program of finite length that outputs every bit sequently in infinite time.

For two representations of finite length of one computable number, are there $P$-time algorithms that compute one from another?

• This is not a well-posed question. Obviously for any two finite strings $x$ and $y$ there is a Turing machine that on input $x$ outputs $y$ in finite time. "Polynomial time" only makes sense for an infinite family of inputs. Dec 10, 2014 at 18:05
• @SashoNikolov, no, you know, " Obviously for any two finite strings x and y there is a Turing machine that on input x outputs y in finite time. "Polynomial time" only makes sense for an infinite family of inputs.", but are you sure the time is polynomial? And is the time relating to the computation? So, I don't think it is not a well-posed question. we have to know that the computational complexity of number is linked to the computation of the number in an intrinsic way, otherwise, all definition is meaningless Dec 11, 2014 at 0:25
• What is the input and what is the output to your problem? The time should be bounded by a polynomial in what parameter? Dec 11, 2014 at 0:34
• @SashoNikolov, The representations is the input, the output is the bits in sequence of the number, and the time has to be bounded by the polynomial in the length of input ,namely the representations. Please see Computable Analysis for reference. And the word representations is not equivalent to "representation" in "representation theory" Dec 11, 2014 at 0:38
• Still not clear. Given two representations of $\sqrt{2}$ as input, what does the algorithm need to output? Your comment seems to say it needs to output the $n$-th bit of $\sqrt{2}$ in time polynomial in $n$, but this can be done while completely ignoring the representations, so what do they have to do with anything? Dec 11, 2014 at 0:48

No, it is undecidable. Imagine a TM that outputs a sequence $0.1111\ldots$ that may be finite or not. If it is finite, the conversion algorithm should give some fraction like $\frac{11\ldots11}{10\ldots000}$. If it is infinite (the TM doesn't halt) then the output should be $\frac{1}{9}$. Any program that converts between the $TM$ representation of a number and a fraction would be able to decide the halting problem.
• Thank you for your answer, but what I wonder is whether for two different representations of any same number that are of finite length,there is $P-$time algorithm convert from one to other. Dec 10, 2014 at 8:55
• No, I ask "For two representations of finite length of one computable number, are there P-time algorithms that compute one from another?" which has stressed "two representations of finite length of one computable number" and have given an example,that is $\sqrt{2}$. You may read it again. Dec 11, 2014 at 0:28