Partial functions and domination
From MaRDI portal
Publication:3196347
Abstract: The current work introduces the notion of pdominant sets and studies their recursion-theoretic properties. Here a set A is called pdominant iff there is a partial A-recursive function {psi} such that for every partial recursive function {phi} and almost every x in the domain of {phi} there is a y in the domain of {psi} with y<= x and {psi}(y) > {phi}(x). While there is a full {pi}01-class of nonrecursive sets where no set is pdominant, there is no {pi}01-class containing only pdominant sets. No weakly 2-generic set is pdominant while there are pdominant 1-generic sets below K. The halves of Chaitin's {Omega} are pdominant. No set which is low for Martin-L"of random is pdominant. There is a low r.e. set which is pdominant and a high r.e. set which is not pdominant.
Recommendations
- Determining and stationary sets for some classes of partial recursive functions
- Almost everywhere domination
- Domains of \(t\)-functions
- A Note on Conjectures of Calude About the Topological Size of Sets of Partial Recursive Functions
- Relativized topological size of sets of partial recursive functions
Cited in
(4)
This page was built for publication: Partial functions and domination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196347)
