Статья содержит два основных раздела. Первый из них (п. 2) отвечает на вопрос о том, как можно расширить понятие нормального алгоритма Маркова, включив, в частности, полиномиальные функции над длинами используемых слов и сохранив при этом объём вычислений в пределах полиномиального числа шагов. Ответом на этот вопрос является последовательность математических понятий алгоритма со всё более мощными вычислительными средствами, но тем не менее совпадающими с классом алгоритмов, полиномиальных по времени (с классом FP) при реализации их на машинах Тьюринга. Второй из основных разделов (п.3) отвечает на вопрос, каким образом можно, всё более расширяя понятие нормального алгоритма Маркова, вложить их в каждый из подклассов FP, алгоритмы которого используют промежуточную память, длина которой ограничена полиномом k-ой степени. Результаты второго раздела могут рассматриваться также и как подтверждение естественной формулировки тезиса Чёрча для последнего из классов алгоритмов, использованных в формулировках теорем этого раздела.

This paper contains two main sections. The first one (section 2) answers the question: В«How to extend the notion of Markov algorithm by inclusion of a polnomial function of a word length and to conserve computation inside polynomial number of steps?В». A sequence of mathematical notions of algorithm with more and more powerfull computational tools is presented. It is proved that every of them coinsides with the class of polynomial in time algorithms (class FP). The second one (section 3) answers the question: В«How to extend the notion of Markov algorithm in order to include it into subclass of FP containing only algorithms using intermediate memory with the length not more than a polynomial of k-th degree?В». The results of this section may be also regarded as a confirmation of the natural formulation of Church thesis for the last two classes of algoritmms used in the formulations of the theorems of this section.