Reverse Computability Theory

			  C T Chong
	      National University of Singapore

We denote by PA^- the axioms of Peano arithmetic without the induction
scheme. I\Sigma_n stands for the induction scheme for sigma_n formulas,
while B\Sigma_n is the Sigma_n bounding principle: Every $Sigma_n$
definable function on a closed interval is bounded in the range. A basic
result in models of arithmetic says that under PA^-,

I\Sigma_n ---> B\Sigma_n  ---> I\Sigma_{n-1}.

The stratification of Peano axioms gives rise to a hierarchy of
computability theories of increasing strength, with full Peano arithmetic
at the apex.

There has been some success in classifying computability-theoretic
statements (notably about c.e. sets and degrees of unsolvability) via
fragments of Peano arithmetic. There is also evidence that these theories
present new insights into the notion of computability, through the
introduction of techniques and tools which have no parallel in the
classical theory. 

In this talk we discuss some problems in this area: A uniform solution for
the Friedberg-Muchnik Theorem, the minimal degree problem, the structure
of degrees without Sigma_n induction, and doing computability theory in
the absence of sigma_n bounding.