Машины Тьюринга и рекурсивные функции

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

Теорема 75. Любая функция, вычислимая на машине Тьюринга не более чем за примитивно рекурсивное (от длины входа) время, примитивно рекурсивна.

Напомним, что мы считаем входом и выходом машины Тьюринга слова из нулей и единиц. Поскольку аргументами и значениями примитивно рекурсивных функций являются числа, теорема будет иметь смысл, только если мы договоримся отождествлять числа и слова. Как уже говорилось, мы отождествляем число n со словом, которое получается после удаления старшего бита 1 в двоичном разложении числа n+1.

При имитации работы машин Тьюринга с помощью программ мы кодировали состояние машины четырьмя числами (код левой части ленты, код правой части ленты, состояние и буква под головкой). При этом удобно было такое кодирование: левую часть ленты мы считали записью числа в системе счисления, в которой основание равно числу символов в алфавите машины, а пробел считается нулем; с правой частью ленты мы поступали так же, только в обратном порядке (младшие разряды у головки). При этом добавление или изъятие символа у головки соответствовало простой арифметической операции (удаление это деление нацело, добавление умножение на основание системы счисления и сложение). При таком кодировании функции перехода (четыре функции четырех аргументов, показывающие следующее состояние как функцию предыдущего), записываются простыми формулами и примитивно рекурсивны.

Теперь рассмотрим итерированную функцию перехода, которая говорит, каково будет состояние машины Тьюринга после t шагов. Точнее, тут имеются четыре функции от пяти аргументов (первые четыре аргумента кодируют состояние, пятый представляет собой число шагов). Их определение имеет вид совместной рекурсии, которую мы только что разобрали. Поэтому эти функции примитивно рекурсивны. Будем считать, что после появления заключительного состоянии конфигурация машины не меняется. Если мы знаем, что число шагов работы ограничено примитивно рекурсивной функцией, то достаточно подставить ее на место пятого аргумента (числа шагов), чтобы убедиться, что заключительная конфигурация машины является примитивно рекурсивной функцией от ее начальной конфигурации. Следовательно, результат работы является примитивно рекурсивной функций начального данного.

Это рассуждение неявно использует примитивную рекурсивность различных функций, связанных с переходом от одного представления данных к другому. Например, вход машины Тьюринга является двоичным словом, которое мы договорились отождествлять с некоторым числом x. Этому входу соответствует начальная конфигурация машины Тьюринга, которую мы кодируем четверкой чисел. Нам важно, что эта четверка примитивно рекурсивно зависит от x. Это легко понять, так как преобразование связано с переходом от одной системы счисления к другой (одно и то же слово кодирует разные числа в разных системах счисления); примитивную рекурсивность таких функций легко установить с помощью описанных выше методов. Кроме того, нам надо из выходной конфигурации примитивно рекурсивно извлечь результат и также перекодировать его, а также по входу получить его длину (чтобы подставить в примитивно рекурсивную функцию, ограничивающую число шагов). Но все это также не выходит из круга разобранных выше приемов, и подробно останавливаться на этом мы не будем.

Эта теорема убеждает нас в примитивной рекурсивности многих довольно сложно определяемых функций. Например, рассмотрим функцию n ( n -ый десятичный знак числа ). Известно, что вычислены миллионы таких знаков, поэтому есть все основания полагать, что известные алгоритмы работают не слишком долго было бы очень странно, если бы время их работы (даже учитывая неудобство машины Тьюринга для программирования) не оценивалось бы, скажем, функцией cx 2ⁿ при достаточно большом c. А такая оценка примитивно рекурсивна, что позволяет сослаться на только что доказанную теорему. (На самом деле тут большой запас существуют примитивно рекурсивные функции, которые растут гораздо быстрее 2ⁿ.)

Другое описание класса примитивно рекурсивных функций, более понятное программистам: это функции, которые можно вычислять программой, содержащей if-then-else -ветвления и for -циклы, но не содержащие while -циклов (и тем более go to и разных других пакостей типа изменения параметра for-цикла внутри цикла).

87. Сформулируйте и докажите соответствующее утверждение.