Алгоритмы Маркова-Турчина и доказательства полиномиальной эффективности программ на языке рефал-5

Abstract

Вводятся алгоритмы Маркова-Турчина как обобщение алгоритмов, введённых автором в [5], и являющиеся существенной модификацией программ, написанных на языке рефал-5. Предлагается критерий их эффективности для реализации на машине Тьюринга за полиномиальное число шагов. Этот критерий не использует ограничения памяти, в отличие от того, как это было установлено в [3] для дважды полиномиальных программ на языке рефал-5. Критерий основан на специального вида рекурсии в программах, являющейся существенным обобщением хвостовой рекурсии, предложенной Т. Борландом для программ на турбо прологе. Это обобщение связано с основным типом данных в языке рефал-5, представляющем собой древовидно структурированные тексты посредством круглых скобок. Для алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором) просто доказываются некоторые модификации теорем теории сложности алгоритмов, полезные для математиков-программистов. Иначе говоря, вводится математическое понятие алгоритма, модифицирующее (в основном, упрощающее, а также объединяющее в единый алгоритм все вспомогательные алгоритмы с помощью использования встроенного интерпретатора) понятие рефал-5 функции, введённой В.Ф. Турчиным (см., например, [2, 6]), в частности, путем расширения понятия нормального алгоритма А.А. Маркова на древовидно оформленные тексты с помощью структурных (круглых) скобок. Введение встроенного динамического интерпретатора (в терминологии В.Ф. Турчина – расширения встроенной метауниверсальной функции), вычисляющего применение любого алгоритма с динамически полученной его записью к исходным данным, является существенным расширением понятия алгоритма Маркова. Известно, что на практике алгоритмы и исходные данные ограничены по длине. В статье также доказываются теоремы о вариантах проблемы применимости алгоритмов Маркова-Поста с учётом этого обстоятельства. Точнее, доказываются нижние оценки длины программ, разрешающих проблему применимости коротких программ к коротким данным на языке алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором). С. 41-49.