Please use this identifier to cite or link to this item:
|Title:||Universal recursively enumerable sets of strings||Authors:||Calude, C.S.
|Issue Date:||2008||Citation:||Calude, C.S.,Nies, A.,Staiger, L.,Stephan, F. (2008). Universal recursively enumerable sets of strings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5257 LNCS : 170-182. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-540-85780-8_13||Abstract:||The present work clarifies the relation between domains of universal machines and r.e. prefix-free supersets of such sets. One such characterisation can be obtained in terms of the spectrum function s W (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 s W (n)+s W (n+1)+...+s W (n+c) is between 2 n-H(n)-d and 2 n-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)+s W (n+1)+...+s W (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 Ω W of such a set W is Martin-Löf random. Furthermore, it is investigated to which extend this results can be transferred to plain universal machines. © 2008 Springer-Verlag Berlin Heidelberg.||Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)||URI:||http://scholarbank.nus.edu.sg/handle/10635/104666||ISBN:||3540857796||ISSN:||03029743||DOI:||10.1007/978-3-540-85780-8_13|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.