11.5. Машины Тьюринга и примитивно рекурсивные функции

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

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

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

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

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

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

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