×

zbMATH — the first resource for mathematics

A class of degrees of unsolvability for functions not possessing a fixed point. (Russian) Zbl 0711.03015
The paper is devoted to the study of the class F of degrees of unsolvability of functions f having no fixed points (i.e. such that \(\forall x(W_{f(x)}\neq W_ x)\). The main result is that there exists a \(\Pi^ 0_ 1\) class \({\mathcal A}\) of sets such that F is equal to \(\{\) dg(A): \(A\in {\mathcal A}\}\).
Reviewer: R.Murawski
MSC:
03D30 Other degrees and reducibilities in computability and recursion theory
03D35 Undecidability and degrees of sets of sentences
PDF BibTeX XML Cite