Вводятся алгоритмы Маркова-Турчина как обобщение алгоритмов, введённых автором в [5], и являющиеся существенной модификацией программ, написанных на языке рефал-5. Предлагается критерий их эффективности для реализации на машине Тьюринга за полиномиальное число шагов. Этот критерий не использует ограничения памяти, в отличие от того, как это было установлено в [3] для дважды полиномиальных программ на языке рефал-5. Критерий основан на специального вида рекурсии в программах, являющейся существенным обобщением хвостовой рекурсии, предложенной Т. Борландом для программ на турбо прологе. Это обобщение связано с основным типом данных в языке рефал-5, представляющем собой древовидно структурированные тексты посредством круглых скобок. Для алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором) просто доказываются некоторые модификации теорем теории сложности алгоритмов, полезные для математиков-программистов. Иначе говоря, вводится математическое понятие алгоритма, модифицирующее (в основном, упрощающее, а также объединяющее в единый алгоритм все вспомогательные алгоритмы с помощью использования встроенного интерпретатора) понятие рефал-5 функции, введённой В.Ф. Турчиным (см., например, [2, 6]), в частности, путем расширения понятия нормального алгоритма А.А. Маркова на древовидно оформленные тексты с помощью структурных (круглых) скобок. Введение встроенного динамического интерпретатора (в терминологии В.Ф. Турчина – расширения встроенной метауниверсальной функции), вычисляющего применение любого алгоритма с динамически полученной его записью к исходным данным, является существенным расширением понятия алгоритма Маркова. Известно, что на практике алгоритмы и исходные данные ограничены по длине. В статье также доказываются теоремы о вариантах проблемы применимости алгоритмов Маркова-Поста с учётом этого обстоятельства. Точнее, доказываются нижние оценки длины программ, разрешающих проблему применимости коротких программ к коротким данным на языке алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором). С. 41-49.

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.