C. T. Chong ; Gordon Hoi ; Frank Stephan ; Daniel Turetsky - Partial functions and domination

lmcs:1592 - Logical Methods in Computer Science, September 21, 2015, Volume 11, Issue 3 - https://doi.org/10.2168/LMCS-11(3:16)2015
Partial functions and dominationArticle

Authors: C. T. Chong ; Gordon Hoi ; Frank Stephan ; Daniel Turetsky

    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öf random is pdominant. There is a low r.e. set which is pdominant and a high r.e. set which is not pdominant.


    Volume: Volume 11, Issue 3
    Published on: September 21, 2015
    Submitted on: August 28, 2014
    Keywords: Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 1021 times.
    This article's PDF has been downloaded 480 times.