Acta Mathematica Academiae Scientiarum Hungaricae 3. (1952)
1952 / 1-2. szám - Kalmár László: Another proof of the Markov-Post theorem
I,. KALMAR 2. My proof for the Markov—Post theorem is based on a theorem due to Kleene 11 according to which a general recursive function R(x, у) of two variables can be given for which there is no algorithm by means of which, given any non-negative integer k, we could decide if the equation R(k,y) = 0 in у has a non-negative integer solution. Here a general recursive function12 is an arithmetical function (i. e., a function with non-negative integers as arguments and values) for which, together with the successor function F(x) = x-\-\ and some additional arithmetical functions (called, together with F and R, the functions “needed to the definition of R”) a system E of equations (called a “defining system of equations for R”) can be given with the following properties. Each equation of E has to be a formula in the formal system Щ defined below. For each function G needed to the definition of R, and for every sequence klt k,, ..., ks of non-negative integers the number s of which coincides with the number of arguments of G, the equation G (Fk' (0), Fk* (0),..., Fk* (0)) = Fk (0) has to be a theorem of the formal system Ф'с for one and only one non-negative integer к which we denote by к = G (F ,k2,..., ks). Here Fk(0) is an abbreviation for F(F(... F(0)...)) with к symbols F and the formal system iP£ is defined as follows. Symbols of Щ are 0; an enumerable infinite set of “variables” x, y,...; a finite set of symbols F, called “functors”, for the functions needed to the definition of R to each of which a positive integer (for F, the integer 1) is attached as the “number of its arguments”; 13 parentheses ( and ) ; comma , ; equality symbol = . Terms of Щ are (i) 0 and the variables; (ii) for any functor G, the sequence of symbols G(t,. t2,..., ts) where s is the number of arguments of the functor G and t,,^, ...,ts are terms of Щ; (iii) nothing else. Formulae of Щ are the sequences of symbols of the form t u where t and u are terms of Щ. Axioms of Щ are the equations of E. rithm by means of which, given any relation in au ag,..., at, we could decide if it holds in the associative system 3is generated by S. 11 S. C. Kleene, General recursive functions of natural numbers, Math. Annalen, 112 (1936), pp. 727—742, especially theorem XV, p. 741. We do not make use of the fact that R(x,y) is actually a primitive recursive function. The same result follows, with a 2-recursive function R, from an unpublished proof of R. Péter for Church’s theorem on the existence of decision problems which are not solvable by any algorithm, by means of Gödel’s theorem on the existence of truth problems unsolvable in a given postulate system, and, with an elementary function R, from an unpublished proof of mine for Church’s above theorem as a particular case of Gödel’s above theorem (see also L. Kalmár, On unsolvable mathematical problems, Proceedings of the tenth International Congress of Philosophy (Amsterdam, August 11 —18, 1948), pp. 756—758). 12 See Kleene, loc. cit. n, Definition 2b, p. 731. 13 We suppose that we never use the same functor for functions with a different number of variables (as F(x) and F(x, y), e. g.).