Статья посвящена сложности алгоритмов и является продолжением статьи автора из журнала номер 4 за 2005 год. Рассматриваются классы сложности задач, для решения которых требуется различное число шагов.

Статья посвящена описание машины Тьюринга, которое было введено для математического уточнения определения алгоритма. Приводятся примеры устройства различных машин Тьюринга, упражнения для самостоятельной работы. На диске, прилагаемом к журналу, помещена программа-эмулятор машины Тьюринга, сделанная Р. Зартдиновым, к данной статье.

Статья посвящена сложности алгоритмов. Рассматриваются примеры алгоритмов, решающих одну и ту же задачу, но затрачивающих различное число шагов.

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

The paper is devoted to the problem of proving that some function is in FP complexity class. Such proofs may use pascal-like functions, that are more easy for programmers, than computation models based on a Turing machine. It will be presented the idea of proof of the theorem, that if both the number of steps of pascal-like function evaluation and a size of all intermediate evaluations are not greater than some polynomial of the length of initial data, then this function is in FP and vice versa.

В [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.

При разработке многократно используемых программ важно, чтобы их выполнение было достаточно быстрым. В книге Ду Д.З. и Ко К.И. сформулирован обобщенный тезис Чёрча: «Функция, вычислимая за полиномиальное время на разумной вычислительной модели, использующей разумное измерение временной сложности, вычислима на детерминированной машине Тьюринга за полиномиальное время» (то есть принадлежит классу FP). Этот расширенный тезис Чёрча более естественно называть полиномиальным тезисом Чёрча для машин Тьюринга. «Разумность» вычислительной модели разными исследователями понимается по-разному, вследствие чего в последнее время всё чаще появляются «доказательства» (содержащие ошибки) знаменитой проблемы: верно ли, что P = NP? При этом шаг различных моделей алгоритмов трактуется интуитивно. В настоящей работе доказано, что «разумность» шага вычисления рекурсивной функции может заключаться в использовании таких рефал-5-предложений из класса FP, длина записи результата выполнения которых (включая длину записи всего изменяемого стека) увеличивается не более чем на константу, единую для всех исходных данных. В этом смысле обычное определение общерекурсивной функции не является «разумной» вычислительной моделью. Достаточно сложным является подсчет числа шагов рекурсивного алгоритма. В настоящей статье доказаны необходимые и достаточные условия полиномиальности по времени функции, реализованной на языке программирования рефал-5. Этот язык является практически реализованным обобщением таких математических моделей алгоритма как нормальные алгоритмы, а также вводимые здесь алгоритмы Маркова-Поста и рекурсивные алгоритмы Маркова-Поста. Поэтому в качестве следствий основной теоремы доказаны условия полиномиальности по времени и этих математических моделей, применимых в теоретических исследованиях. Весьма актуальным является вопрос о возможности доказательства того, что программа, написанная на языке рефал-5, задает полиномиально быструю функцию, то есть функцию, принадлежащую классу FP. В статье вводится понятие дважды полиномиальных рекурсивных вызовов рефал-5-функции, обеспечивающее решение этого вопроса.

It is important for multiple-used programs that their run be sufficiently quick. Du D.Z. and Ko K.I. have formulated a extended Church thesis: В«A function computable in polynomial time in any reasonable computational model using a reasonable time complexity measure is computable by a deterministic Nuring machine in polynomial timeВ» (i.e. it belongs to the class FP. It is more natural to call this extended Church thesis as a polynomial Church thesis for Turing machine. Different researchers differently understand the term reasonable in consequence of which at the last time many В«proofsВ» (containing mistakes) of the famous problem whether P = FP appear. In such В«proofsВ» a step of different algorithm models treats intuitively. In the present work it is proved that reasonability of a recursive function step may be consisted in the use of such refal-5-sentenses from FP, for which the length of result notation (including the lenth of all stack) increases not more than by additive constant unique for all arguments. In such a sence a usual definition of a recursive function is not a reasonable calculation model. The count of recursive algorithm steps is rather difficult. Nesessary and sufficient conditions of time polynomiality of a function, realized by means of programming language refal-5, are proved in the present paper. This language is a practicaly realized generalization of such mathematical models of algorithm notion as normal algoritm and here introduced Markov-Post algorithm and recursive Markov-Post algorithm. That is why conditions of time polynomiality of these mathematical models (used in theoretical reseaches) are proved as corollaries of the main theorem. The question whether it is possible to prove that a refal-5 program realizes a polynomiall time function (i.e. function belonging to FP) is very actual. A notion of a double polynomial recursive refal-5 function call, which provides the solution of this question, is introduced in the paper.