Skip to main content
Article
On the Commutativity of Jumps
The Journal of Symbolic Logic (2000)
  • Timothy H. McNicholl, University of Dallas
Abstract
We study the following classes:

● Q* (r1A1…..rkAk) 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 ri, queries to Ai, for all i ∈ {1..… k}.

● Q(r1A1…..rkAk) which is defined like Q* (r1A1….. rkAk) except that queries to Ai, must be made before queries to Ai+1for all i ∈ {1….. k – 1}.

● QC(r1A1….. rkAk) which is defined like Q{r1A1….. rkAk) except that the Turing machine must halt even if given incorrect answers to some of its queries.

We show that if A1 ….. Ak are jumps that are not too close together, then all three of these classes are identical and are not changed if we permute (r1…..rkAk). 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.
Keywords
  • oracles,
  • Turing machines,
  • commutativity,
  • mathematical sequences,
  • position function,
  • mathematical theorems,
  • logical conjunctions,
  • logical disjunction,
  • logical theorems,
  • eigenfunctions
Publication Date
2000
DOI
10.2307/2695072
Publisher Statement
Copyright 2000. Association for Symbolic Logic
Citation Information
Timothy H. McNicholl. "On the Commutativity of Jumps" The Journal of Symbolic Logic Vol. 65 Iss. 4 (2000) p. 1725 - 1748
Available at: http://works.bepress.com/timothy-mcnicholl/24/