The Arslanov completeness criterion says that a c.e. set A is Turing complete if and only there exists an A-computable function f without fixed points, i.e. a function f such that for each integer x. Recently, Barendregt and Terwijn proved that the completeness criterion remains true if we replace the Gödel numbering with an arbitrary precomplete computable numbering. In this paper, we prove criteria for noncomputability and highness of c.e. sets in terms of (pre)complete computable numberings and fixed point properties. We also find some precomplete and weakly precomplete numberings of arbitrary families computable relative to Turing complete and non-computable c.e. oracles respectively.
K.Ambos-Spies, S.Badaev and S.Goncharov, Inductive inference and computable numberings, Theoretical Comp. Sci.412 (2011), 1652–1668. doi:10.1016/j.tcs.2010.12.041.
2.
U.Andrews, S.Badaev and A.Sorbi, A survey on universal computably enumerable equivalence relations, in: Computability and Complexity. Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, Springer, 2017, pp. 418–451. doi:10.1007/978-3-319-50062-1_25.
3.
M.M.Arslanov, On some generalizations of the fixed point theorem, Sov. Math. (Iz. VUZ)25 (1981), 1–10.
4.
M.M.Arslanov, R.F.Nadirov and V.D.Solov’ev, Completeness criteria for recursively enumerable sets and some general theorems on fixed points, Sov. Math. (Iz. VUZ)21 (1977), 1–4.
S.A.Badaev, S.S.Goncharov and A.Sorbi, Completeness and universality of arithmetical numberings, in: Computability and Models, The University Series in Mathematics, Springer, Boston, MA, 2003. doi:10.1007/978-1-4615-0755-0_2.
7.
H.Barendregt and S.A.Terwijn, Fixed point theorems for precomplete numberings, Ann. Pure App. Log.170 (2019), 1151–1161. doi:10.1016/j.apal.2019.04.013.
8.
Y.L.Ershov, On inseparable pairs, Algebra Log.9 (1970), 396–399. doi:10.1007/BF02219043.
9.
Y.L.Ershov, Theory of Numberings, Nauka, Moscow, 1977, Russian.
10.
Y.L.Ershov, Theory of numberings, in: Handbook of Computability Theory, E.R.Griffor, ed., Studies in Logic and the Foundations of Mathematics, Vol. 140, Elsevier Science, Amsterdam, 1999, pp. 473–506. doi:10.1016/S0049-237X(99)80030-5.
S.S.Goncharov and A.Sorbi, Generalized computable numerations and non-trivial Rogers semilattices, Algebra Log.36 (1997), 359–369. doi:10.1007/BF02671553.
13.
B.Grabmayr, On the invariance of Gödel’s second theorem with regard to numberings, Review Symb. Log.14 (2021), 51–84. doi:10.1017/S1755020320000192.
14.
C.G.JockuschJr., The degrees of bi-immune sets, Z. Math. Logik Grundlagen Math.15 (1969), 135–140. doi:10.1002/malq.19690150707.
15.
C.G.JockuschJr., Degrees in which the recursive sets are uniformly recursive, Canad. J. Math.24 (1972), 1092–1099. doi:10.4153/CJM-1972-113-9.
16.
A.N.Kolmogorov and V.A.Uspensky, On the definition of an algorithm, Usp. Mat. Nauk.13 (1958), 3–28.
17.
M.Kummer, Some applications of computable one–one numberings, Arch. Math. Logic.30 (1990), 219–230. doi:10.1007/BF01792984.
18.
A.I.Mal’tsev, Constructive algebras I, Russ. Math. Surv.16 (1961), 77–129. doi:10.1070/RM1961v016n03ABEH001120.
19.
A.I.Mal’tsev, The Metamathematics of Algebraic Systems, North-Holland, Amsterdam, 1971.
20.
D.A.Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math.12 (1966), 295–310. doi:10.1002/malq.19660120125.
21.
H.Rogers, Gödel numberings of partial computable functions, J. Symb. Logic.23 (1958), 49–57. doi:10.2307/2964292.
22.
R.I.Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, Heidelberg, New York, 1987.
23.
R.I.Soare, Turing Computability, Theory and Applications of Computability, Springer-Verlag, Berlin, Heidelberg, 2016.
24.
V.A.Uspensky, Some remarks on enumerable sets, Z. Math. Logik Grundlagen Math.3 (1957), 157–170. doi:10.1002/malq.19570031202.
25.
V.A.Uspensky and A.L.Semenov, Algorithms: Main Ideas and Applications, Kluwer Academic Publishers, Dordrecht, 1993.
