Sum of Computable Real Sequences is Computable
Theorem
Let $\sequence {x_n}$ and $\sequence {y_n}$ be computable real sequences.
Then $\sequence {x_n + y_n}$ is a computable real sequence.
Corollary
Let $\sequence {x_n}$ be a computable real sequence.
Let $c \in \R$ be a computable real number.
Then, $\sequence {x_n + c}$ is a computable real sequence.
Proof 1
By definition, there exist total recursive $f,g : \N^2 \to \N$ such that:
- For every $m,n \in \N$, $\map f {m, n}$ and $\map g {m, n}$ respectively code integers $k$ and $\ell$ such that:
- $\dfrac {k - 1} {n + 1} < x_m < \dfrac {k + 1} {n + 1}$
- $\dfrac {\ell - 1} {n + 1} < y_m < \dfrac {\ell + 1} {n + 1}$
Define $h : \N^2 \to \N$ as:
- $\map h {m, n} = \map {\operatorname{quot}_\Z} {\map f {m, 4 n + 3} +_\Z \map g {m, 4 n + 3} +_\Z 2, 4_\Z}$
which is total recursive by:
- Addition is Primitive Recursive
- Multiplication is Primitive Recursive
- Constant Function is Primitive Recursive
- Addition of Integers is Primitive Recursive
- Multiplication of Integers is Primitive Recursive
- Quotient of Integers is Primitive Recursive
- Primitive Recursive Function is Total Recursive Function
Now, let $m, n \in \N$ be arbitrary.
Let $k'$ and $\ell'$ be the integers coded by $\map f {m, 4 n + 3}$ and $\map g {m, 4 n + 3}$, respectively.
Then, $\map h {m, n} = \floor {\dfrac {k' + \ell' + 2} 4}$.
Thus, by Floor is between Number and One Less:
- $\dfrac {k' + \ell' - 2} 4 < \map h {m, n} \le \dfrac {k' + \ell' + 2} 4$
Hence:
- $\map h {m, n} - 1 \le \dfrac {k' + \ell' - 2} 4$
- $\dfrac {k' + \ell' + 2} 4 < \map h {m, n} + 1$
From the inequalities above, we have:
\(\ds \dfrac {k' - 1} {\paren {4 n + 3} + 1} + \dfrac {\ell' - 1} {\paren {4 n + 3} + 1}\) | \(<\) | \(\, \ds x_m + y_m \, \) | \(\, \ds < \, \) | \(\ds \dfrac {k' + 1} {\paren {4 n + 3} + 1} + \dfrac {\ell' + 1} {\paren {4 n + 3} + 1}\) | ||||||||||
\(\ds \dfrac {k' + \ell' - 2} {4 n + 4}\) | \(<\) | \(\, \ds x_m + y_m \, \) | \(\, \ds < \, \) | \(\ds \dfrac {k' + \ell' + 2} {4 n + 4}\) | ||||||||||
\(\ds \dfrac {\map h {m, n} - 1} {n + 1}\) | \(<\) | \(\, \ds x_m + y_m \, \) | \(\, \ds < \, \) | \(\ds \dfrac {\map h {m, n} + 1} {n + 1}\) |
Thus, $\sequence {x_n + y_n}$ is computable by definition.
$\blacksquare$
Proof 2
By Computable Real Sequence iff Limits of Computable Rational Sequences, there exist:
- Computable rational sequences $\sequence {a_k}, \sequence {b_k}$
- Total recursive functions $\phi_x, \psi_x, \phi_y, \psi_y : \N^2 \to \N$
such that:
- $\forall m, p \in \N: \forall n \ge \map {\psi_x} {m, p}: \size {a_{\map {\phi_x} {m, n}} - x_m} < \dfrac 1 {p + 1}$
- $\forall m, p \in \N: \forall n \ge \map {\psi_y} {m, p}: \size {a_{\map {\phi_y} {m, n}} - y_m} < \dfrac 1 {p + 1}$
By Computable Subsequence of Computable Rational Sequence is Computable/Corollary, there exist:
- Computable rational sequences $\sequence {a'_k}, \sequence {b'_k}$
such that, for all $m, n \in \N$:
- $a_{\map {\phi_x} {m, n}} = a'_{\map \pi {m, n}}$
- $b_{\map {\phi_y} {m, n}} = b'_{\map \pi {m, n}}$
By Sum of Computable Rational Sequences is Computable:
- $\sequence {a'_k + b'_k}$
is a computable rational sequence.
Define $\psi : \N^2 \to \N$ as:
- $\map \psi {m, p} = \map \max {\map {\psi_x} {m, 2 p + 1}, \map {\psi_y} {m, 2 p + 1}}$
which is total recursive by:
If we can show:
- $\forall m, p \in \N: \forall n \ge \map \psi {m, p}: \size {\paren {a'_{\map \pi {m, n}} + b'_{\map \pi {m, n}}} - \paren {x_m - y_m}} < \dfrac 1 {p + 1}$
then the result will follow by Computable Real Sequence iff Limits of Computable Rational Sequences.
Let $m, n, p \in \N$ be arbitrary, and suppose that $n \ge \map \psi {m, p}$.
Then:
- $n \ge \map {\psi_x} {m, 2 p + 1}$
- $n \ge \map {\psi_y} {m, 2 p + 1}$
Thus, by assumption, we have:
- $\size {a_{\map {\phi_x} {m, n}} - x_m} < \dfrac 1 {2 p + 2}$
- $\size {b_{\map {\phi_y} {m, n}} - y_m} < \dfrac 1 {2 p + 2}$
Hence:
\(\ds \size {\paren {a'_{\map \pi {m, n} } + b'_{\map \pi {m, n} } } - \paren {x_m - y_m} }\) | \(=\) | \(\ds \size {\paren {a'_{\map \pi {m, n} } - x_m} + \paren {b'_{\map \pi {m, n} } - y_m} }\) | ||||||||||||
\(\ds \) | \(\le\) | \(\ds \size {a'_{\map \pi {m, n} } - x_m} + \size {b'_{\map \pi {m, n} } - y_m}\) | Triangle Inequality for Real Numbers | |||||||||||
\(\ds \) | \(=\) | \(\ds \size {a_{\map {\phi_x} {m, n} } - x_m} + \size {b_{\map {\phi_y} {m, n} } - y_m}\) | Definitions of $\sequence {a'_k}, \sequence {b'_k}$ | |||||||||||
\(\ds \) | \(<\) | \(\ds \frac 1 {2 p + 2} + \frac 1 {2 p + 2}\) | Above | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {p + 1}\) |
$\blacksquare$