Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Рекурсивные функции

Рекурсивные функции


Содержание

Понятие машины Тьюринга — не единственный известный путь уточнения понятия алгоритма. В настоящем и следующем параграфах будут рассмотрены еще два способа такого уточнения: рекурсивные функции и нормальные алгоритмы Маркова.


Происхождение рекурсивных функций


Всякий алгоритм однозначно сопоставляет допустимым начальным данным результат. Это означает, что с каждым алгоритмом однозначно связана функция, которую он вычисляет. В предыдущем параграфе были рассмотрены примеры функций, которые вычисляются с помощью алгоритма, названного машиной Тьюринга. Возникает естественный вопрос, для всякой ли функции существует вычисляющий ее алгоритм. Учитывая сформулированный ранее тезис Тьюринга, утверждающий, что функция вычислима с помощью какого-нибудь алгоритма тогда и только тогда, когда она вычислима с помощью машины Тьюринга, данный вопрос трансформируется в следующий. Для всякой ли функции можно указать вычисляющую ее машину Тьюринга? Если нет, то для каких функций существует вычисляющий их алгоритм (машина Тьюринга), как описать такие, как говорят, алгоритмически или эффективно вычислимые функции?


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


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




Основные понятия теории рекурсивных функций и тезис Чёрча


Приступим к построению класса рекурсивных функций в соответствии с изложенными принципами. Напомним, что рассматриваются функции, заданные на множестве натуральных чисел и принимающие натуральные значения. Функции предполагается брать частичные, т. е. определенные, вообще говоря, не для всех значений аргументов. В качестве исходных простейших функций выберем следующие:


S(x)=x+1 (функция следования);
O(x)=0 (нуль-функция);
I_m^n(x_1,x_2,\ldots,x_n)=x_m (функции-проекторы, 1\leqslant m\leqslant n).

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


Определение 33.1 (оператор суперпозиции). Будем говорить, что n-местная функция \varphi получена из m-местной функции f и n-местных функций g_1, \ldots,g_m с помощью оператора суперпозиции, если для всех x_1,\ldots,x_n, справедливо равенство:


\varphi(x_1,\ldots,x_n)= f \bigl(g_1(x_1,\ldots,x_n),\,\ldots,\, g_m(x_1,\ldots,x_n)\bigr).

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


Теорема 33.2. Если функции f(x_1,\ldots,x_m),\, g_1(x_1,\ldots,x_n),\ldots, g_m(x_1,\ldots,x_n) правильно вычислимы по Тьюрингу, то правильно вычислима и сложная функция (суперпозиция функций):


\varphi(x_1,\ldots,x_n)= f \bigl(g_1(x_1,\ldots,x_n),\,\ldots,\, g_m(x_1,\ldots,x_n)\bigr).

Доказательство

Руководствуясь определением 32.9 композиции машин Тьюринга, нетрудно понять, что если машина F правильно вычисляет функцию f(y), а машина G правильно вычисляет функцию g(x), то композиция этих машин F\cdot G правильно вычисляет суперпозицию этих функций f(g(x))\colon


\begin{array}{ll}&\qquad q_101^x\,;\\ G\colon&\qquad q01^{g(x)}\,;\\ F\colon&\qquad q01^{f(g(x))}\,. \end{array}

Рассмотрим более сложную суперпозицию вычислимых функций: \varphi(x,y)= f(g_1(x,y), g_2(x,y)). Пусть машины F,\,G_1,\,G_2 правильно вычисляют функции f,\,g_1,\,g_2 соответственно. Сконструируем машину Тьюринга, правильно вычисляющую сложную функцию \varphi(x,y), пользуясь введенными в предыдущей лекции машинами сдвига, транспозиции, копирования и нулевой функции:


\begin{array}{ll} &\qquad q_101^x01^y\,;\\[2pt] K_2\colon&\qquad 01^x01^yq01^x01^y\,;\\[2pt] G_1\colon&\qquad 01^x01^yq01^{g_1(x,y)};\\[2pt] C\colon&\qquad 01^{g_1(x,y)}q01^x01^y\,;\\[2pt] G_2\colon&\qquad 01^{g_1(x,y)}q01^{g_2(x,y)};\\[2pt] B\colon&\qquad q01^{g_1(x,y)}01^{g_2(x,y)};\\[2pt] F\colon&\qquad q01^{f(g_1(x,y), g_2(x,y))};\\[2pt] q0\to q_00\colon&\qquad q_001^{f(g_1,g_2)}. \end{array}

Сконструируйте самостоятельно композицию машин, правильно вычисляющих функцию


\varphi(x,y)= f \bigl(g_1(x,y),\, g_2(x,y),\, g_3(x,y)\bigr).

Подстановки указанного вида достаточно специфичны (все функции g имеют одно и то же число аргументов) и не исчерпывают всевозможных подстановок, которые можно производить над функциями. Но благодаря функциям-проекторам I_m^n этот недостаток легко устраняется: любая суперпозиция функций в функции может быть выражена через суперпозиции указанного вида и функции-проекторы. В самом деле, например, суперпозиция f(g_1(x_1,x_2), g_2(x_1)) может быть в требуемом виде представлена так: f\bigl(g_1(x_1,x_2),\, I_1^2(g_2(x_1), g_3(x_1))\bigr) — любая функция от x_1. В свою очередь, используя подстановку и функции-проекторы, можно переставлять аргументы в функции:


\begin{gathered}f(x_2,x_1,x_3,\ldots,x_n)= f \bigl(I_2^2(x_1,x_2),\, I_1^2(x_1,x_2),\, x_3,\,\ldots,\,x_n\bigr);\\ f(x_1,x_1,x_3,\ldots,x_n)= f \bigl(I_1^2(x_1,x_2),\, I_1^2(x_1,x_2),\, x_3,\,\ldots,\,x_n\bigr);\end{gathered}

Поэтому можно считать, что теорема полностью доказана.


Определение 33.3. Говорят, что (n+1)-местная функция \varphi получена из n-местной функции f и (n +2)-местной функции g с помощью оператора примитивной рекурсии, если для любых x_1,\ldots,x_n,y справедливы равенства:


\begin{gathered}\varphi(x_1,\ldots,x_n,0)= f(x_1,\ldots,x_n);\\ \varphi(x_1,\ldots,x_n, y+1)= g \bigl(x_1,\ldots,x_n, y, \varphi(x_1,\ldots,x_n,y)\bigr). \end{gathered}

Пара этих равенств называется схемой примитивной рекурсии.


Здесь важно отметить то, что, независимо от числа аргументов в \varphi, рекурсия ведется только по одной переменной y; остальные n переменных x_1,\ldots,x_n, на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров. Кроме того, схема примитивной рекурсии выражает каждое значение определяемой функции \varphi не только через данные функции f и g, но и через так называемые предыдущие значения определяемой функции \varphi\colon прежде чем получить значение \varphi(x_1,\ldots,x_n,k), придется проделать k+1 вычисление по указанной схеме — для y=0,1,\ldots,k.


Определение 33.4. Функция называется примитивно рекурсивной, если она может быть получена из простейших функций O,\,S,\,I_m^n с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.


Наконец, введем заключительный, третий, оператор.


Определение 33.5 (оператор минимизации). Будем говорить, что n-местная функция \varphi получается из (n+1)-местных функций f_1 и f_2 с помощью оператора минимизации, или оператора наименьшего числа, если для любых x_1,\ldots,x_n,y равенство \varphi(x_1,\ldots,x_n)=y выполнено тогда и только тогда, когда значения f_i(x_1,\ldots,x_n,0), \ldots, f_i(x_1,\ldots,x_n,y-1) (i=1;2) определены и попарно неравны:


f_1(x_1,\ldots,x_n,0)\ne f_2(x_1,\ldots,x_n,0), \ldots, f_1(x_1,\ldots,x_n,y-1)\ne f_2(x_1,\ldots,x_n,y-1),

а f_1(x_1,\ldots,x_n,y)=f_2(x_1,\ldots,x_n,y). Коротко говоря, величина \varphi(x_1,\ldots,x_n) равна наименьшему значению аргумента y, при котором выполняется последнее равенство. Используется следующее обозначение:


\varphi(x_1,\ldots,x_n)= \mu y \bigl[f_1(x_1,\ldots,x_n,y)= f_2(x_1,\ldots,x_n,y)\bigr].

В частном случае может быть f_2=0. Тогда \varphi(x_1,\ldots,x_n)= \mu y \bigl[f(x_1,\ldots,x_n,y)=0\bigr]. Оператор минимизации называется также µ-оператором. Этот оператор предназначен для порождения следующего важного класса рекурсивных функций.


Определение 33.6. Функция называется частично рекурсивной, если она может быть получена из простейших функций O,\,S,\,I_m^n с помощью конечного числа применений суперпозиции, примитивной рекурсии и µ-оператора. Если функция всюду определена и частично рекурсивна, то она называется общерекурсивной. (Отметим, что не всегда частично рекурсивную функцию можно эффективно доопределить до общерекурсивной.)


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


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


Числовая функция тогда и только тогда алгоритмически (или машинно) вычислима, когда она частично рекурсивна.


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


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




Примитивно рекурсивные функции


Итак, функция примитивно рекурсивна, если она может быть получена из простейших функций O,\,S,\,I_m^n с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии. Рассмотрим ряд примеров примитивно рекурсивных функций.


▼ Примеры 33.7-33.9

Пример 33.7. Покажем, как, исходя из простейших функций, с помощью оператора примитивной рекурсии получить следующую функцию, называемую усеченной разностью:


x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y= \begin{cases}x-y,&\text{if}\quad x \geqslant y,\\ 0,&\text{if}\quad x<y. \end{cases}

Во-первых, отметим, что функция x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1, получающаяся из функции x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y фиксированием второго аргумента, удовлетворяет следующим соотношениям:


\begin{aligned}& 0 \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1=0=O(x);\\ & (x+1) \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1=x= I_1^2(x,y),\end{aligned}

т.е. получена из простейших функций O(x) и I_1^2(x,y) с помощью оператора примитивной рекурсии. Во-вторых, нетрудно понять, исходя из определения усеченной разности, что эта функция удовлетворяет также равенствам:


\begin{aligned}& x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 0=x= I_1^2(x,y);\\ & x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; (y+1)= (x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y) \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1= h(x,y,x -.1 y)\end{aligned}

для любых x и y. Тождества показывают, что двухместная функция x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y получена с помощью оператора примитивной рекурсии из простейшей функции I_1^2(x,y) и функции h(x,y,z)= z \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1.


Пример 33.8. Покажем, что функция s(x,y)=x+y может быть получена из простейших с помощью оператора примитивной рекурсии. Для функции верны следующие тождества:


\begin{aligned}& x+0=x;\\ & x+(y+1)= (x+y)+1, \end{aligned}

которые можно записать в виде


\begin{aligned}s(x,0)=x;\\ s(x,y+1)= s(x,y)+1\end{aligned} или \begin{aligned}s(x,0)= I_1^1(x);\\ s(x.y+1)= S(s(x,y)),\end{aligned},

а это и есть схема примитивной рекурсии, основывающаяся на простейших функциях I_1^1 и S.


Пример 33.9. Аналогично операции сложения, очевидные соотношения для операции умножения


p(x,0)= x\cdot0=0= O(x),\quad p(x,x+1)= x\cdot y+x= p(x,y)+x= x+p(x,y)= s(x,p(x,y))

говорят о том, что функция p(x,y)=x\cdot y получена из простейшей функции O(x,y) и функции s(x,y)=x+y с помощью оператора примитивной рекурсии.


Теорема 33.10. Функция, полученная суперпозицией примитивно рекурсивных функций, сама примитивно рекурсивна.


Доказательство. В самом деле, компоненты этой функции получены из простейших функций O,\,S,\,I_m^n с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии. Чтобы получить рассматриваемую функцию, нужно добавить еще одну суперпозицию. В итоге эта функция также получается из простейших функций в результате конечного числа применений операторов суперпозиции и примитивной рекурсии, т.е. является примитивно рекурсивной.




Примитивная рекурсивность предикатов


Определив ранее понятие предиката, мы отметили, что к этому понятию возможен и еще один подход. Предикат P(x_1,\ldots,x_n), заданный над множествами M_1,\ldots, M_n, есть функция, заданная на указанных множествах и принимающая значения в двухэлементном множестве \{0;1\}. В теории алгоритмов принято различать предикат P и функцию, связанную с ним, а саму функцию называют характеристической функцией предиката P и обозначают \chi_{{}_P}. Таким образом,


\chi_{{}_P}(x_1,\ldots,x_n)= \begin{cases}0,& \text{if}~~ P(x_1,\ldots,x_n)~~\text{is~true},\\ 1,& \text{if}~~ P(x_1,\ldots,x_n)~~\text{is~false}. \end{cases}

Если M_1=\ldots= M_n=N, то \chi_{{}_P} — функция, входящая в круг наших рассмотрений, и имеет смысл поставить вопрос о ее примитивной рекурсивности.


Определение 33.11. Предикат P называется примитивно рекурсивным, если его характеристическая функция \chi_{{}_P} примитивно рекурсивна.


Отметим еще одно важное свойство, связанное с примитивной рекурсивностью функций. Мы используем его в последующих рассмотрениях. Одним из часто встречающихся, особенно в теории алгоритмов, способов задания функций является их задание с помощью так называемого оператора условного перехода. Этот оператор по функциям f_1(x_1,\ldots,x_n),\,f_2(x_1,\ldots,x_n) и предикату P(x_1,\ldots,x_n) строит функцию \varphi\colon


\varphi(x_1,\ldots,x_n)= \begin{cases}f_1(x_1,\ldots,x_n),& \text{if}~~ P(x_1,\ldots,x_n)~~\text{is~true},\\ f_2(x_1,\ldots,x_n),& \text{if}~~ P(x_1,\ldots,x_n)~~\text{is~false}. \end{cases}

Нетрудно понять, что с помощью характеристических функций предиката P и его отрицания \lnot P функцию \varphi можно выразить следующим образом:


\varphi(x_1,\ldots,x_n)= f_1(x_1,\ldots,x_n)\cdot \chi_{{}_P}(x_1,\ldots,x_n)+ f_2(x_1,\ldots,x_n)\cdot \chi_{{}_{\lnot P}}(x_1,\ldots,x_n).

Из этого выражения вытекает следующее утверждение.


Теорема 33.12. Если функции f_1,\,f_2 и предикат P примитивно рекурсивны, то и функция \varphi, построенная из f_1,\,f_2,\,P с помощью оператора Условного перехода, примитивно рекурсивна. Этот факт выражают также говоря, что оператор условного перехода примитивно рекурсивен.


Оператор условного перехода может иметь и более общую форму, когда переход носит не двузначный, а многозначный характер и определяется конечным числом предикатов P_1,\ldots,P_k, из которых истинен всегда один и только один предикат. Ясно, что и в такой форме оператор условного перехода примитивно рекурсивен, так как и в этом случае производимую им функцию можно представить в аналогичном виде:


\varphi(x_1,\ldots,x_n)= f_1\cdot \chi_{{}_{P1}}+ \ldots+ f_k\cdot \chi_{{}_{Pk}}.

Заметим, что это соотношение определяет \varphi и в том случае, когда ни один из P_1,\ldots,P_k не истинен: в этом случае \varphi равно нулю.


Последнее замечание позволяет доказать примитивную рекур-сивность функций, заданных на конечных множествах, ибо все их можно задать с помощью оператора условного перехода. Правда, при этом их придется доопределить с помощью какой-либо константы на всех остальных натуральных числах, на которых она не определена. Например, функцию ф, определенную на множестве \{1,3,9,17\} равенствами \varphi(1)=8,~ \varphi(3)=0, \varphi(9)=4,~ \varphi(17)=6,, с помощью оператора условного перехода можно описать так:


\varphi(x)= \begin{cases}8,&\text{if}\quad x=1,\\ 0,&\text{if}\quad x=3,\\ 4,&\text{if}\quad x=9,\\ 6,&\text{otherwise}. \end{cases}

Таким образом, \varphi(x)=6 вне исходной области задания.


В заключение обсуждения примитивно рекурсивных функций сделаем два важных замечания.


Во-первых, все примитивно рекурсивные функции всюду определены. Это следует из того, что всюду определены простейшие функции, а операторы суперпозиции и примитивной рекурсии это свойство сохраняют.


Во-вторых, строго говоря, мы имеем дело не с функциями, а с их примитивно рекурсивными описаниями. Различие здесь точно такое же, как и различие между булевыми функциями и их представлениями в виде формул. Примитивно рекурсивные описания также разбиваются на классы эквивалентности: в один класс входят все описания, задающие одну и ту же функцию. Но задача распознавания эквивалентности примитивно рекурсивных описаний являет собой еще один пример алгоритмически неразрешимой задачи.




Вычислимость по Тьюрингу примитивно рекурсивных функций


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


Теорема 33.13. Функция \varphi, возникающая примитивной рекурсией из правильно вычислимых на машине Тьюринга функций f и g, сама правильно вычислима на машине Тьюринга.


Доказательство

Для краткости записей будем считать, что функция \varphi связана с функциями f и g следующим образом: \varphi(x,0)= f(x),~ \varphi(x,i+1)= g(x,\varphi(x,i)). Обозначим F и G — машины Тьюринга, правильно вычисляющие функции f и g соответственно. Пусть x,\,y — произвольные натуральные числа. Требуется сконструировать машину Тьюринга, вычисляющую значение \varphi(x,y). Как мы уже отмечали, для вычисления \varphi(x,y) предстоит вычислить y+1 значений \varphi(x,0), \varphi(x,1),\ldots,\varphi(x,y-1),\varphi(x,y).


Начальная конфигурация такова: q_101^x01^y0. Применим к ней следующую последовательность машин Тьюринга: B^{+}V \Gamma VB^{+}F. В результате получим последовательность конфигураций:


\begin{aligned}q_101^x01^y0\quad \mathop{\Rightarrow}\limits^{B^{+}}&\quad 01^xq01^y0\\ \mathop{\Rightarrow}\limits^{V}&\quad 01^yq01^x0 \\ \mathop{\Rightarrow}\limits^{\Gamma}&\quad 01^yq01^x01^x0\\ \mathop{\Rightarrow}\limits^{V}&\quad 01^xq01^y01^x0\\ \mathop{\Rightarrow}\limits^{B^{+}}&\quad 01^x01^yq01^x0\\ \mathop{\Rightarrow}\limits^{F}&\quad 01^x01^yq_{\alpha}01^{\varphi(x,0)}0. \end{aligned}

На последнем шаге, применив машину, вычисляющую функцию f(x), к конфигурации q01^x, мы получим значение f(x), которое, согласно схеме примитивной рекурсии для \varphi, есть \varphi(x,0). (Промежуточным состояниям q мы намеренно не приписывали никаких индексов. Индекс \alpha получило лишь последнее в этой последовательности состояние.)


Теперь мы можем приступить к вычислению \varphi(x,1), используя второе соотношение схемы примитивной рекурсии: \varphi(x,1)= g(x,\varphi(x,0)). Для этого применим сначала к последней конфигурации команды: q_{\alpha}0\to q_{\alpha+1}0L,~ q_{\alpha+1}\to q_{\alpha+2}0. В результате получим конфигурацию: 01^x01^{y-1} q_{\alpha+2}001^{\varphi(x,0)}0. Теперь нужно подготовить ленту машины к применению машины G, вычисляющей значение g(x,\varphi(x,0)), т.е. необходимо получить на ленте конфигурацию q01^x01^{\varphi(x,0)}. Для этого применим к конфигурации 01^x01^{y-1} q_{\alpha+2}001^{\varphi(x,0)}0 последовательность машин AB^{-}VB^{+}V\Gamma VB^{-} VB^{+}B^{+} VB^{-}. Получим последовательность конфигураций:


\begin{aligned}&01^x01^{y-1}q_{\alpha+2}001^{\varphi(x,0)}0 \quad \mathop{\Rightarrow}\limits^{A}\quad 01^x01^{y-1}q01^{\varphi(x,0)}00 \quad \mathop{\Rightarrow}\limits^{B^{-}}\quad 01^xq01^{y-1}01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{V} \\[2pt] &\quad \mathop{\Rightarrow}\limits^{V}\quad 01^{y-1}q01^{x}01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{B^{+}}\quad 01^{y-1}01^{x}q01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{V}\quad 01^{y-1}01^{\varphi(x,0)}q01^{x} \quad \mathop{\Rightarrow}\limits^{\Gamma}\\[2pt] &\quad \mathop{\Rightarrow}\limits^{\Gamma}\quad 01^{y-1}01^{\varphi(x,0)}q01^{x}01^{x} \quad \mathop{\Rightarrow}\limits^{V}\quad 01^{y-1}01^{x}q01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{B^{-}}\quad 01^{y-1}q01^{x}01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{V}\\[2pt] &\quad \mathop{\Rightarrow}\limits^{V}\quad 01^{x}q01^{y-1}01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{B^{+}}\quad 01^{x}01^{y-1}q01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{B^{+}}\\[2pt] &\quad \mathop{\Rightarrow}\limits^{B^{+}}\quad 01^{x}01^{y-1}01^{\varphi(x,0)}q01^{x} \quad \mathop{\Rightarrow}\limits^{V}\quad 01^{x}01^{y-1}01^{x}q01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{B^{-}}\quad 01^{x}01^{y-1}q01^{x}01^{\varphi(x,0)}. \end{aligned}

Теперь мы можем применить машину G и вычислить значение


\varphi(x,1)= g\bigl(x,\varphi(x,0)\bigr)\,\colon 01^x01^{y-1} q_{\beta}01^{\varphi(x,0)}.

Применим к этой конфигурации команду: q_{\beta}0\to q_{\alpha}0, зацикливающую программу. Получим конфигурацию: 01^x01^{y-1}q_{\alpha}01^{\varphi(x,1)}.


Начинается следующий цикл, осуществляемый командами идущими после первого появления состояния q_{\alpha}. Этот цикл пре' образует конфигурацию вида 01^x01^{y-i}q_{\alpha}01^{\varphi(x,1)} в конфигурации 01^x01^{y-(i+1)}q_{\beta}01^{\varphi(x,i+1)} при условии, что y>i. Команда q_{\beta}0\to q_{\alpha}0 зацикливает программу, и в результате работы цикла параметр y-i будет понижаться до тех пор, пока не получится конфигурация 01^x0 q_{\alpha}01^{\varphi(x,y)}, которая в силу команды q_{\alpha}0\to q_{\alpha+1}0L перейдете конфигурацию 01^xq_{\alpha+1}001^{\varphi(x,y)}.


Дополнительные команды q_{\alpha+1}0\to q_{\beta+1}0,\, A,\,V,\,O,\,V,\,B^{-},\,A создают на ленте требуемую конфигурацию q_001^{\varphi(x,y)}, доказывающую, что функция \varphi(x,y) правильно вычислена на машине Тьюринга.


Следствие 33.14. Всякая примитивно рекурсивная функция вычислима по Тьюрингу.


Доказательство. Утверждение следует (ввиду определения 33.4 примитивно рекурсивной функции) из вычислимости по Тьюрингу простейших функций и свойств сохранения такой вычислимости операторами суперпозиции (теорема 33.2) и примитивной рекурсии (теорема 33.13).




Функции Аккермана


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


Применив теоретико-множественное понятие о мощности, достаточно легко ответить отрицательно на более общий вопрос: исчерпывается ли класс всех функций примитивно рекурсивными функциями, т. е. все ли функции являются примитивно рекурсивными?


Теорема 33.15. Существуют функции, не являющиеся примитивно рекурсивными.


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


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


Пример 33.16. Искомая функция конструируется с помощью последовательности вычислимых функций, в которой каждая функция растет существенно быстрее предыдущей.


Доказательство

Начнем с построения такой последовательности. Мы знаем, что произведение растет быстрее суммы, а степень — быстрее произведения. Начнем построение последовательности именно с этих функций, введя для них единообразные обозначения:


P_0(a,y)= a+y;\qquad P_1(a,y)=a\cdot y;\qquad P_2(a,y)=a^y.

Эти функции связаны между собой следующими рекурсивными соотношениями:


\begin{aligned}P_1(a,y+1)&= a+ay= P_0(a, P_1(a,y)),\quad P_1(a,1)=a;\\ P_2(a,y+1)&= a\cdot a^y= P_1(a, P_2(a,y)),\quad P_2(a,1)=a. \end{aligned}

Продолжим эту последовательность, положив по определению для n=2,3,\ldots\colon


\left.{\begin{aligned}&P_{n+1}(a,0)=1,\\ &P_{n+1}(a,1)=a,\\ &P_{n+1}(a,y+1)= P_n(a,P_{n+1}(a,y)).\end{aligned}}\right\}
(1)

(Первое из равенств (1) предназначено для того, чтобы функции P_n(a,y) были всюду определены.) Эта схема имеет вид примитивной рекурсии, и, следовательно, все функции P_n(a,y) примитивно рекурсивны. Растут они крайне быстро. Например, P_3(a,1)=a,~ P_3(a,2)= P_2(a,a)=a^a,~\ldots. Значение P_3(a,k+1) получается в результате возведения числа a в степень a k-раз.


Зафиксируем теперь значение a=2. Получим последовательность функций от одного аргумента: P_0(2,y),\, P_1(2,y),\,\ldots. Введен, две новые функции: B(x,y)= P_x(2,y) (она перечисляет последнюю последовательность) и A(x)= B(x,x). Первая из них называется функцией Аккермана, а вторая — диагональной функцией Аккермана.


Для функции B(x,y) на основании введенных выше обозначений и соотношений (1) вытекают следующие равенства:


\left.{\begin{aligned}& B(0,y)=2+y,\\ & B(x+1,0)= \operatorname{sg}(x),\\ & B(x+1,y+1)=B(x,B(x+1,y)), \end{aligned}}\right\}
(2)

которые позволяют вычислять значение функции B(x,y), а следовательно, и значения функции A(x). При этом в процессе вычисления значения функции B(x,y) в некоторой точке используются вычисленные ранее ее значения в неких предыдущих точках. Этим схема (2) похожа на схему примитивной рекурсии. Но примитивная рекурсия ведется по одному аргументу, а в схеме (2) рекурсия ведется сразу по двум аргументам (такая рекурсия называется двойной, двухкратной, или рекурсией второй ступени). При этом существенно усложняется характер упорядочения точек, а следовательно, и понятие предшествующей точки. Это упорядочение не предопределено заранее, как в схеме примитивной рекурсии, где число n всегда предшествует числу n+1, а выясняется в ходе вычислений и для каждой схемы (2), вообще говоря, различно. Например, B(3,3)= B(2,B(3,2)), а так как


B(3,2)= P_3(2,2)= P_2(2,P_3(2,1))= P_2(2,2)=2^2=4,

то вычислению B в точке (3,3) по схеме (2) должно предшествовать вычисление B в точке (2, 4): B(3,3)= B(2,4)= P_2(2,4)=24=16. Проверьте самостоятельно, что вычислению B в точке (3 4) должно предшествовать вычисление в точке (2,16).


Итак, функция B(x,y), а вместе с ней и функция A(x) вычислимы (по схеме (2)), а значит, в силу гипотезы Тьюринга, вычислимы посредством подходящей машины Тьюринга. Возникает вопрос, можно ли их вычисление свести к вычислению по схеме примитивной рекурсии, т. е. будут ли эти функции примитивно рекурсивными. Именно такова ситуация с функцией Аккермана A(x). Идея доказательства того, что функция A(x) не является примитивно рекурсивной, состоит в доказательстве того, что функция A(x) растет быстрее, чем любая примитивно рекурсивная функция, и поэтому не может быть примитивно рекурсивной. Более точно, для любой примитивно рекурсивной функции f(x) от одного аргумента найдется такое n, что для любого x\geqslant n будет A(x)>f(x). (Это доказал Аккерман в 1928 г.)


Идея доказательства этого утверждения состоит в следующем. Сначала доказываются два свойства функции B(x,y), которые используются в дальнейшем:


\begin{aligned}& B(x,y+1)> B(x,y)\quad (x,y=1,2,\ldots);\\ & B(x+1,y)\geqslant B(x,y+1)\quad (x \geqslant 1,~ y \geqslant 2). \end{aligned}

Затем вводится понятие B-мажорируемой функции. Функция f(x_1,\ldots,x_n) называется B-мажорируемой, если


(\exists m\in \mathbb{N})(\forall x_1,\ldots,x_n) \bigl[\max(x_1,\ldots,x_n)>1\to f(x_1,\ldots,x_n)< B(m,\max(x_1,\ldots,x_n))\bigr].

Доказывается, что все примитивно рекурсивные функции B-мажорируемы. (Сначала устанавливается B-мажорируемость простейших функций O,\,S(x),\,I_m^n(x). Затем доказывается, что оператор суперпозиции, примененный к B-мажорируемым функциям, дает B-мажорируемую функцию. Аналогичным свойством обладает и оператор примитивной рекурсии.)


Наконец, рассмотрим произвольную примитивно рекурсивную функцию f(x). В силу предыдущего утверждения, для некоторого m и любого x\geqslant 2 имеем f(x)<B(m,x). Но тогда A(m+x)= B(m+x,m+x)> B(m,m+x)> f(m+x). (Предпоследнее неравенство получено исходя из двух свойств функции B(x,y), сформулированных вначале.) Это и означает, что A(x)>f(x), начиная по меньшей мере с x=m+2.


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




Оператор минимизации


Это — оператор наименьшего числа в определении 33.5. В более общем виде его можно определить как оператор, применяемый к произвольному (n+1)-местному предикату P(x_1,\ldots, x_n,y) и дающий в результате n-местную функцию \varphi(x_1,\ldots,x_n). Значение \varphi(a_1,\ldots,a_n) этой функции на наборе аргументов a_1,\ldots,a_n равно наименьшему из таких чисел y, что высказывание \mu y P(a_1,\ldots,a_n,y) истинно. Оно обозначается \mu y P(a_1,\ldots,a_n,y). Если же наименьшего среди таких чисел не существует, то значение функции \varphi(x_1,\ldots,x_n) на этом наборе a_1,\ldots,a_n не определено. (Это означает, что оператор минимизации может породить частичную, т. е. не всюду определенную функцию.) Таким образом, \varphi(x_1,\ldots,x_n)= \mu yP(x_1,\ldots, x_n,y). Оператор минимизации называется также оператором наименьшего числа, или µ-оператором.


Предикат P(x_1,\ldots,x_n,y) (заданный над N), к которому при. меняется оператор минимизации, может быть сконструирован из двух числовых функций следующим образом: "f_1(x_1,\ldots,x_n,y)= f_2(x_1,\ldots,x_n,y)", или из одной: "f(x_1,\ldots, x_n,y)=0". Так что оператор минимизации можно рассматривать как оператор, заданный на множестве числовых функций и принимающий значения в нем же.


В этом своем качестве оператор минимизации является удобным средством для построения обратных функций. Действительно, функция f^{-1}(x)= \mu y[f(y)=x] (наименьший y такой, что f(y)=x) является обратной для функции f(x). (Поэтому в применении к одноместным функциям оператор минимизации иногда называют оператором обращения.)


Рассмотрим примеры действия оператора минимизации для получения обратных функций.


▼ Примеры 33.17-33.18

Пример 33.17. Рассмотрим следующую функцию, получающуюся с помощью оператора минимизации:


d(x,y)= \mu z[y+z=x]= \mu z \bigl[s(I_2^3(x,y,z), I_3^3(x,y,z))= I_1^3(x,y,z)\bigr].

Вычислим, например, d(7,2). Для этого нужно положить y=2 и, придавая переменной z последовательно значения 0,1,2,\ldots, каждый раз вычислять сумму y+z. Как только она станет равной 7, то соответствующее значение z принять за значение d(7,2). Вычисляем:


\begin{aligned}&z = 0,~~2+0 = 2 \ne 7 ;\\ &z= 1,~~ 2+ 1 = 3 \ne 7 ;\\ &z=2,~~ 2+2 = 4 \ne 7 ;\\ &z = 3,~~ 2 + 3 = 5\ne 7;\\ &z= 4,~~ 2 + 4 = 6 \ne 7 ;\\ &z = 5,~~ 2 + 5 = 7.\end{aligned}


Таким образом, d(7,2)=5.


Попытаемся вычислить по этому правилу d(3,4)\colon


\begin{aligned}&z = 0,~~ 4 + 0 = 4 > 3 ;\\&z= 1,~~ 4+ 1 = 5 > 3;\\&z = 2,~~ 4 + 2 = 6 > 3 ;\\&\ldots \ldots\ldots\ldots\ldots \end{aligned}


Видим, что данный процесс будет продолжаться бесконечно. Следовательно, d(3,4) не определено.


Пример 33.18. Аналогично, с помощью оператора минимизации можно получить частичную функцию, выражающую частное от деления двух натуральных чисел:
x\!\!\not{\phantom{|}}\,y= q(x,y)= \mu z[y\cdot z=x]= \mu z \bigl[p(I_2^3(x,y,z), I_3^3(x,y,z))= I_1^3(x,y,z)\bigr].

Заметим, что обе функции из двух последних примеров не всюду определены, т. е. являются частичными.


С помощью µ-оператора можно построить некоторые всюду определенные аналоги рассмотренных функций:


\begin{aligned}&[x-y]= \mu z[y+z \geqslant x]= \mu z[y+z+1>x];\\ &[x\!\!\not{\phantom{|}}\,y]= \mu z[y(z+1)>x].\end{aligned}

Первая из этих функций равна 0, если x<y, и равна x-y, если x\geqslant y. Вторая представляет собой целую часть функций x\!\!\not{\phantom{|}}\,y.


Заметим, что механизм проявления неопределенности функции в точке при вычислении ее значения с помощью µ-оператора такой же, как и при вычислении ее на машине Тьюринга: в случае неопределенности процесс вычисления не останавливается, а продолжается неограниченно долго.




Общерекурсивные и частично рекурсивные функции


Итак, функция называется частично рекурсивной (определение 33.6), если она может быть построена из простейших функций O,\,S,\,I_m^n с помощью конечного числа применений суперпозиции, примитивной рекурсии и µ-оператора. Если функция всюду определена и частично рекурсивна, то она называется общерекурсивной.


Мы уже отмечали, что класс частично рекурсивных функций шире класса примитивно рекурсивных функций, так как все примитивно рекурсивные функции всюду определены, а среди частично рекурсивных функций встречаются функции, не всюду определенные, например функции d(x,y) и q(x,y), рассмотренные в примерах 33.17, 33.18, а также, например, нигде не определенная функция f(x)= \mu y[x+1+y=0]. Примером общерекурсивной, но не примитивно рекурсивной функции может служить и функция Аккермана A(x).


Продолжим теперь продвижение к поставленной цели — к описанию всех функций, вычислимых на машинах Тьюринга. Следующий шаг — доказательство того, что все частично рекурсивные Функции вычислимы по Тьюрингу.




Вычислимость по Тьюрингу частично рекурсивных функций


Теорема 33.19. Если функция f(x,y) правильно вычислима на машине Тьюринга, то и функция \varphi(x)= \mu y[f(x,y)=0]. получающаяся с помощью оператора минимизации из функции f(x,y), также правильно вычислима на машине Тьюринга.


Доказательство

Обозначим F — машину Тьюринга, правильно вычисляющую функцию f(x,y). Используя ее, сконструиру-ем такую машину Тьюринга, которая для заданного значения х вычисляет последовательно значения f(x,0), f(x,1), f(x,2),\ldots до тех пор, пока в первый раз получится f(x,i)=0. После этого машина Должна выдать на ленту число i, представляющее собой значение Функции \varphi(x)=i. Если же для всех i будет иметь место f(x,i)>0, то машина должна работать вечно, и это будет означать, что функция \varphi не определена в точке x. Начальная конфигурация на конструируемой машине такова: q_101^x0. Будем мыслить ее следующим образом: q_101^x01^0 и начнем с применения к ней машины "копирование" \mathsf{K}_2. Получим конфигурацию: 01^x01^0q01^x01^0. Теперь вычислим значение f(x,0), применив машину F\colon\, 01^x01^0q_{\alpha}01^{f(x,0)}.


Далее подбираем команды, которые при условии f(x,i)>0 преобразовывают конфигурацию 01^x01^iq01^{f(x,i)} в конфигурацию 01^x01^{i+1}q01^{f(x,i+1)}\colon


\begin{array}{rl}q_{\alpha}0 \to q_{\alpha+1}0\Pi\colon &\qquad 01^x01^0q_{\alpha+1}1^{f(x,0)};\\ q_{\alpha+1}1 \to q_{\alpha+2}0\colon &\qquad 01^x01^0q_{\alpha+2}01^{f(x,0)-1};\\ q_{\alpha+2}0 \to q_{\alpha+3}0L\colon &\qquad 01^x01^0q_{\alpha+3}001^{f(x,0)-1};\\ q_{\alpha+3}0 \to q_{\alpha+4}1\colon &\qquad 01^x01^0q_{\alpha+4}101^{f(x,0)-1};\\ q_{\alpha+4}1 \to q_{\alpha+5}1\Pi\colon &\qquad 01^x01^1q_{\alpha+5}01^{f(x,0)-1};\\ O\colon &\qquad 01^x01^1q0;\\ B^{-}B^{-}\colon &\qquad q01^x01^1;\\ K_2\colon &\qquad 01^x01^1q01^x01^1;\\ F\colon &\qquad 01^x01^1q_{\beta}01^{f(x,1)};\\ q_{\beta}0\to q_{\alpha}0\colon &\qquad 01^x01^1q_{\alpha}01^{f(x,1)}.\end{array}

Последняя команда зацикливает программу, и машина от конфигурации 01^x01^1q_{\alpha}01^{f(x,1)} переходит к конфигурации 01^x01^2q_{\alpha}01^{f(x,2)}, затем к конфигурации 01^x01^3q_{\alpha}01^{f(x,3)} и т.д. Допустим, что по истечении некоторого времени машина достигла конфигурации 01^x01^iq_{\alpha}01^{f(x,i)}, при которой f(x,i)=0. Это означает, что f(x,i)=0 и машина должна выдать этот результат. Число i накоплено в "счетчике" 01^i. Поэтому поступаем следующим образом. Уже имеющаяся команда q_{\alpha}0\to q_{\alpha+1}0\Pi приведет машину к конфигурации 01^x01^i0q_{\alpha+1}0. Следующие команды выдают на ленту необходимую конфигурацию q_001^i, то есть q_001^{\varphi(x)}\colon


\begin{array}{rl}q_{\alpha+1}0\to q_{\gamma}0\colon &\qquad 01^x01^iq_{\alpha}0;\\ B^{-}B^{-}\colon &\qquad 01^xq01^i;\\ BOB^{-}\colon &\qquad q_{\delta}01^i;\\ q_{\delta}0\to q_00\colon &\qquad q_001^{\varphi(x)}.\end{array}

Теорема доказана.


Следствие 33.20. Всякая частично рекурсивная функция вычислима по Тьюрингу.


Доказательство. Итак, поскольку оператор минимизации сохраняет свойство вычислимости по Тьюрингу (этим же свойством, как было установлено выше, обладают и операторы суперпозиции и примитивной рекурсии), простейшие функции O,\,S,\,I_m^n вычислимы по Тьюрингу, а всякая частично рекурсивная функция получается из простейших с помощью применения конечного числа раз трех указанных операторов, то всякая частично рекурсивная функция вычислима по Тьюрингу.




Частичная рекурсивность функций, вычислимых по Тьюрингу


Наконец мы расширили класс вычислимых по Тьюрингу функций до таких размеров, что он исчерпывает класс всех вычислимых по Тьюрингу функций. Это нам и предстоит доказать. Другими словами, мы намерены доказать, что вычислимы по Тьюрингу лишь частично рекурсивные функции, т.е. если функция вычислима по Тьюрингу, то она частично рекурсивна. Еще точнее, по функциональной схеме (программе) машины Тьюринга, вычисляющей функцию f(x_1,\ldots, x_n), можно построить рекурсивное описание этой функции. Эта теорема впервые была доказана Тьюрингом.


Теорема 33.21. Если функция вычислима по Тьюрингу, то она частично рекурсивна.


Доказательство

Прежде чем приступить к доказательству теоремы, обратим внимание на следующее обстоятельство. Машина Тьюринга, преобразовывающая слова в алфавите A=\{a_0,a_1,\ldots, a_{m-1}\}, никак не различает природу этого алфавита. В частности, она никак не отличает числа от "нечисел": работая с числами, машина не считает их в смысле известных арифметических правил, а преобразовывает слова, представляющие собой записи чисел на каком-то языке (в какой-то системе счисления). Правила преобразований задаем мы с помощью соответствующей программы, и мы же даем полученному машиной словесному результату числовую интерпретацию. Именно в этом смысле мы говорили о вычислимости машиной Тьюринга тех или иных числовых функций. Чтобы доказать сформулированную теорему, необходимо идею арифметической (числовой) интерпретации работы машины Тьюринга довести до определенного совершенства и показать, что любое преобразование, осуществляемое машиной Тьюринга, если его интерпретировать как вычисление, является частично рекурсивным.


Разделим доказательство на этапы (их будет пять).


Первый этап. Арифметизация машин Тьюринга начинается с того, что мы вводим в машину своего рода арифметическую систему координат. Эта система координат предназначена для конфигураций машины. Как известно, в каждый момент времени конфигурация на ленте машины Тьюринга имеет вид \alpha q_ia_j \beta, где \alpha — слово в алфавите A=\{a_0,a_1,\ldots, a_{m-1}\}, записанное на ленте левее обозреваемой в данный момент ячейки; q_i — состояние, в котором находится в данный момент машина; a_j — содержимое обозреваемой в данный момент ячейки; \beta — слово в алфавите A, записанное на ленте правее обозреваемой ячейки. Указанной конфигурации однозначно сопоставляется упорядоченная четверка (\widetilde{\alpha}, \widetilde{q}_i, \widetilde{a}_j, \widetilde{\beta}) чисел, определяемых следующим образом: \widetilde{q}_i=i;~ \widetilde{a}_j=j;~ \widetilde{\alpha} — число, изображаемое цифрами, полученными кодированием символов слова \alpha по следующему правилу: эти символы интерпретируются как m-ичные цифры, т.е. цифры m-ичной системы счисления, т.е. a_i кодируется цифрой i; \widetilde{\beta} аналогично получается из \beta, но при этом читается справа налево, т.е. крайняя слева ячейка \beta содержит самый младший разряд, а крайняя справа — самый старший (это сделано для того, чтобы нули справа от \beta не влияли на значение \widetilde{\beta}).


Завершим кодирование элементов машины Тьюринга. Символу a_0 пустой ячейки сопоставим число 0, сдвигу вправо \Pi сопоставим 1, сдвигу влево L — 2, отсутствию сдвига C сопоставим 0, буквой z закодируем заключительное состояние (состояние остановки) q_0. В итоге алфавит A закодируется числовым множеством \widetilde{A}, а алфавит Q — числовым множеством \widetilde{Q}.


Тогда, например, если мы имеем машину Тьюринга с внешним алфавитом A=\{a_0, a_1\} и на ее ленте имеется конфигурация a_1a_0a_1a_1a_0q_3a_1a_1a_0a_1a_1, то при нашей кодировке (или координатизации) ей соответствует следующая упорядоченная четверка натуральных чисел: (22, 3, 1, 13). Поясним, как она получилась. В нашей конфигурации \alpha=a_1a_0a_1a_1a_0, q_i=q_3,~ a_j=a_1, \beta= a_1a_0a_1a_1. Поэтому \widetilde{\alpha}=10110 — двоичное число, которое следующим образом переводится в десятичное:


[10110]_2=1\cdot 2^4+0\cdot 2^3+ 1\cdot 2^2+1\cdot 2^1+ 0\cdot 2^0=22

Далее, \widetilde{q}_3=3,~ \widetilde{a}_1=1 и, наконец, \widetilde{\beta}= [1101]_2=13.


Второй этап. При таком кодировании система команд машины Тьюринга с алфавитом A и множеством состояний Q превращается в тройку числовых функций:


\varphi_a\colon~ \widetilde{Q}\times \widetilde{A}\to \widetilde{A} (функция печатаемого символа);
\varphi_q\colon~ \widetilde{Q}\times \widetilde{A}\to \widetilde{Q} (функция следующего состояния);
\varphi_d\colon~ \widetilde{Q}\times \widetilde{A}\to \{0,1,2\} (функция сдвига).

Например, если среди команд машины Тьюринга имеется команда q_ia_j\to q'_ia'_jX, то


\varphi_a(\widetilde{q}_i, \widetilde{a}_j)= \widetilde{a}'_j,\qquad \varphi_q(\widetilde{q}_i, \widetilde{a}_j)= \widetilde{q}'_i,\qquad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)= \xi,

где \xi=0,\,1,\,2, если X=C,\,\Pi,\,L соответственно.


Отметим, что все эти функции \varphi_a,\,\varphi_q,\,\varphi_d заданы на конечном множестве \widetilde{Q}\times \widetilde{A} и потому примитивно рекурсивны.


Третий этап. Выполнив одну команду, машина Тьюринга преобразует имеющуюся на ленте конфигурацию K=\alpha q_ia_j \beta в новую конфигурацию K'=\alpha' q'_ia'_j \beta'. При арифметизации это означает, что упорядоченной четверке чисел (\widetilde{\alpha},\widetilde{q}_i,\widetilde{a}_j, \widetilde{\beta}), соответствующей конфигурации K, однозначно сопоставляется упорядоченная четверка чисел (\widetilde{\alpha}',\widetilde{q}'_i,\widetilde{a}'_j, \widetilde{\beta}'), соответствующая конфигурации K'.


Например, при команде q_3a_1\to q_4a_0 ранее приведенная конфигурация перейдет в конфигурацию K'= a_1a_0a_1a_1a_0a_0 q_4a_1a_0a_1a_1, которой соответствует четверка чисел (44,4,1,6).


Так будет происходить почти со всеми конфигурациями, связанными с алфавитами A,\,Q. В итоге на множестве таких конфигураций будет задана (вообще говоря, не всюду определенная, т.е. частичная) нечисловая функция \psi_{\Theta}(K)=K', обусловленная данной машиной Тьюринга \Theta. Назовем ее функцией следующего шага.


При введенной арифметизации этой функции соответствует четверка числовых функций следующего шага. Иначе говоря, \widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}' — это числовые функции, каждая из которых зависит от четырех числовых переменных \widetilde{\alpha}, \widetilde{q}, \widetilde{a}, \widetilde{\beta}. Попытаемся понять, как эти функции связаны с функциями системы команд \varphi_a, \varphi_q, \varphi_a. Во-первых, ясно, что \widetilde{q}'_i= \varphi_q и функция \widetilde{q}' фактически не зависит от \widetilde{\alpha},\, \widetilde{\beta}, а зависит лишь от \widetilde{q},\, \widetilde{a}, то есть \widetilde{q}'(\widetilde{\alpha}', \widetilde{q}'_i, \widetilde{a}'_j, \widetilde{\beta}')= \varphi_q(\widetilde{q}_i, \widetilde{a}_j).


Рассмотрим теперь функцию \widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_i, \widetilde{a}_j, \widetilde{\beta}). Если при рассматриваемом такте работы машины ее головка осталась на месте, т.е. обозреваемая ячейка не изменилась, т.е. \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=0, то ясно, что \widetilde{\alpha}'= \widetilde{\alpha}. Если головка сдвинулась вправо, т.е. \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=1, то это означает, что степень каждого разряда числа \widetilde{\alpha} повысилась на единицу: нулевой разряд стал первым, первый — вторым и т.д., т.е. число \widetilde{\alpha} увеличилось в m раз (напомним, что m — число элементов в алфавите A, т.е. основание системы счисления, в которой рассматривается наша арифметизация): m\widetilde{\alpha}. Кроме того, в образовавшийся младший (нулевой) разряд помещается та m-ичная цифра, которая соответствует при кодировании только что вписанному на ленту элементу из A. Эта цифра равна \varphi_a(\widetilde{q}_i, \widetilde{a}_j). В итоге получим, что при сдвиге вправо: \widetilde{\alpha}'( \widetilde{\alpha}', \widetilde{q}'_i, \widetilde{a}'_j, \widetilde{\beta}')= m \widetilde{\alpha}+ \varphi_a(\widetilde{q}_i, \widetilde{a}_j). Наконец, при сдвиге на данном шаге головки влево, т.е. при \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=2, степень каждого разряда числа \widetilde{\alpha} понизилась на единицу: первый разряд стал нулевым, второй — первым и т.д., т.е. число \widetilde{\alpha} уменьшилось в m раз: \widetilde{\alpha}\!\!\not{\phantom{|}}\,m. Но поскольку самый младший (нулевой) разряд оказался фактически как бы "отрубленным", то в итоге получилось не частное \widetilde{\alpha}\!\!\not{\phantom{|}}\,m (оно могло бы оказаться дробным), а его целая часть: [\widetilde{\alpha}\!\!\not{\phantom{|}}\,m].


Итак, для функции \widetilde{\alpha}' мы получаем следующее описание с помощью оператора условного перехода:


\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_i, \widetilde{a}_j, \widetilde{\beta})= \begin{cases}\widetilde{\alpha},& \text{elsi}\quad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=0\quad \text{(net sdviga)},\\[2pt] m\widetilde{\alpha}+\varphi_a(\widetilde{q}_i, \widetilde{a}_j),& \text{esli}\quad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=1\quad \text{(sdvig vpravo)},\\[2pt] \widetilde{\alpha}\!\!\not{\phantom{|}}\,m,& \text{esli}\quad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=2\quad \text{(sdvig vlevo)}.\end{cases}

Совершенно аналогичная, но в определенном смысле двойственная картина наблюдается и для функции \widetilde{\beta}\colon при сдвиге вправо (влево) она ведет себя так же, как функция \widetilde{\alpha} при сдвиге влево (вправо). Так что для нее получаем следующее описание с помощью оператора условного перехода:


\widetilde{\beta}'(\widetilde{\alpha}, \widetilde{q}_{i}, \widetilde{a}_{j}, \widetilde{\beta})= \begin{cases}\widetilde{\beta},& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=0\quad \text{(net sdviga)},\\ \widetilde{\beta}\!\!\not{\phantom{|}}\,m,& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=1\quad \text{(sdvig vpravo)},\\ m\widetilde{\beta}+ \varphi_{a}(\widetilde{q}_{i}, \widetilde{a}_{j}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=2\quad \text{(sdvig vlevo)}. \end{cases}

Наконец, рассмотрим функцию \widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_{i}, \widetilde{a}_{j}, \widetilde{\beta}). Если сдвига не происходит, то ясно, что \widetilde{\alpha}'= \varphi_{a}(\widetilde{q}_{i}, \widetilde{a}_{j}). Если происходит сдвиг вправо, то машина приходит к обозрению самого левого разряда (напомним, что это есть младший разряд) — числа \widetilde{\beta}\colon именно он был отброшен при взятии для \widetilde{\beta}' целой части частного \widetilde{\beta} \!\!\not{\phantom{|}}\, m. Он как раз и представляет собой остаток от деления числа \widetilde{\beta} на m, т.е. в этом случае \widetilde{\alpha}'= r(m,\widetilde{\beta}). Если же происходит сдвиг влево, то двойственно получаем: \widetilde{\alpha}'= r(m, \widetilde{\alpha}). Итак, функция \widetilde{\alpha}' получает следующее описание:


\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_{i}, \widetilde{a}_{j}, \widetilde{\beta})= \begin{cases} \varphi_{a}(\widetilde{q}_{i}, \widetilde{a}_{j}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=0\quad \text{(net sdviga)},\\ r(m,\widetilde{\beta}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=1\quad \text{(sdvig vpravo)},\\ r(m, \widetilde{\alpha}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=2\quad \text{(sdvig vlevo)}. \end{cases}

Теперь сделаем выводы. В полученных выражениях для функций \widetilde{q}', \widetilde{\alpha}', \widetilde{\beta}, \widetilde{a}', а задействованы только примитивно рекурсивные функции, и указанные функции получены из этих примитивно рекурсивных функций с помощью оператора условного перехода, который, как мы знаем, сохраняет свойство примитивной рекурсивности, т.е. из примитивно рекурсивных функций создает снова примитивно рекурсивную функцию. Следовательно, все функции \widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}' примитивно рекурсивны.


Итак, мы доказали, что на каждом шаге любая машина Тьюринга осуществляет примитивно рекурсивное вычисление.


Четвертый этап. Рассмотрим теперь с точки зрения введенной арифметизации работу машины Тьюринга в целом.


Пусть задана начальная конфигурация K(0)= (\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0). Тогда конфигурация K(t), возникающая на такте t работы машины, зависит от величины t и компонент \widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0 начальной конфигурации, т.е. она является векторной функцией K(t)= \bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr), компоненты которой, в свою очередь, являются функциями, зависящими от переменных t, \widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0. Эти функции определяются следующим образом:


\begin{aligned}&K_{\alpha}(0,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)= \widetilde{\alpha}_{0};\\[2pt] &K_{\alpha}(t+1,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)=\\ &\qquad= \widetilde{\alpha} \bigl(K_{\alpha}(t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0), K_{q}(t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0), K_{a}(t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0), K_{\beta} (t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)\bigr);\\[2pt] &K_{q}(0)= \widetilde{q}_{0};\\[2pt] &K_{q}(t+1)= \widetilde{q}'\bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr);\\[2pt] &K_{a}(0)= \widetilde{a}_{0};\\[2pt] &K_{a}(t+1)= \widetilde{a}' \bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr);\\[2pt] &K_{\beta}(0)= \widetilde{\beta}_{0};\\[2pt] &K_{\beta}(t+1)= \widetilde{\beta}' \bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr). \end{aligned}

(В записях для функций K_{q},K_{a},K_{\beta} аргументы \widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0 для краткости опущены.)


Эти соотношения представляют собой схемы примитивной рекурсии, определяющие функции K_{\alpha},K_{q},K_{a},K_{\beta} с помощью функций \widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}'. При этом рекурсия ведется по переменной t. Примитивная рекурсивность функций \widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}' установлена на предыдущем шаге доказательства. Тогда отсюда очевидно следует, что и функции. K_{\alpha}, K_{q}, K_{a}, K_{\beta} также примитивно рекурсивны.


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


Здесь мы докажем утверждение, обратное тому, которое было доказано в предыдущем пункте: всякая функция, правильно вычислимая на машине Тьюринга, частично рекурсивна. Пусть \varphi — функция, правильно вычисляемая машиной Тьюринга. Такая машина, начав с конфигурации q_1a_0 \beta_0, останавливается в конфигурации вида q_za_z \beta_z, т.е. для такой машины K_{a}(0)=0,~ K_{q}(0)=1, исходное слово на ленте кодируется числом m \widetilde{\beta}_0+\widetilde{\alpha}_0, заключительное слово — числом m \widetilde{\beta}_z+\widetilde{\alpha}_z, т.е. вычисляется значение функции \varphi(m \widetilde{\beta}_0+\widetilde{\alpha}_0)= m \widetilde{\beta}_z+ \widetilde{\alpha}_z. Заключительное слово — это слово, написанное на ленте в тот момент t_z, когда машина впервые перешла в заключительное состояние q_z, т.е. в момент t_z= \mu t[K_{q}(t)=z]. Поэтому \widetilde{\beta}_z= K_{\beta}(t_z),~ \widetilde{\alpha}_z= K_{a}(t_z) и


\varphi(m \widetilde{\beta}_0+\widetilde{\alpha}_0)= m \widetilde{\beta}_z+ \widetilde{\alpha}_z= mK_{\beta}(t_z,0,1,\widetilde{\alpha}_0, \widetilde{\beta}_0)+ K_{a}(t_z,0,1, \widetilde{\alpha}_0, \widetilde{\beta}_0).

Учитывая, что \widetilde{\beta}_0= [x\!\!\not{\phantom{|}}\,m],~ \widetilde{\alpha}_0= r(m,x), выражение для результирующего значения \varphi(x) можно со всеми подробностями записать так:


\begin{aligned}\varphi(x)&= mK_{\beta} \bigl(\mu t[K_{q}(t,0,1, r(m,x), [x\!\!\not{\phantom{|}}\,m])=z], 0,1, r(m,x), [x\!\!\not{\phantom{|}}\,m]\bigr)+\\ &\quad+ K_{a} \bigl(\mu t[K_{q}(t,0,1, r(m,x), [x\!\!\not{\phantom{|}}\,m])=z], 0,1, r(m,x), [x\!\!\not{\phantom{|}}\,m]\bigr), \end{aligned}

где m,\,z — константы, зависящие от конкретной машины. Отсюда непосредственно видно, что функция \varphi(x), представляющая собой результат работы машины Тьюринга, построена из примитивно рекурсивных функций с помощью оператора минимизации \mu и, следовательно, является частично рекурсивной.


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


Соединив вместе следствие 33.20 и теорему 33.21, приходим к следующей теореме.


Теорема 33.22. Функция вычислима по Тьюрингу тогда и только тогда, когда она частично рекурсивна.


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2022 MathHelpPlanet.com. All rights reserved