Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-03073-4_28
DC FieldValue
dc.titleIndex sets and universal numberings
dc.contributor.authorJain, S.
dc.contributor.authorStephan, F.
dc.contributor.authorTeutsch, J.
dc.date.accessioned2014-12-01T08:22:52Z
dc.date.available2014-12-01T08:22:52Z
dc.date.issued2009
dc.identifier.citationJain, S.,Stephan, F.,Teutsch, J. (2009). Index sets and universal numberings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5635 LNCS : 270-279. ScholarBank@NUS Repository. <a href="https://doi.org/10.1007/978-3-642-03073-4_28" target="_blank">https://doi.org/10.1007/978-3-642-03073-4_28</a>
dc.identifier.isbn3642030726
dc.identifier.issn03029743
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/113936
dc.description.abstractThis 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 1 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 DMIN1 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. © 2009 Springer Berlin Heidelberg.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/978-3-642-03073-4_28
dc.sourceScopus
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.contributor.departmentMATHEMATICS
dc.description.doi10.1007/978-3-642-03073-4_28
dc.description.sourcetitleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.description.volume5635 LNCS
dc.description.page270-279
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

3
checked on Nov 27, 2021

Page view(s)

139
checked on Dec 2, 2021

Google ScholarTM

Check

Altmetric


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