Тезис Чёрча для полиномиальных по времени рекурсивных алгоритмов над словами и их длинами

Abstract

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.