Universal recursively enumerable sets of strings

作者：Calude Cristian S; Nies Andre; Staiger Ludwig; Stephan Frank^*

来源：Theoretical Computer Science, 2011, 412(22): 2253-2261.

DOI：10.1016/j.tcs.2011.01.002

• Algorithmic information theory
• Universal machines
• Domains of universal machines
• Recursively enumerable sets

The main topics of the present work are universal machines for plain and prefix-free description complexity and their domains. It is characterised when an r.e. set W is the domain of a universal plain machine in terms of the description complexity of the spectrum function s(W) mapping each non-negative integer n to the number of all strings of length n in W; furthermore, a characterisation of the same style is given for supersets of domains of universal plain machines. Similarly the prefix-free sets which are domains or supersets of domains of universal prefix-free machines are characterised. Furthermore, it is shown that the halting probability Omega(V) of an re. prefix-free set V containing the domain of a universal prefix-free machine is Martin-Lof random, while V may not be the domain of any universal prefix-free machine itself. Based on these investigations, the question whether every domain of a universal plain machine is the superset of the domain of some universal prefix-free machine is discussed. A negative answer to this question had been presented at CiE 2010 by Mikhail Andreev, Ilya Razenshteyn and Alexander Shen, while this paper was under review.

• 出版日期2011-5-13