5
$\begingroup$

Suppose I have an algorithm $F$ that, given a numeric input $x$, generates an infinite sequence of numbers that converges to a $f(x)$, where $f$ is some continuous real-valued function.

Similarly, I have an algorithm $G$ that, given a numeric input $y$, generates an infinite sequence of numbers that converges to $g(y)$, where $g$ is another continuous real-valued function.

I would like to have an algorithm $H$ that, given $x$, generates an infinite sequence of numbers that converges to $g(f(x))$. How can I do this?

My current idea is as follows. For every algorithm $A$ and integer $i$, let $A_i(x)$ be the $i$-th value in the sequence returned by algorithm $A$ when run on input $x$.

Then, the algorithm $H$ should return the sequence:

$$G_i(F_i(x))$$

Initially, $H$ runs a single step of $F$ on $x$ and runs a single step of $G$ on the result. Then, $H$ runs two steps of $F$ on $x$ and runs two steps of $G$ on the result. This goes on infinitely.

Is this idea correct? Is there a better idea?

$\endgroup$
  • $\begingroup$ Should one assume that $x$ and $y$ are numbers. What kind? What are the numbers generated (natural numbers, or reals, or computable reals, or ...). How are they represented? What do you mean precisely by converge. In the realm of algorithms and computability, this kind of precision matters. --- --- Running infinite computations and giving them meaning is also something to handle with care. It is often safer mathematically to consider a function $F(x,i)$ which computes in finiate time what you call $F_i(x)$. That can be handled by usual Turing machines. $\endgroup$ – babou Jul 22 '15 at 22:25
  • 1
    $\begingroup$ You need more assumptions on the convergence for there to be any hope of an algorithm. As a counterexample for your specific suggestion, let $F_i(x) = 1/i$ and $G_i(x) = [xi < 1]$ ($[P]$ is the Iverson bracket). Clearly $g(f(x)) = 1$, but $G_i(F_i(x)) = 0$, and thus converges to the wrong thing. $\endgroup$ – user5386 Jul 22 '15 at 23:13
  • 1
    $\begingroup$ @Kittsil: $G_i(0) = [0<1] = 1$ converges to $1$, so $ g(0) = 1$. $\endgroup$ – user5386 Jul 23 '15 at 8:59
  • 1
    $\begingroup$ @Hurkyl I added an assumption that the functions are continuous. $\endgroup$ – Erel Segal-Halevi Jul 23 '15 at 12:28
  • 2
    $\begingroup$ @Erel: Is that enough? My guess was that you'd need something like uniform convergence here. $\endgroup$ – user5386 Jul 23 '15 at 18:27
2
$\begingroup$

Is this idea correct?

(I apologize for my initial, poorly thought-out response to this question, and thank the commentors for pointing out the flaws.)

Your solution will work if $g(\cdot)$ is differentiable around $f(x)$.

Since $G(y)$ converges to $g(y)$, for any constant $\epsilon_G>0$ there exists some $N_G>0$ such that for any $y$ and all $i>N_G$, $$-\epsilon_G < G_i(y)-g(y) < \epsilon_G.$$

If $g(\cdot)$ is differentiable around $f(x)$, there exists constant $\epsilon_f>0$ such that $g(y)$ slopes toward $g(f(x))$ for all $y \in \left(f(x)-\epsilon_f, f(x)+\delta_g\right)$. Because $F$ converges to $f(x)$, there exists some $N_F>0$ such that for all $i>N_F$, $$-\epsilon_f< F_i(x) - f(x) < \epsilon_f.$$

Since $g(\cdot)$ slopes toward $f(x)$ in the neighborhood containing all $F_i(x)$ for $i>N_F$, as $F(x)$ approaches $f(x)$, $g(F(x))$ approaches $g(f(x))$; i.e., $g(F_i(x))$ converges to $g(f(x))$. That is, for any $\epsilon_g>0$, there exists some $N_g>N_F$ such that for all $i>N_g$, $$-\epsilon_g < g(F_i(x)) - g(f(x)) < \epsilon_g.$$

Now let $y=F_i(x)$. For any $\epsilon>0$, set $\epsilon_G = \epsilon_g = \frac{\epsilon}{2}$. Then for all $i>N$ (where $N=\max(N_G, N_F, N_g)$), $$-\epsilon = -(\epsilon_G+\epsilon_g) < G_i(F_i(x))-g(F_i(x)) + g(F_i(x)) - g(f(x)) < (\epsilon_G+\epsilon_g) = \epsilon,$$ or, $$-\epsilon < G_i(F_i(x)) - g(f(x))) < \epsilon.$$ That is, $G_i(F_i(x))$ converges to $g(f(x))$.


Is there a better idea?

Probably. Your algorithm generates $O(i)$ numbers to create the $i$th output number.

Consider if the algorithms were finite (i.e., you stopped at the $n$th output). Then, you would run $F$ to $F_n(x)$, then run $G$ using this as your input. This would only take generating $O(n)$ numbers. Your problem is not finite, though.

However, you can choose some constant $c$ and only restart $G$ after every $c$ steps. That is, the $i$th output will be $G_i(F_{c\lfloor i/c\rfloor}(x))$. This will make the convergence less smooth, but it will help your running time; it will now only generate $O(i/c)$ (amortized) numbers to create the $i$th output number.

$\endgroup$
  • $\begingroup$ What do you mean by: "Your algorithm takes O(i) to generate the ith output."? What is your computational model? What is a unit operation? $\endgroup$ – babou Jul 22 '15 at 22:36
  • $\begingroup$ @babou Good point. I clarified that this counts the number of generated numbers. $\endgroup$ – Kittsil Jul 23 '15 at 0:44
  • 1
    $\begingroup$ Your second sentence used to be "Yes! It will definitely converge to g(f(x))". You modified it to do away with @Hurkyl 's counter example. How do you prove what you assert? That would avoid fear of new counter-examples. --- --- Is your idea to only execute $F$ up to the $n^{th}$ value, then call $G$ so as to reduce the number of compuations of $G$? $\endgroup$ – babou Jul 23 '15 at 10:41
  • $\begingroup$ You claim this will converge to $g(f(x))$ without any justification, but I think this needs a careful proof. Do you have a proof of your answer? If not, then it is a bit sketchy to simply assert that it works, without any caveats, when you don't know for sure whether this is true or not. $\endgroup$ – D.W. Jul 23 '15 at 21:43
  • 1
    $\begingroup$ Also, it's still not clear to me what "As $F(x)$ approaches $f(x)$" means. If what you really mean is "$F(x)$ converges to $f(x)$", you should say that. Use standard terminology -- it exists for a reason. And even then, if we make that modification, it's not clear what that sentence was supposed to mean. Did you mean "Since $F(x)$ converges to $f(x)$, it follows that $g(F(x))$ converges to $g(f(x))$"? If so, this statement needs justification/proof. Just saying that it follows "since $g(\cdot)$ slopes towards $f(x)$..." is not a justification. $\endgroup$ – D.W. Jul 23 '15 at 23:53

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.