<p>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.</p>

CC BY-SA 3.0
2014-12-10T08:55:26.340Z
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.
XL _At_Here_There
CC BY-SA 3.0
2014-12-10T08:58:46.780Z
Your question stated "...program *of finite length* that outputs...". What representations are you interested in in particular?
Tom van der Zanden
CC BY-SA 3.0
2014-12-11T00:28:30.450Z
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.
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T02:19:35.910Z
I have known how to express the question now. Thank you.
XL _At_Here_There
CC BY-SA 3.0
2014-12-10T08:42:15.177Z
2014-12-10T08:42:15.177Z
Tom van der Zanden
<p>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. </p>

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

CC BY-SA 3.0
2014-12-10T18:05:09.387Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-12-11T00:25:16.320Z
@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
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T00:34:56.853Z
What is the input and what is the output to your problem? The time should be bounded by a polynomial in what parameter?
Sasho Nikolov
CC BY-SA 3.0
2014-12-11T00:38:50.787Z
@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"
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T00:48:13.593Z
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?
Sasho Nikolov
CC BY-SA 3.0
2014-12-11T01:10:08.767Z
@SashoNikolov, the output would be the infinite bits in sequence of $\sqrt{2}$, or the expansion in the base of 10 or 2. In order to compare the two representation, we have to require the output be in finite sequence of bits ,which means the output is in required precision $\leq \epsilon$. The computational complexity and computation model is the same as in Computable Analysis. Okay, thank you for your comment, I know I have omitted some background. The polynomial time is related to the length of input or representation. Now, I have known the question may be relating to some deep open problem.
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T01:17:05.710Z
@SashoNikolov, Now, I have known the question may be relating to some deep open problems, like the one presented by Stearns and Harmanis in 1965
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T01:26:17.593Z
@SashoNikolov, sorry, I have made a mistake in the comments. the inputs is one of the representation, and the output is another representation, both of them are of finite length. The algorithms convert one to another. Are there $P$ time  algorithms (the input length is the parameter of the complexity)that convert one to another? both representations can be computed to output the infinite  or finite( if the expansion of number is finite) sequence of the number. Both [to be continued]
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T01:29:34.260Z
[cont] representation is finite and can be computed to output the infinite or finite (if the expansion of the number is finite)sequence of bits of the number, that is it is a computable number.
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T02:18:32.283Z
@SashoNikolov, I have known how to express what I want to know. I will reprase it and post it as another question.
XL _At_Here_There
CC BY-SA 3.0
2014-12-11T03:34:13.913Z
Let me repeat this one last time: to talk of a computational problem and polynomial time you need an infinite class of inputs, each with a required output. Two finite representations do not make an infinite class of inputs.
Sasho Nikolov
<cc.complexity-theory><reference-request><computable-analysis>
For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another
XL _At_Here_There
# For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another

(Asked by: username_0 on 2014-12-10)

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?

**Tags:** cc.complexity-theory, reference-request, computable-analysis

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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  
> **username_1**: What is the input and what is the output to your problem? The time should be bounded by a polynomial in what parameter?  
> **username_0**: @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"  
> **username_1**: 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?  
> **username_0**: @SashoNikolov, the output would be the infinite bits in sequence of $\sqrt{2}$, or the expansion in the base of 10 or 2. In order to compare the two representation, we have to require the output be in finite sequence of bits ,which means the output is in required precision $\leq \epsilon$. The computational complexity and computation model is the same as in Computable Analysis. Okay, thank you for your comment, I know I have omitted some background. The polynomial time is related to the length of input or representation. Now, I have known the question may be relating to some deep open problem.  
> **username_0**: @SashoNikolov, Now, I have known the question may be relating to some deep open problems, like the one presented by Stearns and Harmanis in 1965  
> **username_0**: @SashoNikolov, sorry, I have made a mistake in the comments. the inputs is one of the representation, and the output is another representation, both of them are of finite length. The algorithms convert one to another. Are there $P$ time  algorithms (the input length is the parameter of the complexity)that convert one to another? both representations can be computed to output the infinite  or finite( if the expansion of number is finite) sequence of the number. Both [to be continued]  
> **username_0**: [cont] representation is finite and can be computed to output the infinite or finite (if the expansion of the number is finite)sequence of bits of the number, that is it is a computable number.  
> **username_0**: @SashoNikolov, I have known how to express what I want to know. I will reprase it and post it as another question.  
> **username_1**: Let me repeat this one last time: to talk of a computational problem and polynomial time you need an infinite class of inputs, each with a required output. Two finite representations do not make an infinite class of inputs.  

---

## 1 answers

### Answer by username_2 on 2014-12-10. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: Your question stated "...program *of finite length* that outputs...". What representations are you interested in in particular?  
> **username_0**: 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.  
> **username_0**: I have known how to express the question now. Thank you.  

---

