FOM: what is computability theory?

[Vladimir Sazonov]

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)?


Vladimir Sazonov

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/