Universal recursively enumerable sets of strings
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. (C) 2011 Elsevier B.V. All rights reserved.
recursively enumerable sets universal machines algorithmic information theory domains of universal machines