Back to Search
Start Over
PARTIAL FUNCTIONS AND DOMINATION.
- Source :
- Logical Methods in Computer Science (LMCS); 2015, Vol. 11 Issue 3, p1-16, 16p
- Publication Year :
- 2015
-
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 ψ such that for every partial recursive function ϕ and almost every x in the domain of ϕ there is a y in the domain of ψ with y ≤ x and ψ(y)>ϕ(x). While there is a full Π<subscript>1</subscript><superscript>0</superscript>- class of nonrecursive sets where no set is pdominant, there is no Π<subscript>1</subscript><superscript>0</superscript> 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 Ω are pdominant. No set which is low for Martin- Löf random is pdominant. There is a low r.e. set which is pdominant and a high r.e. set which is not pdominant. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 18605974
- Volume :
- 11
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Logical Methods in Computer Science (LMCS)
- Publication Type :
- Academic Journal
- Accession number :
- 110264027
- Full Text :
- https://doi.org/10.2168/lmcs-11(3:16)2015