On the Commutativity of Jumps

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

Abstract

We study the following classes: $Q* $ 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 \in \{1,..., k\}$. $Q$ which is defined like $Q* $ except that queries to $A_i$ must be made before queries to $A_{i+1}$ for all $i \in \{1,..., k - 1\}$. $QC$ which is defined like $Q$ 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 $$. 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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On the commutativity of jumps.Timothy H. McNicholl - 2000 - Journal of Symbolic Logic 65 (4):1725-1748.
Limit lemmas and jump inversion in the enumeration degrees.Evan J. Griffiths - 2003 - Archive for Mathematical Logic 42 (6):553-562.
Generalized cohesiveness.Tamara Hummel & Carl G. Jockusch - 1999 - Journal of Symbolic Logic 64 (2):489-516.
Generalized Cohesiveness.Tamara Hummel & Carl Jockusch - 1999 - Journal of Symbolic Logic 64 (2):489-516.
Automata techniques for query inference machines.William Gasarch & Geoffrey R. Hird - 2002 - Annals of Pure and Applied Logic 117 (1-3):169-201.
A cohesive set which is not high.Carl Jockusch & Frank Stephan - 1993 - Mathematical Logic Quarterly 39 (1):515-530.
On the expressibility and the computability of untyped queries.Jose Turull Torres - 2001 - Annals of Pure and Applied Logic 108 (1-3):345-371.

Analytics

Added to PP
2017-02-21

Downloads
0

6 months
0

Historical graph of downloads

Sorry, there are not enough data points to plot this chart.
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