×

Degrees of functions with no fixed points. (English) Zbl 0694.03027

Logic, methodology and philosophy of science VIII, Proc. 8th Int. Congr., Moscow/USSR 1987, Stud. Logic Found. Math. 126, 191-201 (1989).
[For the entire collection see Zbl 0676.00003.]
Let us define \(FPF=\{f:\) \(\forall e[W_ e\neq W_{f(e)}]\}\), and \(DNR=\{g:\) \(\forall e[g(e)\neq \phi_ e(e)]\}\). Let \(DNR_ k\) be the class of all functions \(g\in DNR\) with \(g(e)<k\) for all e. The author reviews some results, concerning the properties of the above defined sets, obtained earlier by him as well as by other authors. Then he proves that there cannot exist a reduction procedure \(\Phi\) and a number k such that \(\Phi (g)\in DNR_ k\) for all \(g\in DNR_{k+1}\). Every degree in FPF is shown to contain an effectively immune set. A number of other questions concerning DNR and FPF are considered.
Reviewer: G.B.Marandzhyan

MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
03D20 Recursive functions and relations, subrecursive hierarchies

Citations:

Zbl 0676.00003