|
Organizers |
Universal recursively enumerable sets of strings
by
Frank Stephan
National University of Singapore
Coauthors: Cristian Calude, Andre Nies and Ludwig Staiger
The present work clarifies the relation between domains of universal machines and r.e. prefix-free supersets of such sets. One such characterisation ca be obtained in terms of the spectrum function sW(n) mapping n to the number of all strings of length n in the set W. An r.e. prefix-free set W is the superset of the domain of a universal machine iff there are two constants c, d such that sW(n)+sW(n+1)+...+sW(n+c) is between 2n-H(n)-d and 2n-H(n)+d for all n; W is the domain of a universal machine iff there is a constant c such that for each n the pair of n and sW(n)+sW(n+1)+...+sW(n+c) has at least the prefix-free description complexity n. There exists a prefix-free r.e. superset W of a domain of a universal machine which is the not a domain of a universal machine; still, the halting probability of such a set W is Martin-Loef random. Furthermore, it is investigated to which extend this results can be transferred to plain universal machines.
Date received: February 29, 2008
Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawo-12.