В [3] даны определения числа шагов и длины записи промежуточных вычислений паскалевидных функций. С их помощью было получено представление класса всех функций, вычислимых на машинах Тьюринга за число шагов, ограниченное сверху полиномом от длины записи исходных данных (класса FP), с помощью дважды полиномиальных (то есть полиномиальных по числу шагов и по длине записи промежуточных вычислений) паскалевидных функций. Для удобства доказательства принадлежности паскалевидной функции классу FP здесь введено понятие паскалевидных функций над списком S паскалевидный функций. Для этих функций даны определения числа шагов и длины записи промежуточных вычислений, наконец, определены дважды полиномиальные паскалевидные функции над списком S. (для каждой функции из S число шагов и длина записи промежуточных вычислений равны единице). Функции из S соответствуют базовым подпрограммам. Доказывается теорема о совпадении класса дважды полиномиальных паскалевидных функций над S и класса FP.

[3] gives definitions of time and space comlexity of pascal-like functions. Using this definitions it was obtained the representation of the class of all functions computable by Turing machine in time upper bounded by the polynomial of the length of the initial data (FP class) by means of double polynomial (i.e. polynomial in time and space) pascal-like functions. For the convinience of proving that a pascal-like function is in FP, we introduce the notion of the pascal-like functions over a list S of pascal-like functions. For such functions we give definitions of time and space complexities, finally, we define double polynomial pascal-like functions over a list S. (for every function in S, time and space complexity are equal to one). Functions from S correspond to basic subroutines. The theorem about the equality of the class of double polynomial pascal-like functions over S and the FP class is proved.