Premium
BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
Author(s) -
Habart Karol,
Habart K.
Publication year - 1992
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/malq.19920380141
Subject(s) - turing , hierarchy , time hierarchy theorem , turing machine , description number , computer science , mathematics , universal turing machine , theoretical computer science , algorithm , programming language , computation , economics , market economy
A hierarchy of functions with respect to their role as bounds in the Turing reducibility of functions is introduced and studied. This hierarchy leads to a certain notion of incompressibility of sets which is also investigated.