Алгоритмы Маркова-Турчина и доказательства полиномиальной эффективности программ на языке рефал-5

Abstract

Refal5 functions and introduced by the author in [5] Markov-Turchin algorithms are under consideration in the paper. Such an algorithm is an essential modification of a Refal5 program. The test of its polynomial efficiency for the Turing machine implementation of such a program is offered. This test does not use the bound on the used memory size as it was stated in [3] for double polynomial Refal5 programs. The test is based on a special kind of recursion in a program which is an essential generalisation of a tail recursion proposed by T. Borland for a Turbo Prolog program. This generalisation is connected with the main Refal5 data type: a tree-like text structured by means of brackets. For a Markov-Turchin algorithm (with a built-in dynamical interpreter) some modifications of complexity theory theorems useful for mathematicians-programmers have simple proofs. In other words an introduced here mathematical notion of an algorithm modifies (mainly simplifying and combining into a single algorithm all needed auxiliary algorithms with the use of the built-in dynamical interpreter) the notion of a Refal5 function introduced by V.F. Turchin (see, for example, [2, 6]). This modification is, in particular, an extension of the Markov algorithm notion for tree-like formed texts with the help of structural brackets. The introduction of the built-in dynamical interpreter (in the terminology of V.F. Turchin – the extended built-in meta-universal function) computing an application of any dynamically received algorithm to the input data is an essential extension of the Markov algorithm. It is known that in practice algorithms and the initial data have bounded lengths. Theorems on variants of the halting problem for the Markov algorithm with such a restriction are proved in the paper. More precisely, lower bounds of the length of a Markov-Turchin algorithm (with a built-in dynamical interpreter) for the program checking the halting problem for short programs and short data are proved.