一般遞歸函數的構成

<正> 引言 在本文中我們所討論的悉限於非負整數,故本文內备變元及函數的值均限於非負整數. 如果有一系列的有限個等式,使得對於任意指定的值a_1,a_2,…,a_r,互可依照這些等式在有限次步驟內把函數F(x_1,x_2,…,x_r)在(a_1,a_2,…,a_r)點的值計算出來,則函數F(x_1,x_2,…,x_r)名曰一般遞歸函數.

ON THE EXPLICIT FORM OF GENERAL RECURSIVE FUNCTIONS

According to L. Kalmar, the elementary functions are the functions obtainable from the initial functions x+y, |x-y|, x.y, x/y] by means of the operations stitution. If only the narrowed summation and substitution are available, the functions obtained are called restricted elementary functions. We may show that the latter form a proper subclass of the class of elementary functions (this remains true even if the operation ai is also available).The main result of the present paper is to improve the well known Kleene's theorem as follows:Every gefieral reeursive function may be expressed in the form A(eyB(x_1,x_2,…,x_r, y)=0]), where A and B are restricted elementary functions.In the additional note we get a still stronger result. Let us call basical functions those functions which are obtainable from the initial functions x+1, x?y(=sg x+sg y), x-y, x·sg y,by means of the operations ∑ and substitution alone. Evidently the basical functions form a proper subclass of the class of the restricted elementary functions. We show that the functions A and B mentioned above may be required to be basieal ones.