There isn’t an immediately accessible proof of this that I am happy with, though it is not particularly hard. I will agonise every detail, strap in.
Fix an explicitly known bijection \(\pi : \mathbb N \to \mathbb Q\), where \(\mathbb Q\) is represented by the equivalence classes of pairs \((p, q) \in \mathbb Z \times (\mathbb Z \setminus \{0\})\) under the relation \((p, q) \sim (s, t) \leftrightarrow pt = q s\). For example, enumerate \(\mathbb Z^2\) by a spiral and delete those elements with second coordinate \(0\), or that are \(\sim\)-equivalent to a previously iterated rational.
Cauchy Name: We say that a sequence of natural numbers \(\langle {e_n}\rangle_{n \in \mathbb N}\) is a (\(\pi\)-)Cauchy name for \(x \in \mathbb R\) if \(|\pi(e_n) – x| < 2^{-n}\). Realistically, we will write \(x_n = \pi(e_n) \in \mathbb Q\) and consider \(\langle {x_n}\rangle\) to be the Cauchy name.
Oracle Turing Machine: We introduce oracle Turing machines as Turing machines with an additional read-only “oracle tape” consisting of \(0\)s and \(1\)s. At any stage, the machine can move the read head along this tape and read the cell that it hovers over. We write the space of sequences with terms either \(0\) or \(1\) as \(2^\omega\). We computably enumerate these machines by \(\phi_0^\bullet\), \(\phi_1^\bullet\), \(\ldots\). For \(\sigma \in 2^\omega\), we write \(\phi_e^\sigma\) for the machine formed by loading \(\sigma\) in as the oracle tape on the machine \(\phi_e^\bullet\).
Use Principle: If a Turing machine halts, it does so in finitely many steps. Similarly, if an oracle Turing machine halts, then it does so in finitely many steps. Hence, it can only have read finitely many cells of the oracle tape. Suppose that for \(\sigma \in 2^\omega\) and \(j \in \mathbb N\), \(\phi_e^\sigma(j)\) halts. \(\phi_e\) only reads finitely many entries of \(\sigma\), some initial segment \(\sigma \mid n\). Whenever the oracle Turing machine reads those natural numbers in sequence on the first \(n\) bits, it must do precisely the same thing: it does not know anything about the tape it is given and can only read its cells. Hence, if another string \(\widetilde \sigma\) coincides with \(\sigma\) on the first \(n\) bits, the action of the machine must be precisely the same. That is, \(\phi_e^{\widetilde \sigma}(j)\) will still halt, and it will give the same output. This will become useful.
Pedantry I: Though the oracle tape should technically consist of \(0\)s and \(1\)s, I will consider it fine to consist of natural numbers. We write the space of natural number sequences by \(\omega^\omega\). It is fairly easy to obtain a computable embedding of \(\omega^\omega\) into \(2^\omega\). Given a tape \(\tau\) in \(\omega^\omega\), we write a tape \(\sigma\) in \(2^\omega\) as follows. If \(\tau_0 = t_0\), we write \(\sigma_i = 1\) for \(0 \le i \le t_0 – 1\) and then \(\sigma_n = 0\). Then if \(\tau_1 = t_1\), we write \(\sigma_i = 1\) for \(n + 1 \le i \le t_0 + t_1\) and then \(\sigma_n = 0\). You get the idea, if \(\tau_n\) reads \(t_n\) then we write \(t_n\) ones to the tape, then a zero.
Pedantry II: Given a string in \(2^\omega\) constructed this way, we can easily reconstruct the origin string in \(\omega^\omega\) by counting the number of \(1\)s between each zero. Consecutive zeroes will indicate zero values in \(\omega^\omega\). Of course, this is not a bijection since \((1, 1, 1, 1, \ldots)\) does not get mapped to. The upshot of all of this is that we can understand an index name \(\langle x_n\rangle\) as an oracle tape for an oracle Turing machine.
Type II Computable: We say that a function \(f : \mathbb R \to \mathbb R\) is Type-II computable if there exists an oracle Turing machine \(\Phi_e\) which accepts a Cauchy name \(\langle x_n\rangle\) for a real number \(x\) and gives as its output a Cauchy name for \(f(x)\). Precisely, whenever \(\langle x_n\rangle\) is a Cauchy name for \(x\), we have that \(|\pi(\Phi_e^{\langle x_n\rangle}(j)) – f(x)| < 2^{-j}\) for each \(j \in \mathbb N\). For the reader’s sanity we will consider the output of \(\Phi_e^{\langle x_n\rangle}(j)\) to actually be \(q_j = \pi(\Phi_e^{\langle x_n\rangle}(j))\) so that \(|q_j – f(x)| < 2^{-j}\), and we will informally say that \(q_j\) is the \(j\)th order approximation to \(f(x)\).
Theorem A: A Type II computable function \(f\) is continuous.
Proof Line 1: Let \(x \in \mathbb R\). Let \(\langle x_n\rangle\) be a Cauchy name for \(x\) that satisfies \(|x – x_n| < 2^{-(n + 1)}\). For example, take any Cauchy name \(\langle y_n\rangle\) and set \(x_n = y_{n + 1}\). Let \(\Phi_e^\bullet\) be the oracle Turing machine whose existence is granted by the Type II computability of \(f\). Let \(\epsilon > 0\). We wish to show that there exists \(\delta > 0\) such that whenever \(|x – y| < \delta\) for some \(x \in \mathbb R\), we have \(|f(x) – f(y)| < \epsilon\). Take \(j \in \mathbb N\) with \(2^{-j} < \epsilon\).
Proof Line 2: Consider the action of \(\Phi_e^{\langle x_n\rangle}(j + 1)\). By the Use Principle, \(\Phi_e\) will only read finitely many of the terms \(x_n\) before halting. Suppose that it reads up to \(x_N\). Consider \(y \in \mathbb R\) such that \(|x – y| < 2^{-(N + 1)}\). Then \(x_n\) for \(n \le N\) starts a Cauchy name for \(y\), as we will now prove. We have \(|y – x_n| \le |x – y| + |x – x_n| < 2^{-(N + 1)} + 2^{-(n + 1)} \le 2^{-n}\) for \(n \le N\). We can complete \(x_n\) to a Cauchy name for \(y\) arbitrarily.
Proof Line 3: Consider the action of \(\Phi_e^{\langle y_n\rangle}(j + 1)\). \(\Phi_e\) will read the first \(N\) cells of the oracle tape, discover \(x_1, \ldots, x_N\), do the same operations as with \(\langle x_n\rangle\), halt, and output \(\Phi_e^{\langle x_n\rangle}(j + 1)\). Hence \(q = \pi(\Phi_e^{\langle x_n\rangle}(j + 1))\) is a \((j + 1)\)th order approximation for both \(f(x)\) and \(f(y)\). That is, \(|q – f(x)| < 2^{-(j + 1)}\) and \(|q – f(y)| < 2^{-(j + 1)}\) so that \(|f(x) – f(y)| < 2^{-j} < \epsilon\). Recall that \(y \in \mathbb R\) only satisfied \(|x – y| < 2^{-(N + 1)}\), hence if we take \(\delta = 2^{-(N + 1)}\) then we are done.
There is a similar notion of computability called Borel computability. For this, we will need to introduce the concept of a computable real number. I will enumerate the Turing machines by \(\phi_1, \phi_2, \ldots\).
Index Name: We say that \(\phi_e\) gives a computable Cauchy name for \(x \in \mathbb R\) if \(|\pi(\phi_e(j)) – x| < 2^{-j}\) for all \(j \in \mathbb N\). We refer to \(x_n = \phi_e(n)\) as the computable Cauchy name. We call \(e \in \mathbb N\) an index name for \(x\). We say that \(x \in \mathbb R\) is computable if an index name for \(x\) exists. We write the set of such real numbers by \(\mathbb R_c\).
Borel computability: We say that a function \(f : \mathbb R_c \to \mathbb R_c\) is Borel computable if there exists an oracle Turing machine \(\Phi_e\) which accepts a computable Cauchy name \(\langle x_n\rangle\) of an \(x \in \mathbb R_c\) and an \(j \in \mathbb N\) and gives a \(j\)th order approximation to \(f(x)\).
Hence Borel computability is Type II computability restricted to computables. Tracing the proof of the continuity of a type II computable function, we readily obtain that Borel computable functions are continuous. We can say more.
Effectively continuous: Let \(f : \mathbb R_c \to \mathbb R_c\) be a function. We say that \(f\) is effectively continuous if there exists a partially defined computable function \(\alpha : \mathbb N^2 \to \mathbb N\) that accepts a pair \((e, j)\) as input. If \(\phi_e\) gives a computable Cauchy name for a computable real number \(x \in \mathbb R_c\), then \(\alpha(e, j)\) should be such that whenever \(y \in \mathbb R_c\) has \(|x – y| < 2^{-\alpha(e, j)}\), we have \(|f(x) – f(y)| < 2^{-j}\).
Theorem B: Borel computable functions \(f\) are effectively continuous.
Proof Line 1: This is a straightforward adaption of Theorem A. Accept an input \((e, j)\). Try to do the following, if it fails at any point then \(\phi_e\) does not compute any real number and we can simply allow \(\alpha\) to be undefined. However, it may be still be defined when \(\phi_e\) does not compute any real number. We will point out why this is the case during the proof. This, however, does not matter since we only fuss about the output of \(\alpha\) when \(\phi_e\) does compute a real number.
Proof Line 2: Suppose that \(x_n\) is the sequence produced by \(\phi_e\). Let \(\Phi_F^\bullet\) be the oracle Turing machine computing \(f\). Run \(\Phi_F^{\langle x_n\rangle}(j + 1)\) until it halts. Let \(N\) be the greatest index of the \(x_N\) that are read by \(\Phi_F\) in the computation. We then output \(\alpha(e, j) = N + 1\). Tracing the proof of Theorem A, this works.
Note: If \(\Phi_F^{\langle x_n\rangle}(j + 1)\) halts after reading \(x_N\), then we can define a sequence \(\langle y_n\rangle\) to coincide with \(\langle x_n\rangle\) up to index \(N\), and then write oscillatory garbage thereafter. The resulting sequence may not be the Cauchy name of any real number, yet the machine will still halt due to the Use Principle. In this case \(\phi_e\) has simply produced a “partial” Cauchy name before dissolving into nonsense. We do not care about this.
I finish with the notion of computability that I use in my research, Markov computability.
Markov computability: Let \(f : \mathbb R_c \to \mathbb R_c\) be a function. We say that \(f\) is Markov computable if there exists a partial computable function \(\nu : \mathbb N \to \mathbb N\) that when given an index name \(e\) for a real number \(x \in \mathbb R_c\), will output an index name for \(f(x)\).
Theorem C: Markov computable functions are effectively continuous. Further, a function is Markov computable if and only if it is Borel computable.
Proof: For the first part, see Section 8 of A Banach–Mazur computable but not Markov computable function on the computable real numbers by Hertling. For the second part, see Notes on Computable Analysis by Porter, Day, Downey – note that this is based on a masters thesis and I would not recommend trying to read their proof that Markov computable functions are effectively continuous. However, they both prove that effectively continuous Markov computable functions are Borel computable and that Borel computable functions are Markov computable, and these proofs are both perfectly readable.
Leave a Reply