Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jcss.2010.07.001
Title: Index sets and universal numberings
Authors: Jain, S. 
Stephan, F. 
Teutsch, J.
Keywords: 1-generic
Index sets
Kolmogorov property
MIN *
Minimal indices
Turing degrees
Universal numberings
Issue Date: Jul-2011
Citation: Jain, S., Stephan, F., Teutsch, J. (2011-07). Index sets and universal numberings. Journal of Computer and System Sciences 77 (4) : 760-773. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jcss.2010.07.001
Abstract: This paper studies the Turing degrees of various properties defined for universal numberings, that is, for numberings which list all partial-recursive functions. In particular properties relating to the domain of the corresponding functions are investigated like the set DEQ of all pairs of indices of functions with the same domain, the set DMIN of all minimal indices of sets and DMIN * of all indices which are minimal with respect to equality of the domain modulo finitely many differences. A partial solution to a question of Schaefer is obtained by showing that for every universal numbering with the Kolmogorov property, the set DMIN* is Turing equivalent to the double jump of the halting problem. Furthermore, it is shown that the join of DEQ and the halting problem is Turing equivalent to the jump of the halting problem and that there are numberings for which DEQ itself has 1-generic Turing degree. © 2010 Elsevier Inc. All rights reserved.
Source Title: Journal of Computer and System Sciences
URI: http://scholarbank.nus.edu.sg/handle/10635/113925
ISSN: 00220000
DOI: 10.1016/j.jcss.2010.07.001
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

5
checked on Jun 19, 2018

WEB OF SCIENCETM
Citations

3
checked on Jun 19, 2018

Page view(s)

51
checked on Jun 8, 2018

Google ScholarTM

Check

Altmetric


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