Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-38236-9_14
Title: Selection by recursively enumerable sets
Authors: Merkle, W.
Stephan, F. 
Teutsch, J.
Wang, W.
Yang, Y. 
Issue Date: 2013
Citation: Merkle, W.,Stephan, F.,Teutsch, J.,Wang, W.,Yang, Y. (2013). Selection by recursively enumerable sets. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7876 LNCS : 144-155. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-38236-9_14
Abstract: For given sets A, B and Z of natural numbers where the members of Z are z0, z1,⋯ in ascending order, one says that A is selected from B by Z if A(i) = B(zi) for all i. Furthermore, say that A is selected from B if A is selected from B by some recursively enumerable set, and that A is selected from B in n steps iff there are sets E0, E1,⋯, En such that E0 = A, En = B, and Ei is selected from Ei+1 for each i < n. The following results on selections are obtained in the present paper. A set is ω-r.e. if and only if it can be selected from a recursive set in finitely many steps if and only if it can be selected from a recursive set in two steps. There is some Martin-Löf random set from which any ω-r.e. set can be selected in at most two steps, whereas no recursive set can be selected from a Martin-Löf random set in one step. Moreover, all sets selected from Chaitin's Ω in finitely many steps are Martin-Löf random. © Springer-Verlag Berlin Heidelberg 2013.
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/104624
ISBN: 9783642382352
ISSN: 16113349
DOI: 10.1007/978-3-642-38236-9_14
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

87
checked on Nov 18, 2021

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.