On the commutativity of jumps

Journal of Symbolic Logic 65 (4):1725-1748 (2000)
  Copy   BIBTEX

Abstract

We study the following classes: Q* (r 1 A 1 ,..., r kA k ) which is defined to be the collection of all sets that can be computed by a Turing machine that on any input makes a total of r i queries to A i for all i ∈ {1,..., k}. Q(r 1A 1 ,...,r kA k ) which is defined like Q* (r 1A 1 ,..., r kA k ) except that queries to A i must be made before queries to A i+1 for all i ∈ {1,..., k - 1}. QC(r 1A 1 ,..., r kA k ) which is defined like Q(r 1A 1 ,..., r kA k ) except that the Turing machine must halt even if given incorrect answers to some of its queries. We show that if A 1 ,..., A k are jumps that are not too close together, then all three of these classes are identical and are not changed if we permute (r 1A 1 ,..., r kA k ). This extends a result of Beigel's [1]. Since the second class is not affected by permutations, we say that these sets commute with each other. We also show that jumps that are too close together may not commute. We also characterize the commutative sequences of sets obtained by iterating the jump operation through an ordinal notation

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 104,556

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Rings which admit elimination of quantifiers.Bruce I. Rose - 1978 - Journal of Symbolic Logic 43 (1):92-112.
Generalized cohesiveness.Tamara Hummel & Carl Jockusch - 1999 - Journal of Symbolic Logic 64 (2):489-516.
R-analytic functions.Tobias Kaiser - 2016 - Archive for Mathematical Logic 55 (5-6):605-623.
Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.

Analytics

Added to PP
2009-01-28

Downloads
38 (#656,184)

6 months
5 (#855,288)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references