-1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Dec 10 '14 at 18:05
  • $\begingroup$ @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 $\endgroup$ – XL _at_China Dec 11 '14 at 0:25
  • $\begingroup$ What is the input and what is the output to your problem? The time should be bounded by a polynomial in what parameter? $\endgroup$ – Sasho Nikolov Dec 11 '14 at 0:34
  • $\begingroup$ @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" $\endgroup$ – XL _at_China Dec 11 '14 at 0:38
  • 1
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Dec 11 '14 at 0:48
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – XL _at_China Dec 10 '14 at 8:55
  • $\begingroup$ Your question stated "...program of finite length that outputs...". What representations are you interested in in particular? $\endgroup$ – Tom van der Zanden Dec 10 '14 at 8:58
  • $\begingroup$ 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. $\endgroup$ – XL _at_China Dec 11 '14 at 0:28
  • $\begingroup$ I have known how to express the question now. Thank you. $\endgroup$ – XL _at_China Dec 11 '14 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.