is there an algorithm that generates the continued fraction of a product of convergent continued fractions? I understand that there are algorithms (eg a famous one by Gosper) that generate, from certain pairs of continued fractions a, b, the continued fraction of the product. 
I'm guessing that this algorithm only works for arguments with finite expansions, since I also read that these algorithms fail to generate 2 = [2;0,0,0,0,...] for the product of sqrt(2) = [1;2,2,2,2,...] with itself. I have a vague understanding of why they fail for this case, but I don't understand enough to know if this is a limitation of certain particular algorithms for if it is generally impossible to find an algorithm that generates the continued fraction of the product of any (i.e. possibly infinite, convergent) continued fractions.
 A: The answer is that no such algorithm can exist, because having such an algorithm lets you solve the halting problem.
For example, given a computer program $n$, you can write a computable continued fraction $[a_0,a_1,\dots]$ where $a_0=1$ and for $k>0,$ $a_k=2$ unless the program halts at step $n$ or earlier, then $a_k=2+(-1)^{k-1}$ (chosen so the resulting real number is $\leq \sqrt{2},$ with equality only when the program does not halt.)
Your algorithm would let us multiply this by $\sqrt{2}=[1,2,2,\dots]$ and we'd be able to solve the halting problem by whether the resulting continued fraction was $\geq 2$ or not.

Basically, your algorithm would have to "know" in a finite amount of time, and hence after perusing only a finite number of coefficients, whether a continued fraction would $\geq \sqrt{2}$. ($\sqrt{2}$ here is not special, just an easy example.)

It's almost trivially true, actually, that you can't figure out in finite time that a continued fraction is $\geq \sqrt{2}$. Presumably, we aren't even given an algorithm, just a stream of coefficients for our number $\alpha,$ so if $\alpha$ is actually $\sqrt{2}$, at what point do we figure out that $\sqrt{2}\alpha\geq 2$? If the algorithm figures this out after reading $n$ coefficients, then we can find infinitely many numbers $\beta<\sqrt{2}$ that agree with $\sqrt{2}$ in those coefficients, and thus will likewise return the same value.

I believe that if you can solve the halting problem (say, you are given an Oracle which solves it,) then you solve effective multiplication and addition of continued fractions. That is, you can write a program which:


*

*Takes two programs (which do not use the oracle) as input, which are interpreted as outputing two continued fractions.

*Outputs (using the oracle) a sequence of coefficients that represent the product (or sum.)

