On the commutativity of jumps

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


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

Download options


    Upload a copy of this work     Papers currently archived: 72,856

External links

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

Through your library


Added to PP

19 (#588,492)

6 months
1 (#386,040)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references

Citations of this work

No citations found.

Add more citations