文章基本信息

标题：Random strings and tt-degrees of Turing complete C.E. sets
本地全文：下载
作者：Mingzhong Cai ; Rodney Downey ; Rachel Epstein 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2014
卷号：10
期号：3
页码：1
DOI：10.2168/LMCS-10(3:15)2014
出版社：Technical University of Braunschweig
摘要：We investigate the truth-table degrees of (co-)c.e.\ sets, in particular, sets of random strings. It is known that the set of random strings with respect to any universal prefix-free machine is Turing complete, but that truth-table completeness depends on the choice of universal machine. We show that for such sets of random strings, any finite set of their truth-table degrees do not meet to the degree~0, even within the c.e. truth-table degrees, but when taking the meet over all such truth-table degrees, the infinite meet is indeed~0. The latter result proves a conjecture of Allender, Friedman and Gasarch. We also show that there are two Turing complete c.e. sets whose truth-table degrees form a minimal pair.
其他关键词：random strings, truth-table degrees, strong reducibilities, minimal pair