FOM: what is computability theory?
sazonov at logic.botik.ru
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
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
> 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)?
Computer Logic Lab. | Tel. +7-08535-98945 (Inst.),
Program Systems Institute, | Tel. +7-08535-98365 (home),
Russian Acad. of Sci. | Fax. +7-08535-20566
Pereslavl-Zalessky, | e-mail: sazonov at logic.botik.ru
152140, RUSSIA | http://www.botik.ru/~logic/SAZONOV/
More information about the FOM