Search
 Submission Procedure share: |

available in:   PDF (101 kB) PS (24 kB)

get:
 Similar Docs BibTeX Write a comment
get:

DOI:   10.3217/jucs-001-02-0151

# On Completeness of Pseudosimple Sets

(Odessa State University, Ukraine
ul. Perekopskoj divizii 67-40
Odessa 270062, UKRAINE
bulitko.odessa@REX.iasnet.com)

Abstract: The paper contains completeness criterions for pseudosimple sets. Those criterions are constructed using effectivization of the definitions as well as extensionally bounded functions.

Keywords: Completeness, Pseudosimple set, Effectivization, Extensionally bounded function

Category: G

# 1 On Completeness of Pseudosimple Sets

A recursively enumerable (r.e.) set is called complete (Turing-complete) if any r.e. set can be reduced to that set using Turing reducibility. Optionally complete sets can have some interesting properties, for instance they can be simple, pseudosimple, etc. Problems of constructing completeness criterions for simple sets by an effectivization of definitions have been investigated by McLaughlin, Smullyan, Lachlan, Arslanov, etc. History and systematical description of that can be found in [Arslanov 87].

Simple sets fall into class of r.e. set classification by Uspenskij and Dekker-Myhill [Rogers 67]. For creative sets the criterions have been constructed even before. However we do not know any specific criterion for pseudosimple and pseudocreative sets. In this paper we propose some completeness criterions for pseudosimple sets.

Most of our notation follows [Rogers 67] also r. means recursive, r.e. means recursively enumerable and i.r.e. means infinite recursively enumerable. We use and as ' under definition'. Sometimes we use 'number of' as 'index of'. Let us recall the following definitions from [Rogers 67]:

Definition 1. A is pseudosimple (1) A is r.e. but not r.;
(2) . Such C we will denote .

Definition 2. A is pseudosimple with center C (1) A is pseudosimple;
(2)

Above definitions allow the following effectivization:
Definition 1'. A is weakly effectively pseudosimple (1) A is pseudosimple;
(2)

Definition 2'. A is weakly effectively pseudosimple with center C (1) A is pseudosimple with center C; (2)

First prove two complementary lemmas.

Lemma 1. For any complete set A and any r.e. set M the following function is total and recursive in A:

Page 151

Proof. because is an r.e. set.

Therefore f is computable with oracle A.

Lemma 2. Let A be complete and g be partial recursive in A. Then the following function is partial recursive in A:

Proof. Let us make computation of as follows. Given z we start computation of g(z) and if it ends, we enumerate numbers of r.e. sets until some of them fall into which is recursive in A. Let it happen when i=n so we set equal to . Note we use uniform recursiveness of in respect to complete A.

Theorem 1. (A is pseudosimple and complete) (A is weakly effectively pseudosimple and ).

Proof. Let A be pseudosimple and complete then obviously . Define total f as follows:

f is computable with oracle A by lemma 1,2, and because is an r.e. set, and is immune. Thus A is weakly effectively pseudosimple.

Using f, which is recursive in A, and possibility to write out elements of in increasing order with oracle A, construct initial segment of enumeration of in increasing order. An r.e. index of X(z) can be computed with oracle A because X(z) is finite and recursive in A. Let g(z) be that r.e. index. So . Thus A is complete by the Arslanov theorem [Arslanov 87]. (The Arslanov theorem used here and below states that for any r.e.s. A (A is complete) .

Another completeness criterion can be obtained introducing concept of special function.

Definition 3. Let A be weakly effectively pseudosimple. We call total and recursive in A function f special for A if

Theorem 2. (A is pseudosimple and complete) (A is weakly effectively pseudosimple and there is f special for A).

Proof. Define f as follows:

f can be computed with oracle A by lemmas 1,2, and because is an r.e. set, and is immune. So A is weakly effectively pseudosimple with special function f.

Let g be defined as follows:

Page 152

g can be computed with oracle A because f is recursive in A. Also g is total and obviously does not have fixed points so we can apply the Arslanov theorem that causes A is complete.

There is also another approach to effectivization of the definitions. The approach is based on use of functions evaluating complexity characteristics of set other than the number of elements. For instance, Lachlan in [Lachlan 68] used the number of value changes of characteristic function for a given r.e. set on a cohesive set building sufficient conditions for complete maximal sets. Completeness criterion for maximal sets [Bulitko 92] constructed using Kolmogorov complexity of set initial segments is another example. Next step in that direction is use of extensionally bounded functions to construct completeness criterions for special classes of simple sets. That approach has been posed by V.K.Bulitko in [Bulitko 95]. In present paper we use that approach to describe pseudosimple and complete sets.

Definition 4. Total f is extensionally bounded (e.b.)

Theorem 3. (A is pseudosimple and complete) (A is r.e. but not r. & such that the following function f: is e.b. and recursive in A).

Proof. Obviously A is r.e. but not r. f is computable with oracle A by lemma 1 and because is immune. For any number i of r.e. f(i) is bounded by cardinality of X that is finite because A is pseudosimple. f is equal to 0 for a number of an r.e. set which is not a subset of . Therefore f is e.b.

Assume . Then taking in account infiniteness of index set we get f is not bounded on index set. That contradicts with the definition of e.b. function. Therefore our assumption is wrong and A is pseudosimple. Completeness of A can be proved in the same way as in theorem 2.

Let us consider pseudosimple sets with center.

Theorem 4. (A is pseudosimple with recursive center C and complete) (A is weakly effectively pseudosimple with recursive center C).

Proof. Define f as follows:

f is computable with oracle A by lemmas 1,2 and . Therefore A is weakly effectively pseudosimple with recursive center.

We can get total function that does not have fixed points doing in the same way as in the first theorem. Using the Arslanov theorem we obtain completeness of A.

Page 153

Situation regarding case of non-recursive (in general) center is described by the following theorems and remarkable enough. Trying to get the criterion we succeeded in way of using e.b functions only.

Theorem 5. (A is weakly effectively pseudosimple with center C recursive in A) (A is pseudosimple with center C and complete).

Proof. Follows from the first theorem.

Definition 5. Let A be weakly effectively pseudosimple with center C. Call total and computable with oracle A function f bounding for A if

Theorem 6. (A is weakly effectively pseudosimple with center C and there is bounding for A function f) (A is pseudosimple with center C and complete).

Proof. Define g as follows:

g can be computed with oracle A because f is recursive in A. Also g is total and does not have fixed points. Thus A is complete by the Arslanov theorem.

Theorem 7. (A is pseudosimple with center C and complete) (A is r.e. but not r.; ; the following f is e.b. and computable with oracle A):

Proof. Obviously A is r.e. but not r. f is computable with oracle A by lemma 1 and because having oracle A we are able to write out all of elements not belonging to C and situated in f is e.b. because f is bounded on numbers of r.e. which is finite because A is pseudosimple with center, and f is equal to 0 on numbers of an r.e. set which is not a subset of .

A is pseudosimple with center C because f is e.b. and therefore (otherwise we would get unbounded f taking in account that any r.e. set has an infinite number of its indexes). Completeness of A can be proved in the same way as in theorem 6.

# References

[Arslanov 87] Arslanov, M.M.: 'Local theory of unsolvability degrees and sets'; KGU press / Kazan, (1987).(In Russian).

[Rogers 67] Rogers, H. Jr.: 'Theory of recursive functions and effective computability'; McGrow-Hill / N.-Y. (1967).

[Lachlan 68] A.H.Lachlan, A. H.: 'Complete recursively enumerable sets'; Proc. Amer. Math. Soc., 19, (1968), 99-102.

[Bulitko 92] Bulitko, V. K.: 'Subturing reducibilities with bounded complexity'; Izv. VUZov, ser. mat., 1 (1992), 27-37. (In Russian).

[Bulitko 95] Bulitko, V. K.: 'On some complexity characteristics of Immune sets'; MLQ, 41, 3 (1995) (in press).

Page 154