Partial functions and domination
From MaRDI portal
Publication:3196347
DOI10.2168/LMCS-11(3:16)2015zbMATH Open1347.03078arXiv1506.06869OpenAlexW2233140512MaRDI QIDQ3196347FDOQ3196347
Authors:
Publication date: 29 October 2015
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1506.06869
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
genericityrecursion theoryrecursively enumerable setsdomination of partial functionslow and high degrees
Algorithmic randomness and dimension (03D32) Recursive functions and relations, subrecursive hierarchies (03D20)
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)
