Всякая эффективно вычислимая функция частично рекурсивна это высказывание принадлежит

Обновлено: 04.11.2024

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

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

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

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

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

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

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

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

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

Частично рекурсивные функции

Операторы примитивной рекурсии и подстановки не выводят нас из класса всюду определенных функций . Не так обстоит дело с оператором минимизации, о котором мы уже упоминали. Он применяется к (k+1) -местной функции f и дает k -местную функцию g , определяемую так: g(x₁. x_k) есть наименьшее y , для которого f(x₁. x_k,y)=0 .

Смысл выделенных слов ясен, если функция f всюду определена. Если нет, то понимать их надо так: значение g(x₁. x_k) равно y , если f(x₁. x_k,y) определено и равно нулю, а все значения f(x₁. y_k,y') при y'<y определены и не равны нулю.

Часто используется обозначение

$g(x_</p> ,\dots ,x_)=\mu y(f(x_,\dots ,x_,y)=0),$

$\mu$

и потому оператор минимизации также называют -оператором.

Ясно, что такое определение обеспечивает вычислимость g , если вычислима f (мы перебираем в порядке возрастания все y , ожидая появления нулевого значения).

88. Покажите, что если изменить определение и разрешить f(x₁. x_k,y') быть не определенным при y'<y , то функция g может быть невычислимой при вычислимой f .

Функции, получающиеся из базисных (нуля, проекции и прибавления единицы) с помощью операторов подстановки, примитивной рекурсии и минимизации, называются частично рекурсивными. Если такая функция оказывается всюду определенной, то ее называют общерекурсивной функцией.

Такая странная терминология, видимо, сложилась в результате переводов с английского. По-английски были " primitive recursive functions " ( примитивно рекурсивные функции ). Затем было дано более общее ( general ) понятие вычислимой всюду определенной функции, и такие функции были названы " general recursive functions ". Затем стали рассматривать и частичные (partial) вычислимые функции, называя их "partial recursive functions". В русском же языке слово "partial" попало не туда, и вместо частичных рекурсивных функций стали говорить о частично рекурсивных функциях . Та же участь постигла и слово " general ", которое странным образом вошло в прилагательное " общерекурсивная" и означает, что функция всюду определена.

Теорема 76. Всякая функция , вычислимая с помощью машины Тьюринга, является частично рекурсивной.

Пусть f вычислимая с помощью машины Тьюринга (обозначим эту машину через M ) функция одного аргумента. Рассмотрим свойство T(x,y,t) , состоящее в том, что машина M на входе x дает ответ y за время не более чем t . Как мы видели выше, по входу машины Тьюринга и по времени t можно примитивно рекурсивно вычислить ее состояние в момент t ; ясно, что можно также узнать, закончила ли она работу, и если да, то был ли ответ равен y . Итак, свойство T примитивно рекурсивно.

Теперь объединим аргументы y и t в пару с помощью примитивно рекурсивной нумерации; получится примитивно рекурсивная функция T' , для которой T'(x,[y,t])=T(x,y,t) ; теперь можно написать (\mu\ z\ T" />
, где p₁ дает по номеру пары ее первый член, а означает " наименьшее z , для которого, .. .". Таким образом, функция f является частично рекурсивной.

Верно и обратное: Теорема 77. Всякая частично рекурсивная функция вычислима на машине Тьюринга.

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

После этого остается только сослаться на то, что всякая функция , вычисляемая программой с конечным числом регистров, вычислима на машине Тьюринга (как мы видели в разделе 10.2, теорема 66).

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

На самом деле история здесь сложнее и примерно может быть описана так. Определение примитивно рекурсивной функции было дано великим логиком Куртом Геделем и использовано как техническое средство при доказательстве теоремы Геделя о неполноте, в начале 1930-х годов. Он же дал определение общерекурсивной функции (не совпадающее с приведенным нами, но эквивалентное ему). Американский логик Алонзо Черч сформулировал свой тезис для всюду определенных функций , предположив, что всякая вычислимая всюду определенная функция является общерекурсивной. Затем американский математик Клини предложил распространить этот тезис на функции, не являющиеся всюду определенными.

Параллельно английский математик Тьюринг и американский математик Пост предложили свои модели абстрактных вычислительных машин (машины Тьюринга и Поста), отличающиеся лишь некоторыми деталями, и высказали предположение о том, что такие машины покрывают весь класс алгоритмических процессов. Вскоре стало ясно, что вычислимость функции на таких машинах равносильна частичной рекурсивности. (Исторические подробности можно узнать из книги Клини [4].)

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

(Заметим в скобках, что еще одна вычислительная модель нормальные алгорифмы, или алгоритмы Маркова, были предложены Андреем Андреевичем Марковым-младшим (сыном старшего, в честь которого названы марковские цепи и марковские процессы). Это было уже в 1950-ые годы. Марков писал слово алгорифм через " ф ". Соответствующий принцип (всякий алгорифм эквивалентен нормальному) он называл принципом нормализации. В его работах нормальные алгорифмы использовались для построения неразрешимого ассоциативного исчисления. Кроме того, Марков реально выписал во всех деталях конструкцию универсального алгоритма и провел точное доказательство его корректности; кажется, это достижение остается никем не повторенным ни у кого больше не хватило настойчивости, чтобы для какого-то языка программирования написать на этом языке его интерпретатор и формально доказать его корректность .)

Читайте также: