Regular approximations to the recursive predicates

R. I. Freidson

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part IV, Tome 20 (1971), pp. 220-233

Résumé

By machines we mean Turing machines, idealized computer programs, or any idealized devices for computing the recursive functions. The machines and their size must satisfy the axioms of M. Blum. Let $\Phi$ be a total recursive function and $S$ a recursive predicate which is so complex that any machine computing $S(n)$ takes more than $\Phi(n)$ steps to do so for infinitely many $n$. A sequence of machines $M_1,M_2,\dots,M_n,\dots$ will be called a $\Phi$-bounded approximation to the recursive predicate $S$ if for each $n$ machine $M_n$ computes $S(x)$ for $x\leq n$ and takes no more than $\Phi(x)$ steps to do so. As a measure of the complexity of such approximation let us take the function which value on ft is the size of machine $M_n$. One of the possible approaches to make the general problem of bounded approximation more precise is considered and some results concerning the compexity of such approximations are stated. The case when limitations on the complexity of computation force the members of approximating sequence to degenerate into finite-state machines is studied more carefully.