Acta Mathematica Academiae Scientiarum Hungaricae 3. (1952)

1952 / 1-2. szám - Kalmár László: Another proof of the Markov-Post theorem

ANOTHER PROOF OF THE MARKOV—POST THEOREM* By LÁSZLÓ KALMÁR (Szeged), corresponding member of the Academy The word problem for associative systems (i. e. semigroups without postulating the cancellation law) has been proved to be unsolvable by any (finite, general recursive) algorithm independently and simultaneously by Post1 and Markov.2 Markov’s proof is simpler than that of Post’s;3 moreover, Markov obtained by means of his method some further results about the non-existence of some algorithms in the theory of associative systems.4 In the present paper, 1 shall give another proof for the non-existence of an algorithm to the effect of solving the word problem for associative systems. My proof seems to show some advantages over both Post’s and * Inaugural address, delivered 30 January 1950. 1 E. L. Post, Recursive unsolvability of a problem of Thue, The Journal of Symbolic Logic, 12 (1947), pp. 1—11. 2 А. Марков, Невозможность некоторых алгорифмов в теории ассоциативных систем, Доклады Академии Наук СССР, 55 (1947), рр. 587—590. 3 Indeed, Post relies besides (1) on a theorem of Church’s stating the non-existence of a decision algorithm for Z-convertability (see A. Church, An unsolvable problem of elementary number theory, American Journal of Math., 58 (1936), pp. 345—363), (2) on Rosser’s combinatorial equivalent of the calculus of Z-conversion (see J. B. Rosser, A mathematical logic without variables, Annals of Math., (2) 36 (1935), pp. 127—150 and Duke Math. Journal, 1 (1935), pp. 328—355), (3) on Post’s transformation method of logical systems in canonical form to those in normal form (see E. L. Post, Formal reduc­tions of the general combinatorial decision problem, American Journal of Math., 65 (1943), pp. 197-215), which have been used also by Markov, (4) on Post’s (very easy) transfor­mation method of logical systems in normal form to those in normal form and containing but two primitive letters (see E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Math. Society, 50 (1944), pp. 284 — 316, especially footnote5), and (5) on Turing’s theory of computing machines (see A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Math. Society, (2) 42 (1937), pp. 230—265 and 43 (1937), pp. 544—546). 4 See, besides loc. cit. 2, А. Марков, Невозможность некоторых алгорифмов в теории ассоциативных систем II, Доклады Академии Наук СССР, 58 (1947), рр. 353—356, as well as А. Марков, Невозможность некоторых алгоритмов в теории ассоциативных систем, Доклады Академии Наук СССР, 77 (1951), рр. 19—20.

Next