Fixed point theorems for precomplete numberings (Q2311209)

In this paper, the authors provide further steps on the generalization process of Kleene's fixed point theorem. The paper also contains some interesting questions for further developments. Kleene's fixed point theorem states that every computable function \(f:\omega\rightarrow\omega\) has a fixed point, that is, an \(n\in\omega\) such that \[ \varphi_{f(n)}=\varphi_n. \] Here, \(n\mapsto\varphi_n\) is the standard numbering of all the partial computable functions. The uniform version of Kleene's fixed point theorem states that there exists a computable function \(f\) such that for every computable function \(g\), if \(\varphi_n=g\) then \(f(n)\) is a fixed point of \(g\): \[ \varphi_{g(f(n))}=\varphi_{f(n)}. \] A numbering of a set \(S\) is a surjection \(\gamma:\omega\rightarrow S\). A numbering \(\gamma\) is \textit{precomplete} if and only if for every partial computable function \(\psi\) there exists a computable function \(f\) such that for every \(n\in\omega\) \[ \psi(n)\mbox{ is defined }\Rightarrow \gamma(f(n))=\gamma(\psi(n)). \] \textit{Y. L. Ershov} [Z. Math. Logik Grundl. Math. 21, 473--584 (1975; Zbl 0344.02031)] generalizes Kleene's fixed point to every precomplete numbering. Actually, the following uniform version of Ershov's fixed point theorem is known, a proof of which can be found in [\textit{U. Andrews} et al., Lect. Notes Comput. Sci. 10010, 418--451 (2017; Zbl 1485.03146), cf. Theorem 2.1]: (1) Let \(\gamma:\omega\rightarrow S\) be a precomplete numbering. There exists a computable function \(f\) such that for every \(n\in\omega\), \[ \varphi_n(f(n))\mbox{ is defined }\Rightarrow \gamma(\varphi_n(f(n)))=\gamma(f(n)). \] In the paper under review, the authors generalize (1) by extending the notions of numbering and precompleteness of numberings from \(\omega\) to each \textit{partial combinatory algebra} (pca). Definition (generalized numbering). Given a pca \(\mathcal{A}\) and a set \(S\), a \textit{generalized numbering} is a surjective map \(\gamma:\mathcal{A}\rightarrow S\). \(\gamma\) is \textit{precomplete} if for every term \(t(x)\) with one variable \(x\) there exists a total element \(f\in\mathcal{A}\) such that, for every \(a\in\mathcal{A}\), \[ t(a)\mbox{ is defined }\Rightarrow \gamma(fa)=\gamma(t(a)). \] They show that (1) is a special case of the following: (a) Let \(\mathcal{A}\) be a pca and \(\gamma:\mathcal{A}\rightarrow S\) a generalized precomplete numbering. Then there exists a total \(f\in\mathcal{A}\) such that for all \(g\in\mathcal{A}\), \[ g(fg)\mbox{ is defined }\Rightarrow\gamma(g(fg))=\gamma(fg). \] The authors also discuss \textit{M. M. Arslanov}'s completeness criterion [Sov. Math. 25, No. 5, 1--10 (1981; Zbl 0523.03029)] and \textit{A. Visser}'s ADN theorem [``Numerations, \(\lambda\)-calculus, and arithmetic'', in: To H. B. Curry: Essays on combinatory logic, lambda calculus and formalism. London etc.: Academic Press, A Subsidiary of Harcourt Brace Jovanovich, Publishers. 259--284 (1980)]. In particular, they give the following two generalizations to each precomplete numbering: (b) (Arslanov's completeness criterion for precomplete numberings). Let \(\gamma\) be a precomplete numbering and \(A<_T\emptyset'\) a computably enumerable set. If \(g\) is an \(A\)-computable function, then \(g\) has a fixed point modulo \(\gamma\), i.e. there exists \(n\in\omega\) such that \[ \gamma(g(n))=\gamma(n). \] (c) (ADN theorem, uniform version for precomplete numberings). Let \(\gamma\) be a precomplete numbering and suppose that \(\delta\) is a partial computable diagonal function for \(\gamma\). Then there exists a computable function \(f\) such that for every fixed \(e\in\omega\) the function \(f(\langle e,n\rangle)\) totalizes \(\varphi_e\) avoiding \(\delta\) modulo \(\gamma\), namely: \[ \varphi_e(n)\mbox{ is defined }\Rightarrow \gamma(f(\langle e,n\rangle))=\gamma(\varphi_e(n)), \] \[ \varphi_e(n)\mbox{ is undefined }\Rightarrow \delta(f(\langle e,n\rangle))\mbox{ is undefined}. \] In the final part of the paper, the authors analyze the relation between combinatory completeness of a pca \(\mathcal{A}\) and the precompleteness of the generalized identity numbering \(\gamma_{\mathcal{A}}:\mathcal{A}\rightarrow\mathcal{A}\).