Portal de Periódicos da CAPES

Proof of some theorems on recursively enumerable sets.

1962; Duke University Press; Volume: 3; Issue: 2 Linguagem: Inglês

10.1305/ndjfl/1093957149

1939-0726

Thoralf A. Skolem,

Data Management and Algorithms

In this paper I shall first define a class of functions which I call lower elementary, abbreviated Lei.functions in the sequel, and after some preliminary considerations prove that every recursively enumerable set of integers can be enumerated by a Lei.function.All variables and functions shall here take non-negative integers as values.L. Kalmar defined the notion elementary function (see [l]).These are the functions that can be constructed from addition, multiplication and the operation ~ by use of the general sums and products x x 2/ω ^d TT /(r) ' r=o r=ό where / may contain parameters, together with the use of composition.If we omit the use of general products, we get what I call the lower elementary functions.The definition is therefore: Df 1.The Lei. functions are those which can be built by starting with x the functions 0, 2, x + y, xy, x ~ y and using the summation \\ f ( r )> where *=o / may contain parameters, besides use of composition.By the way, instead of xy one can choose S (%, y), the Kronecker delta (see [2]).As to the summation schema it can be shown that it is sufficient to require its use in the case that / contains one parameter at most.Of course xy can be omitted as starting function.Clearly every polynomial is an Lei.function.Further every Lei.function can be majorised by a polynomial.This is seen immediately to be true for the starting functions and it is easily seen to be hereditary with regard to summation and composition.If for example f(x, y) is always ^ Ψ(x, y), where φ is a polynomial, then for all x and y x xΣttr,y)<Σφ{τ,y)