Completeness with given accuracy in function systems of program type

Yu. V. Golunkov

Diskretnaya Matematika, Tome 2 (1990) no. 3, pp. 42-49

Résumé

As the main model of a function system of program type we use the system of algorithmic algebras $R=P\cup Q$ of all one-place partial recursive functions $P$ and predicates $Q$. For a general recursive function $\varphi (x)$, a set $M\subseteq R$ is said to be $\phi $-complete if it contains a predicate with nonempty domains of truth and falsehood and for every function $f\in P$ the closure $[M]$ contains a function $t$ with the same domain as $f$ satisfying $|f(x)-t(x)|\leqslant\varphi (x)$ for each $x$ in the domain of $f$ and $t$. We find necessary and sufficient conditions under which each $\varphi $-complete set is complete in the usual sense. We show that the criterion for $\varphi $-completeness cannot be essentially simpler than the criterion for ordinary completeness no matter what the general recursive function $\varphi$ is.