Index sets and universal numberings

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 o...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2011-07, Vol.77 (4), p.760-773
Main Authors: Jain, Sanjay, Stephan, Frank, Teutsch, Jason
Format: Article
Language:English
Subjects:
Equivalence
Lists
Mathematical analysis
Mathematical models
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0022-0000
DOI:10.1016/j.jcss.2010.07.001