Please use this identifier to cite or link to this item:
|Title:||Selection by recursively enumerable sets||Authors:||Merkle, W.
|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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.