Partial functions and domination
From MaRDI portal
Publication:3196347
DOI10.2168/LMCS-11(3:16)2015zbMATH Open1347.03078arXiv1506.06869OpenAlexW2233140512MaRDI QIDQ3196347
Author name not available (Why is that?)
Publication date: 29 October 2015
Published in: (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
No records found.
No records found.
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)
