Post Problem for Restricted Reducibilities

V.K.Bulitko

We consider the well known [1] problem by E.Post on construction of such sets that with respect to a given reducibility have degrees intermediate between the degrees of recursive sets and the degrees of complete sets.

Post considered reducibilities ≤_{m}, ≤_{btt}, ≤_{tt}, ≤_{T} and solved the problem for all of them except ≤_{T}. For the latter Post constructed classes of simple and hyper-simple sets.

In [2] the following result was presented: Post’s approach is applicable to any ”characteristically bounded” reducibility ≤_{T M} that does not coincide with ≤_{T} on the class of recursively enumerable sets (r.e.s.). Furthermore, even the class of hyper-simple sets suffices to show that.

In this work another complexity measure for Turing reductions is considered. We call it segment complexity [3]. Let A[n] = (A(i))_{i<n} denote the initial segment of set A. So A(i) denotes the i-th element of A. The number n is the length of the segment A[n]. We can now say A ≤_{MT} B iff there exist an index x ∈ ℕ and a total function h : ℕ → ℕ such that the reduction A ≤_{T}^{x} B takes place, h ≤_{T} M, and the initial segment of oracle B[h(n)] is sufficient to compute A[n] via the reduction almost for any n. For any set M relation ≤_{MT} is also a reducibility with respect to decidability.

Therefore, the problem of interest is to describe such T -degrees d_{T} (M) that Post’s ideas are applicable to reducibilities ≤_{MT}.

As a part of our solution, we introduce radius of recursiveness R_{B} : ℕ → ℕ of any set B defined as a function that on the input n yields the length of the maximal initial segment of B computable by a program with the length no greater than n. M-radially-h-simple set is such a r.e.s. A that the radius of recursiveness RĀ of its complement can not be majorated by any increasing total recursive in M function.

Theorem. For any set M of low Turing degree there exist M-radially-h-simple non-simple sets. All such sets are not ≤_{MT} -complete.

[1] Rogers H.,Jr. Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.

[2] Bulitko V.K. On Post’s Problem for Reducibilities with Information Bounds, 11th International Congress of LMPS, Cracow, Poland, 1999, Volume of Abstracts, p.76.

[3] Bulitko V.K. About Segment Complexity of Turing Reductions, Math. Logic Quart., 45 (1999) 4, 561-571.

Address: Odessa State University, Fontanskaya Doroga 67-40, Odessa 65062, Ukraine

E-mail: booly@@te.net.ua