Premium
Post's Problem for Reducibilities of Bounded Complexity
Author(s) -
Bulitko Valeriy K.
Publication year - 2002
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/1521-3870(200204)48:3<367::aid-malq367>3.0.co;2-h
Subject(s) - recursively enumerable language , mathematics , discrete mathematics , turing , dtime , turing machine , bounded function , combinatorics , degree (music) , recursively enumerable set , computer science , algorithm , universal turing machine , mathematical analysis , physics , acoustics , computation , programming language
In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤ m , ≤ btt , ≤ tt and ≤ T and solved the problem for al of them except ≤ T . Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub‐Turing reducibilities what were studying in [1, 2].