Portal de Periódicos da CAPES

Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion

1989; Cambridge University Press; Volume: 54; Issue: 4 Linguagem: Inglês

10.1017/s0022481200041104

1943-5886

C. G. Jockusch, M. Lerman, Robert I. Soare, R. M. Solovay,

semigroups and automata theory

Let W e be the e th recursively enumerable (r.e.) set in a standard enumeration. The fixed point form of Kleene's recursion theorem asserts that for every recursive function f there exists e which is a fixed point of f in the sense that W e = W f ( e ) . In this paper our main concern is to study the degrees of functions with no fixed points. We consider both fixed points in the strict sense above and fixed points modulo various equivalence relations on recursively enumerable sets. Our starting point for the investigation of the degrees of functions without (strict) fixed points is the following result due to M. M. Arslanov [A1, Theorem 1] and known as the Arslanov completeness criterion. Proofs of this result may also be found in [So1, Theorem 1.3] and [So2, Chapter 12], and we will give a game version of the proof in §5 of this paper. Theorem 1.1 (Arslanov). Let A be an r.e. set. Then A is complete ( i.e. A has degree 0 ′) iff there is a function f recursive in A with no fixed point .