文章基本信息

标题：Partial functions and domination
本地全文：下载
作者：C.T. Chong ; Gordon Hoi ; Frank Stephan 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2015
卷号：11
期号：3
页码：1
DOI：10.2168/LMCS-11(3:16)2015
出版社：Technical University of Braunschweig
摘要：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 {\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.
其他关键词：Recursion Theory; Domination of Partial Functions; Genericity; Recursively Enumerable Sets; Low and High Degrees.