Defining the Turing Jump
Richard A. Shore, Theodore A. Slaman · Mathematical Research Letters · 1999
Introduction The primary notion of e#ective computability is that provided by Turing machines (or equivalently any of the other common models of computation). We denote the partial function computed by the eth Turing machine in some standard list by # e . When these machines are equipped with an "oracle" for a subset A of the natural numbers #, i.e. an external procedure that answers questions of the form "is n in A", they define the basic notion of relative computability or Turing reducibility (from Turing (1939)). We say that A is computable from (or recursive in) B if there is a Turing machine which, when equipped with an oracle for B, computes (the characteristic function of) A, i.e. for some e, # B e = A. We denote this relation by A # T