# FOM: what is computability theory?

Wed Aug 19 17:41:49 EDT 1998

```Stephen G Simpson wrote:

> Martin Davis writes:
>  > The short answer to this question is it is the same subject hat
>  > used to be called "recursive function theory" and then
>  > metamorphosed to "recursion theory". ....
>
> Are you sure that "computability theory" (as discussed by Soare in his
> 1995 position paper) is the same subject as recursion theory?  For
> example, does it include asymptotic computational complexity theory,
> or doesn't it?  Soare chose to waffle on this important point.

What about the following (roughly formulated) theorems
related to so called descriptive complexity theory?

THEOREM 1. [Sazonov 80, Gurevich 83] "General" recursive functions
defined by systems of (least fixed point) functional equations
f(x)=T(f,x) with the terms T (constructed from 0, Successor,
If-Then-Else, f, x) having *arbitrary* form define exactly the class
of Polynomial Time computable (global) functions, *provided* these
equations are interpreted over a finite row of natural numbers
0,1,2,...,\Box with the largest number \Box whose value is not
specified in advance (i.e. \Box is a parameter "resource bound";
let, for definiteness, Succ(\Box)=\Box.)

Call such functions \Box-recursive. Thus,

\Box-recursion = PTIME-computability.

THEOREM 2. [Gurevich 83]

\Box-primitive recursion = LOGSPACE-computability.

(Strictly speaking, we should consider here *relative recursion*,
i.e. right-hand sides T(f,g,x) of recursive equations may actually
contain finite (non-global) functional parameters
g:{0,1,2,...,\Box}а.{0,1,2,...,\Box}.)

By the way, we may even consider \Box as having a *fixed* value,
say = 2^1000 or even = 1000. Even in this case it makes a sense
to distinguish between \Box-recursive (i.e. having "feasible"
recursive description) and non-\Box-recursive finite functions.
This may lead to non-asymptotic analogue of "asymptotic"
("infinitistic") complexity/recursion theory. Recall chess and
how playing this finite (8x8) game is complex
(non-feasibly-8-recursive?).

> (I
> take it as a given that recursion theory *does not* include asymptotic
> complexity theory.  I learned this from my thesis advisor, Gerald
> Sacks, in the late 1960's.)

Would you recall the arguments of Sacks (or yourself)?