Density of a final segment of the truth-table degrees

Jean-Leah Mohrherr

Vol. 115 (1984), No. 2, 409–419

DOI: 10.2140/pjm.1984.115.409

Abstract

This work answers two questions from the topic of degrees of unsolvability, which is part of recursive function theory. We give a simple and explicit example of elementary inequivalence of the Turing degrees to the truth-table degrees. In constructing this example, we show that every truth-table degree above that of the halting problem is the jump of another truth-table degree.

Mathematical Subject Classification 2000

Primary: 03D30

Milestones

Received: 7 February 1983

Published: 1 December 1984