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

Abstract

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