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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom