Вычислимые функции, тезис Тьюринга-Черча и неразрешимые проблемы

Разбить на страницы

Показывать лекцию целиком

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

Напомним, что в теореме 8.1 мы уже показали, что каждая ч.р.ф. вычислима некоторой структурированной программой.

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

Теорема 10.1. Для всякой ч.р.ф. f существует м.Т. $$\mathcal{ M}_f$$, вычисляющая функцию f.

Доказательство. Доказательство проведем индукцией по определению частично рекурсивной функции f.

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

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

Суперпозиция. Пусть F^m и fⁿ₁,..., fⁿ_m - ч.р.ф., вычислимые на м.Т. $$\mathcal {M}_F, \mathcal { M}_{f_1}, \ldots, \mathcal {M}_{f_n}$$, соответственно. Пусть функция Gⁿ получена из них с помощью суперпозиции: Gⁿ=[F^m;fⁿ₁,..., fⁿ_m]. Тогда м.Т. $$\mathcal { M}_G$$, вычисляющая G, работает следующим образом:

m раз копирует вход $$|^{x_1}*\ldots *|^{x_n}$$, отделяя одну копию от другой символом # ;

на полученном слове вида $$|^{x_1}*\ldots *|^{x_n}\# \ldots \# |^{x_1}*\ldots *|^{x_n}$$

запускает параллельную композицию машин $$\mathcal { M}_{f_1}, \ldots, \mathcal {M}_{f_n}$$ и получает конфигурацию вида $$|^{ y_1}\# \ldots \# |^{y_n}$$, где $$y_{i}=f_{i}(x_{1},\dots ,x_{n}) (i \in [1,m])$$.

заменяет все символы 0023 на * ;

затем запускает программу м.Т. $$\mathcal {M}_F$$ на получившемся после этапа 3) входе вида $$|^{ y_1}* \ldots * |^{y_n}$$, и вычисляет требуемое значение $$G(x_1,\ldots,x_n)=F(y_1, \ldots, y_m)$$.

Если обозначить м.Т., выполняющую копирование на этапе (1), через Коп^m, а м.Т., выполняющую замену # на * на этапе (3), через Зам_*^#, то требуемую для суперпозиции м.Т. $$\mathcal { M}_G$$ можно представить как

$$\textit{Коп}^m; \mathbf{par}_{\#}( \mathcal { M}_{f_1}, \ldots , \mathcal {M}_{f_n}); \textit{Зам}_*^\#; \mathcal {M}_F$$

Примитивная рекурсия. Пусть функция Fⁿ⁺¹(x₁,... ,x_n,y) получена с помощью оператора примитивной рекурсии из функций gⁿ(x₁,..., x_n) и fⁿ⁺²(x₁,... ,x_n, y, z), которые вычислимы на м.Т. $$\mathcal{ M}_g$$ и $$\mathcal {M}_f$$. Определим вспомогательные м.Т.:

$$\mathcal{M}_1$$, используя $$\mathcal{ M}_g$$, строит по входу вида $$|^{x_1}*\ldots *|^{x_n}*|^y$$ конфигурацию на ленте $$|^y*|^{x_1}*\ldots*|^{x_n}*\wedge*|^{g(x_1,\ldots,x_n)};$$

$$\mathcal{ M}_2$$, используя $$\mathcal{M}_f$$, строит по входу вида $$|^y*|^{x_1}*\ldots*|^{x_n}*|^u*|^z$$ конфигурацию $$|^y*|^{x_1}*\ldots*|^{x_n}*|^{u+1}*|^{f(x_1,\ldots,x_n,u,z)};$$

$$\mathcal{M}_3$$ на входе вида $$|^y*|^{x_1}*\ldots*|^{x_n}*|^u*|^z$$ выдает в качестве результата $$|^z;$$

$$\Phi$$ на входе вида $$|^y*|^{x_1}*\ldots*|^{x_n}*|^u*|^z$$ проверяет условие $$y \ne u$$.

Построение каждой из указанных м.Т. достаточно очевидно. Из них можно получить, используя определенные в предыдущем разделе конструкции "языка программирования" для машин Тьюринга, требуемую м.Т. $$\mathcal {M}_F$$:

$$\mathcal {M}_1\/;\ \mathbf{ while\ }\Phi\ \mathbf{ do\ } \mathcal{ M}_2\ \mathbf{enddo};\ \mathcal {M}_3$$

Минимизация. Пусть $$f^{n}(x_{1},\dots , x_{n}) = \mu y [ g^{n+1}(x_{1},\dots , x_{n},y)=0]$$ и м.Т. $$\mathcal{M}_g$$ вычисляет функцию gⁿ⁺¹. Определим следующие вспомогательные м.Т.:

$$\mathcal {N}_1$$ приписывает аргумент 0 ко входу, т.е. вход вида $$|^{ x_1}*\ldots *|^{x_n}$$ переводит в конфигурацию на ленте $$|^{x_1}*\ldots*|^{x_n}*\wedge $$ (напомним, что при унарном кодировании 0 соответствует пустой символ).

$$\mathcal{N}_2$$ копирует свой вход с разделителем #, т.е. по любому входу w выдает w # w.

Через E обозначим м.Т., которая ничего не делает.

Пусть $$\mathcal{N}_3 = \mathbf{par}_{\#}(E, M_g)$$, т.е. вход вида $$|^{x_1}*\ldots*|^{x_n}* |^y\# |^{x_1}*\ldots*|^{x_n}* |^y$$ машина $$\mathcal{N}_3$$ перерабатывает, используя $$\mathcal{M}_g$$, в $$|^{x_1}*\ldots*|^{x_n}* |^y\# |^z$$, где z= g(x₁,... ,x_n, y)

$$\Phi$$ на входе вида w # v проверяет непустоту v (т.е. условие v > 0 ).

$$\Phi( w\#v)=\left \{ \aligned 0,\qquad \textit{если }v \neq \wedge\\ 1\qquad \textit{если }v= \wedge \endaligned \right .$$

Таким образом, при v=g(x₁,...,x_n,y) машина $$\Phi$$ проверяет условие $$g(x_{1},\dots ,x_{n},y) \ne 0$$.

$$\mathcal{N}_4$$ по входу вида $$|^{x_1}*\ldots*|^{x_n}* |^y\# w$$ стирает #w и прибавляет к y единицу, т.е. выдает результат: $$|^{x_1}*\ldots*|^{x_n}* |^{y+1}$$.

Наконец, $$\mathcal{N}_5 $$ по входу $$|^{x_1}*\ldots*|^{x_n}* |^y\# w$$ выдает |^y, стирая ненужные блоки символов.

Ясно, что каждая из перечисленных м.Т. $$\mathcal{N}_1$$, $$\mathcal{N}_2$$, $$\mathcal{N}_3$$, $$\mathcal{N}_4$$, $$\mathcal{N}_5$$ и $$\Phi$$ легко реализуема. Построим теперь с их помощью следующую м.Т. $$\mathcal{M}_f$$:

$$\mathcal{M}_f: \\ \mathcal{N}_1; \mathcal{N}_2; \mathcal{N}_3; \\ {\bf while\ } \Phi\ {\bf do\ } \mathcal{N}_4;\ \mathcal{N}_2;\ \mathcal{N}_3\ {\bf enddo};\\ \mathcal{N}_5.$$

Из этого определения непосредственно следует, что $$\mathcal{M}_f $$ вычисляет функцию fⁿ(x₁,..., x_n), заданную с помощью оператора минимизации.

Моделирование структурированных программ машинами Тьюринга

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

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

Доказательство Пусть структурированная программа $$\Pi$$ вычисляет арифметическую функцию f(x₁, ..., x_n). Не ограничивая общности, будем считать, что $$Var_{\Pi } =\{ x_{1}, \dots , x_{n}$$, x_n+1, ..., x_m } и что результирующей переменной является x₁. М.Т. $$M_{\Pi }$$, моделирующая $$\Pi,$$ будет иметь m -этажную ленту с алфавитом $$\Sigma =\{ \wedge , |, *\} \cup \{ \wedge , |\} ^{m}$$. Обозначим конфигурацию ленты M_\Pi, в которой на i -ом этаже, начиная с 1-ой ячейки, записано слева направо k_i символов '|' (i = 1, 2, ..., m), а далее идут "пустышки " $$\wedge,$$ как (k₁, k₂, ..., k_m). Тогда состоянию $$\sigma : Var_{\{ }\Pi \} \to N$$ программы $$\Pi$$ будет соответствовать конфигурация ленты $$M_{\Pi }$$: $$K_{\sigma } =(\sigma (x_{1}),\sigma (x_{2}),\dots , \sigma (x_{m}))$$.

$$M_{\Pi }$$ получается с помощью конструкций последовательной композиции, условного оператора и цикла из простых машин Тьюринга, реализующих элементарные присваивания и условия структурированных программ.

Команду x_i := 0 (i=1,... , m) программы $$\Pi$$ реализует м.Т. Mⁱ₀ , обнуляющая i -ый этаж M, т.е. переводящая любую конфигурацию (k₁,..., k_i-1,k_i, k_i+1 ..., k_m) в конфигурацию (k₁,..., k_i-1, 0, k_i+1, ... , k_m). Команду x_i := x_i +1 (i=1,... , m) программы $$\Pi$$ реализует м.Т. Mⁱ₊₁ , добавляющая один символ ' | ' справа на i -ом этаже, т.е. переводящая любую конфигурацию (k₁,..., k_i-1, k_i, k_i+1 ... , k_m) в конфигурацию (k₁,..., k_i-1, k_i+1, k_i+1, ... , k_m). Команду x_i := x_j (i, j=1,... , m) программы $$\Pi$$ реализует м.Т. M^ij, переписывающая содержимое j -го этажа на i -ый, т.е. переводящая любую конфигурацию (k₁,..., k_i, ..., k_j, ... , k_m) в конфигурацию (k₁,..., k_j, ... , k_j, ... , k_m).

Условие x_i = x_j реализуется машиной $$\Phi _{=}^{ij}$$, которая, работая на конфигурации (k₁, ..., k_i, ..., k_j, ... , k_m) выдает 0, если k_i=k_j, и 1 - в противном случае.

Условие x_i < x_j реализуется машиной $$\Phi _{<}^{ij}$$, которая, работая на конфигурации (k₁, ..., k_i, ..., k_j, ... , k_m) выдает 0, если k_i < k_j, и 1 - в противном случае.

Далее по индукции: пусть $$\Pi _{1}$$ и $$\Pi _{2}$$ - структурированные программы, для которых построены соответствующие машины Тьюринга $$M_{\Pi_1}$$ и $$M_{\Pi_2}$$, а $$\Phi$$ - некоторое условие, реализуемое м.Т. $$M_{\Phi }$$. Тогда программа $$\Pi = \Pi _{1} ; \Pi _{2}$$ реализуется машиной $$M_{\Pi}=M_{\Pi_1};M_{\Pi_2}$$ программа $$\Pi =$$ если $$\Phi$$ то $$\Pi _{1}$$ иначе $$\Pi _{2}$$ конец реализуется машиной $$M_{\Pi }= if M_{\Pi } then M_{\Pi 1} else M_{\Pi 2} endif$$, а программа $$\Pi =$$ пока $$\Phi$$ делай $$\Pi _{1}$$ все реализуется машиной $$M_{\Pi }=$$ while $$M^{\Pi}$$ do $$M_{\Pi 1}$$ enddo.

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

Утверждение 1. Пусть м.Т. $$M_{\Pi }$$ реализует в соответствии с приведенными определениями структурированную программу $$\Pi.$$ Тогда для любого состояния $$\sigma$$ программы $$\Pi$$ $$\Pi (\sigma ) = \sigma _{1}$$ тогда и только тогда, когда м.Т $$M_{\Pi }$$, начав работу в конфигурации $$K_{\sigma }$$ завершит ее в конфигурации $$K_{\sigma 1}$$.

Теперь для завершения доказательства теоремы достаточно взять в качестве результирующей следующую м.Т.: $$M = M_{start}; M_{\Pi }; M_{end}$$, где м.Т. M_start переводит одноэтажную начальную конфигурацию $$|^{x_1}*|^{x_2}*\ldots |^{x_n}$$ в m -этажную конфигурацию (x₁, x₂,..., x_n, 0,..., 0), а м.Т. M_end заключительную m -этажную конфигурацию (x₁, 0,..., 0) переводит в одноэтажную заключительную конфигурацию |^x1.

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

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

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

Доказательство этой теоремы - дополнительный материал, который можно при первом чтении опустить.

Доказательство Пусть м.Т. $$\mathcal{ M} = <Q, \Sigma, P,q_0, q_f> $$ вычисляет функцию f(x₁,..., x_n). Пусть также Q ={q₀,q₁,... ,q_k-1 }, q_f=q₁ и $$\Sigma = \{ a_{0}=\wedge , a_{1}, \dots , a_{ R-1}= | \}$$. Предположим также, не ограничивая общности, что $$\mathcal{ M} $$ никогда не пишет пустой символ $$\wedge$$ (как перестроить программу произвольной м.Т., чтобы она удовлетворяла этому условию ?).

Определим кодирование элементов конфигураций $$\mathcal{ M} $$ целыми числами. Пусть конфигурация $$\mathcal{ M} $$ имеет вид K=(w₁,q_i,a_j,w₂), где $$w_1=a_{i_m}a_{i_{m-1}} \ldots a_{i_0} $$ - слово на ленте левее головки, q_i - состояние м.Т., a_j - наблюдаемый в данной конфигурации символ и w₂= a_j0a_j1 ... a_jp} - слово на ленте правее головки. Кодом символа $$a_{j} \in \Sigma$$ будет число j, кодом состояния q_i - число i. Слова w₁ и w₂ будем рассматривать как числа в R -ичной системе счисления, читаемые в противоположных направлениях (из наших предположений следует, что $$i_{m} \ne 0$$ при m >0 и $$j_{p} \ne 0$$ при p>0 ) :

$$code_1(w_1) = \sum_{l=0}^{m} R^l i_l \ code_2(w_2) = \sum_{l=0}^{p} R^l j_l .$$

Например, если $$\Sigma = \{ \wedge , *, |\}$$, то для конфигурации K=(|**,q₃,|,* | |) имеем code₁(w₁)=3⁰ 1+3¹ 1+ 3² 2= [211]₃=22 и code₂(w₂)=3⁰ 1+ 3¹ 2 +3² 2= [221]₃=25. По программе P определим следующие табличные функции, кодирующие ее команды:

A(i,j) - код символа, который пишет $$\mathcal{ M}$$, когда она в состоянии q_i видит символ a_j;

Q(i,j) - код состояния, в которое переходит $$\mathcal{ M}$$, когда она в состоянии q_i видит символ a_j;

C(i,j) - код направления сдвига головки $$\mathcal{M}$$, когда она в состоянии q_i видит символ a_j (0 - на месте, 1 - вправо, 2 - влево).

Пусть при i >= k или j >= R эти функции принимают какое-нибудь фиксированное значение (например, 0). Тогда по лемме 18.1 все они примитивно рекурсивны.

Определим функции, которые по кодам компонент одной конфигурации K=(w₁,q_i,a_j,w₂) вычисляют коды компонент следующей конфигурации K^’=(w₁^’,q_m,a_p,w₂^’).

$$lf(code_1(w_1),i,j,code_2(w_2))= code_1(w_1^\prime); \\ rt(code_1(w_1),i,j,code_2(w_2))= code_2(w_2^\prime); \\ q(code_1(w_1),i,j,code_2(w_2))= m; \\ a(code_1(w_1),i,j,code_2(w_2))= p.$$

Покажем, что все эти функции примитивно рекурсивны. Для q это следует из того, что для любых i, j q(l,i,j,m)=Q(i,j). Определения остальных трех функций зависят от сдвига. При C(i,j)=0 имеем lf(l,i,j,r)=l, rt(l,i,j,r)= r, a(l,i,j,r)=A(i,j).

Если C(i,j)=2, то lf(l,i,j,r)=div(R, l), rt(l,i,j,r)= rR+A(i,j), a(l,i,j,r)=rm(R,l). Если же C(i,j)=1, то lf(l,i,j,r)=lR+A(i,j), rt(l,i,j,r)= div(R, r), a(l,i,j,r)=rm(R,r) Объединяя эти случаи получаем, что

$$lf(l,i,j,r)= eq(C(i,j),0)l+eq(C(i,j),2)div(R, l)+\\eq(C(i,j),1)(lR +A(i,j))$$

( здесь rm(x,y) - это функция, дающая остаток от деления y на x, а div(x,y) - функция целочисленного деления y на x ).

Аналогичные представления справедливы и для функций rt(l,i,j,r) и a(l,i,j,r). Следовательно, все эти функции примитивно рекурсивны.

Пусть из данной конфигурации K через t тактов получается конфигурация K^t. Определим коды компонент K^t как функции от компонент K и t :

$$A(l,i,j,r,0)=j, Q(l,i,j,r,0)=i, Lf(l,i,j,r,0)=l, Rt(l,i,j,r,0)=r, \\ A(l,i,j,r,t+1)=a(Lf(l,i,j,r,t),Q(l,i,j,r,t),A(l,i,j,r,t),\\Rt(l,i,j,r,t)), \\ Q(l,i,j,r,t+1)=q(Lf(l,i,j,r,t),Q(l,i,j,r,t),A(l,i,j,r,t),\\Rt(l,i,j,r,t)), \\ Lf(l,i,j,r,t+1)=lf(Lf(l,i,j,r,t),Q(l,i,j,r,t),A(l,i,j,r,t),\\Rt(l,i,j,r,t)), \\ Rt(l,i,j,r,t+1)=rt(Lf(l,i,j,r,t),Q(l,i,j,r,t),A(l,i,j,r,t),\\Rt(l,i,j,r,t)). \\$$

Это определение задает функции A⁽⁴⁾, Q⁽⁴⁾, Lf⁽⁴⁾, Rt⁽⁴⁾ с помощью совместной рекурсии. Следовательно, по лемме 18.5 они примитивно рекурсивны.

Пусть м.Т. $$\mathcal{ M} $$ вычисляет функцию f(x), (т.е. n=1 ). Тогда для начальной конфигурации $$K_{x}=K^{0}=(\wedge ,q_{0},|,|^{x-1})$$ code₁(w₁)=0, code(q₀)=0, code(|)=R-1, code₂( w₂ ) = (R-1)R^x-2+(R-1)R^x-3+ ... +(R-1)R⁰=R^x-1-1. Положим $$\bar Q(x,t)=Q(0,0,R-1,R^{x-1}-1, t) $$ и $$\bar{Rt}(x,t)=Q(0,0,R-1,R^{x-1}-1, t)$$. Тогда функция $$\tau(x)= \mu t(\bar Q(x,t)=1) $$ задает число шагов до перехода $$\mathcal{ M} $$ в заключительное состояние на входе x. Эта функция, очевидно, частично рекурсивна. Тогда функция $$\hat{Rt}(x)=\bar{Rt}(x,\tau(x)) $$ задает код правой части заключительной конфигурации, имеющий вид R^f(x)-1-1. Отсюда получаем, что

$$f(x)= 1 + \log_R(\hat{Rt}(x))+1)=\\1+\log_R(Rt(0,0,R-1,R^{x-1})+1),$$

и следовательно, функция f(x) частично рекурсивна.

Тезис Тьюринга-Черча и алгоритмически неразрешимые проблемы

Мы рассмотрели три математические модели для описания алгоритмов и вычисляемых ими функций, отражающие различные аспекты и представления о работе абстрактного вычислителя. Из теорем 8.1, 10.2 и 10.3 непосредственно получаем

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

Естественно, возникает вопрос о том, насколько общим является этот результат? Верно ли, что каждый алгоритм может быть задан одним из рассмотренных способов? На эти вопросы теория алгоритмов отвечает следующей гипотезой.

Тезис Тьюринга-Черча:

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

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

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

Чтобы показать связь теории алгоритмов с "практическим" программированием, рассмотрим некоторые алгоритмичские проблемы, связанные со структурированными программами.

Зафиксируем конечный алфавит A={a₀, a₁,..., a_m-1}, включающий все символы латинского алфавита, цифры, знак пробела (пусть это будет a₀ ), знаки ' ; ', ' = ', ' < ', ' := ' , а также знаки-ключевые слова если, то, конец, пока, делай и все. Тогда каждая структурированная программа $$\Pi$$ представляет собой некоторое слово $$w_{\Pi}=a_{i_1}a_{i_2}\ldots a_{i_k}$$ в алфавите A. Не ограничивая общности, будем считать, что это слово начинается не с пробела, т.е. i₁ >0. Тогда слово $$w_{\Pi }$$ однозначно определяет натуральное число $$n_{\Pi }$$, m -ичной записью которого оно является, т.е. $$n_{\Pi}=\sum_{j=1}^k i_j m^{k - j}$$. Назовем это число номером программы $$\Pi$$ . По тексту программы $$\Pi$$ ее номер $$n_{\Pi }$$ определяется однозначно. Рассмотрим теперь обратное соответствие. Конечно, не каждое число является номером некоторой структурированной программы. Поэтому сопоставим каждому числу $$n \in N$$ структурированную программу $$\Pi _{n}$$ следующим образом: если $$n=n_{\Pi }$$ для некоторой программы $$\Pi,$$ то $$\Pi _{n}=\Pi$$, иначе, т.е. когда n не является "естественным" номером никакой программы, сопоставим ему в качестве $$\Pi _{n}$$ некоторую никогда не останавливающуюся программу P (например, программу $$\Pi _{5}(1)$$: x₁ := x₁; пока x₁=x₁ делай x₁:=x₁ все из примера 7.5).

Проблема самоприменимости заключается в проверке для каждой программы $$\Pi$$ с входной переменной x и выходной переменной y того, остановится ли $$\Pi$$ на собственном номере $$n_{\Pi }$$, т.е в вычислении всюду определенной функции

$$F_s(x)=\left \{ \aligned 1,\qquad \textit{если } \Phi_{\Pi_x,y}(n_{\Pi_x}) < \infty\\ 0\qquad \textit{в противном случае}\endaligned \right .$$

Теорема 10.4. Проблема самоприменимости алгоритмически неразрешима, т.е. не существует структурированной программы, вычисляющей функцию F_s(x).

Доказательство от противного. Предположим, что существует программа P, вычисляющая функцию F_s(x). Без ограничения общности, можно считать, что ее выходная переменная есть y (почему?) и поэтому $$\Phi _{P,y}(x)=F_{s}(x)$$ для всех x. Пусть переменная z не входит в P. Рассмотрим следующую программу P’:

$$P; z:=0; \textbf{ если } z < y \textbf{ то } \Pi_5(1) \textbf{ иначе } y:= z \textbf{ конец}$$

Легко проверить, что если P на входе x выдает результат y=1, то P’ на этом входе не останавливается, а если P выдает результат y=0, то P’ останавливается ( и тоже выдает 0). Пусть n’=n_P’ - номер программы P’. Чему тогда равно значение $$\Phi _{P,y}(n’)$$? Если оно равно 1, то на входе x=n’ программа P’ не остановится, т.е. $$\Phi _{P’,y}(n’)= \infty$$, но тогда $$F_{s}(n’)=0 \ne \Phi _{P,y }(n’)$$. Если же $$\Phi _{P,y }(n')=0$$, то P’ на входе x=n’ останавливается с результатом 0, т.е. $$\Phi _{P’,y}(n') < \infty$$. Но тогда $$F_{s}(n’)=1 \ne \Phi _{P,y }(n')=0$$. Во всех случаях получили, что $$F_{s} \ne \Phi _{P,y }$$ и, следовательно, предположение о существовании программы для вычисления функции F_s неверно.

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

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

Проблема останова: по произвольной структурированной программе $$\Pi$$ определить завершится ли вычисление $$\Pi$$ на входе 0, т.е вычислить всюду определенную функцию

$$F_{h0}(n)=\left\{\begin{array}{ll} 1,\qquad \textit{если } \Phi_{\Pi_n,y}(0) < \infty\\ 0 \qquad \textit{в противном случае} \end{array} \right.$$

В более общем виде проблема останова состоит в вычислении следующей функции:

$$F_h(n,a)=\left\{\begin{array}{ll} 1,\qquad \textit{если } \Phi_{\Pi_n,y}(a) < \infty\\ 0 \qquad \textit{в противном случае} \end{array} \right.$$

Из этого определения следует, что программа $$\Pi _{n}$$ останавливается на входе a тогда и только тогда, когда F_h(n,a)=1.

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

$$F_t(n)= \left\{\begin{array}{ll} 1, \qquad \textit{если для всех } a\ \Phi_{\Pi_n,y}(a) < \infty\\ 0 \qquad \textit{в противном случае} \end{array} \right.$$

Проблема эквивалентности: по произвольным двум структурированным программам $$\Pi$$ и $$\Pi '$$ определить, эквивалентны ли они, т.е вычисляют ли они одну и ту же функцию:$$F_{eq}(n,m)= \left\{\begin{array}{ll} 1, \qquad \textit{если для всех } a\ \Phi_{\Pi_n,y}(a) =\Phi_{\Pi_m,y}(a)\\ 0 \qquad \textit{в противном случае} \end{array} \right.$$

Проблемы оптимизации текста программы. Одна из возможных оптимизаций (текста) программы состоит в удалении из нее операторов присваивания, которые никогда не работают, а другая - в замене условных операторов вида

$$\textbf{ если } \varphi \textbf{ то } \Pi_1 \textbf{ иначе } \Pi_2 \textbf{ конец},$$

на $$\Pi _{1}$$ в случае, когда условие $$\phi$$ истинно на любых входных данных, и - на $$\Pi _{2}$$, если оно на любом входе ложно. Определим соответствующие этим оптимизациям функции:

$$F_{opt1}(n,m)= \left\{\begin{array}{ll} 1, \qquad \textit{если существует вход } a, \textit{при работе на котором}\\ \qquad\textit{ в программе } \Pi_n \textit{срабатывает } m\textit{-ый по счету}\\ \qquad \textit{оператор присваивания}\\ 0 \qquad \textit{в противном случае} \end{array} \right.$$

Из этого определения следует, что при F_opt1(n,m)=0 программу $$\Pi _{n}$$ можно оптимизировать, удалив из нее m -ый оператор присваивания. Назовем задачу вычисления функции F_opt1(n,m) проблемой лишнего присваивания

$$F_{opt2}(n,m)= \left\{\begin{array}{ll} 1, \textit{если существует вход } a, \textit{ на котором при некотором}\\ \textit{срабатывании } m\textit{-го по счету условного оператора из}\\ \textit{программы } \Pi_n \textit{его условие истинно}\\ 0 \textit{в противном случае} \end{array} \right.$$

Ясно, что при F_opt2(n,m)=0 программу $$\Pi _{n}$$ можно оптимизировать, заменив ее m -ый условный оператор его второй альтернативой. Назовем задачу вычисления функции F_opt2 (n,m) проблемой лишнего условия

Заметим, что проблема самоприменимости и все проблемы, перечисленные в пп. 1-4 выше, связаны с вычислением функций, принимающих два значения 0 и 1. Эти функции являются характеристическими функциями соответствующих множеств. Например, F_h0(n) является характеристической функцией множества номеров программ, останавливающихся на входе 0. Напомним, что для множества $$A \subseteq N^{k}$$ его характеристическая функция c_A^k определяется следующим образом:

$$c_A^k(x_1,\ldots,x_k)= \left\{\begin{array}{ll} 1, \qquad \textit{если } (x_1,\ldots,x_k)\in A\\ 0 \qquad \textit{в противном случае} \end{array} \right.$$

На множества переносится понятия разрешимости и неразрешимости.

Определение 10.1. Множество $$A \subseteq N^{k}$$ назовем разрешимым (или рекурсивным ), если его характеристическая функция c_A^k вычислима, т.е. является общерекурсивной функцией, в противном случае, оно (и связанная с ним проблема) неразрешимо.

Используя это определение, теорему 10.4 можно переформулировать так:

Множество номеров программ, остановливающихся на собственном номере,

$$M_s=\{ n | \Phi_{\Pi_n}, y (n) < \infty\} неразрешимо.}$$

Обычно доказательства неразрешимости проблем используют метод сведения. Неформально его идею можно сформулировать следующим образом: "Если решение некоторой неразрешимой проблемы A можно эффективно получить, используя решение проблемы B, то тогда проблема B тоже неразрешима."

Определим отношение сводимости более формально. Напомним, что нумерационные функции позволяют вместо наборов (векторов, n -ок) целых чисел рассматривать их номера. Для множества $$B \subseteq N^{r}$$ обозначим через c_r(B) множество номеров входящих в B наборов: $$c_{r}(B)=\{ c_{r}(a_{1},\dots , a_{r}) | (a_{1},\dots , a_{r})\in B\}$$ (при r=1, разумеется, c₁(B)=B ).

Лемма 10.1. Множество (проблема) $$A \subseteq N^{k}$$ сводится к множеству (проблеме) $$B \subseteq N^{r}$$, если существует общерекурсивная функция f: N^k -> N такая, что $$(x_{1},\dots ,x_{k}) \in A \Leftrightarrow f (x_{1},\dots ,x_{k}) \in c_{r}(B)$$. В этом случае будем писать A <=_m B посредством f.

Содержательно, " A сводится к B посредством f " означает, что для выяснения, входит ли x в A, можно эффективно преобразовать x в такие входные данные y=f(x) проблемы B, что при $$y \in B$$ имеем $$x \in A$$, а если $$y \notin B$$, то и $$x \notin A$$.

Разрешимые множества сводятся к любым нетривиальным множествам.

Лемма 10.2. Если A разрешимо, а B не совпадает с $$\varnothing$$ и N, то A <=_m B.

Доказательство. По условию имеются такие b и d, что $$b \in B$$, а $$d \notin B$$. Положим f(x) = b , c_A(x) + d ,(1 - c_A(x)). Тогда при $$x \in A$$ имеем $$f(x) = b , 1 + d ,(1-1)= b \in B$$, а при $$x \notin A$$ - $$f(x) = b , 0 + d ,(1-0)= d \notin B$$. Таким образом, A <=_m B посредством f.

Как мы уже отмечали, доказательство неразрешимости можно основывать на следующем утверждении.

Лемма 10.3. Если A сводится к B и проблема A неразрешима, то и проблема B неразрешима.

Доказательство. Пусть A <=_m B посредством f. Тогда из определения сводимости следует, что для всех x имеет место равенство c_A(x)=c_B(f(x)). Поэтому, если бы B была разрешима, то ее характеристическая функция c_B была бы общерекурсивна и c_A также была бы общерекурсивна. Но это противоречит неразрешимости проблемы A.

Теорема 10.5. Все проблемы, перечисленные выше в пунктах 1-4, являются алгоритмически неразрешимыми.

Доказательство. Нам потребуются следующие вспомогательные программы $$\Pi _{x:=n}: x:=0; x:= x+1; \dots ; x:= x+1$$ ( присваиваие x:=x+1 повторяется n раз). Понятно, что для любого начального состояния $$\sigma$$ после выполнения $$\Pi _{x:=n}$$ имеем $$\Pi _{x:=n}(\sigma )(x)=n$$.

Докажем неразрешимость {проблемы останова:} по произвольной структурированной программе $$\Pi$$ определить, завершится ли вычисление $$\Pi$$ на входе 0. Пусть $$M_{h0}=\{ n | \Phi _{\Pi n,y }(0) < \infty \}$$. Докажем, что множество номеров самоприменимых программ M_s сводится к M_h0. Пусть n - номер программы $$\Pi _{n}$$. преобразуем ее в программу $$\Pi ': \Pi _{x:=n};\Pi _{n}; y:=0$$. Таким образом, $$\Pi '$$ вначале заносит в x номер n программы $$\Pi _{n}$$, а затем применяет $$\Pi _{n}$$ к этому номеру и, если $$\Pi _{n}$$ на n останавливается, выдает результат y=0. Поэтому $$\Pi '$$ останавливается на любом аргументе (в том числе и на 0) тогда и только тогда, когда $$n \in M_{s}$$. Преобразование программы $$\Pi _{n}$$ в программу $$\Pi '$$ осуществляется эффективно. Поэтому (на основании тезиса Тьюринга-Черча) существует такая о.р.ф. f, которая по n вычисляет номер m программы $$\Pi '=\Pi _{m}=\Pi _{f(n)}$$. Эта функция и будет сводить M_s к M_h0, так как $$n \in M_{s} \Leftrightarrow f(n) \in M_{h0}$$. Следовательно, по лемме ref{lm-red} проблемы останова M_h0 неразрешима.

Очевидно, что и более общая форма проблемы останова $$M_{h}=\{ (n,a) | \Phi _{\Pi n, y }(a) < \infty \}$$ также неразрешима, поскольку к ней сводится M_h0: $$n \in M_{h0} \Leftrightarrow (n,0) \in M_{h}$$.

Для сведения M_s к множеству M_t номеров программ, вычисляющих всюду определенные функции, можно также использовать функцию f из пункта 1. Действительно, $$\Pi _{n}$$ останавливается на входе n тогда и только тогда, когда $$\Pi '=\Pi _{f(n)}$$ останавливается на всех входах, т.е. $$n\in M_{s} \Leftrightarrow f(n) \in M_{t}$$. Следовательно, проблема тотальности M_t неразрешима.

Рассмотрим теперь проблему эквивалентности. Пусть

$$M_{eq}=\{(n,m) | \textit{ для всех } x \\ \Phi_{\Pi_n,y}(x) = \Phi_{\Pi_m,y}(x) \}.$$

Зафиксируем следующую программу P⁰: x:=x; y:=0. Очевидно, что она вычисляет функцию, тождественно равную нулю, т.е. $$\Phi_{P^0,y}(x)=0$$ для всякого x. Пусть ее номер n(P⁰) равен k₀. Для произвольного n рассмотрим пару (f(n), k₀). Из определения f следует, что $$\Pi _{n}$$ останавливается на входе n тогда и только тогда, когда $$\Pi '=\Pi _{f(n)}$$ останавливается на всех входах и выдает результат 0: $$\Phi_{\Pi_{f(n),y}}(x)=0$$ для всех x, т.е. $$\Pi _{ f(n)}$$ и $$\Pi_{k_0}$$ эквивалентны. Тогда $$n \in M_{s}\Leftrightarrow (f(n),k_{0}) \in M_{eq}$$. Положим g(n)= c₂(f(n),k₀) . Тогда g является о.р.ф. и $$n \in M_{s}\Leftrightarrow g(n) \in c_{2}(M_{eq})$$. Следовательно, M_s сводится к M_eq посредством g и проблема M_eq неразрешима.

Для доказательства неразрешимости проблемы лишнего присваивания:

$$M_{opt1}=\{(n,m) | \textit{на некотором входе } \ a\ \textit{ в программе } \ \Pi_n \textit{срабатывает }\\ m\textit{-ый по счету } \textit{оператор присваивания}\}$$

снова используем функцию f из пункта 1. Напомним, что $$\Pi _{f(n)}: \Pi _{\{ }x:=n\} ;\Pi _{n}; y:=0$$. По n и соответствующей программе $$\Pi _{n}$$ можно легко определить номер m последнего присваивания y:=0 в $$\Pi _{f(n)}$$:

$$m= (n+1) + (\textit{число присваиваний в } \Pi_n) +1$$

Пусть g(n) - это о.р.ф., вычисляющая по n этот номер m. Тогда $$n \in M_{s}\Leftrightarrow (f(n),g(n)) \in M_{opt1}$$. Положим h(n)= c₂(f(n),g(n)). Тогда h является о.р.ф. и $$n \in M_{s}\Leftrightarrow h(n) \in c_{2}(M_{opt1})$$. Следовательно, M_s сводится к M_opt1 посредством h и проблема M_opt1 неразрешима.

Рассмотрим теперь проблему лишнего условия:

$$M_{opt2}=\{(n,m) | \textit{существует вход\ }, a\\ \textit{ на котором при некотором срабатывании}\\\textit{ m-го по счету условного оператора}\\\textit{ в программе } \Pi_n\ \textit{его условие истинно}\}.$$

Для доказательства ее неразрешимости определим по n программу $$\Pi ’‘: \Pi ’; если y=0 то y:=y иначе y:=y +1 конец$$ ( здесь $$\Pi '$$ - программа из п. 1). И в этом случае программа $$\Pi ''$$ строится по программе $$\Pi _{n}$$ эффективно. Пусть ее номер вычисляется о.р.ф. f’, т.е. $$\Pi _{f’(n)}=\Pi ''$$, и пусть о.р.ф. g’(n) определяет номер последнего условного оператора в программе $$\Pi _{f’(n)}$$. Тогда $$n \in M_{s}\Leftrightarrow$$ в программе $$\Pi _{f'(n)}$$ последний условный оператор выполняется (на любом входе) и при этом y=0, т.е. его условие истинно, а это означает, что $$(f’(n),g'(n)) \in M_{opt2}$$. Положив h’(n)= c₂(f’(n),g’(n)), получим, что $$n \in M_{s} \Leftrightarrow h'(n) \in c_{2}(M_{opt2})$$. Следовательно, M_s сводится к M_opt2 посредством h’ и проблема M_opt2 также неразрешима.

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

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

Задачи

Задача 10.1. Докажите, что машины Тьюринга $$\mathcal{ M}_F $$ и $$\mathcal{M}_f$$, определенные в доказательстве теоремы 10.1 для примитивной рекурсии и минимизации, действительно правильно реализуют указанные операторы.

Задача 10.2. Постройте машины Тьюринга Mⁱ₀ , Mⁱ₊₁, M^ij, $$\Phi ^{ ij }_{=}$$, $$\Phi ^{ ij}_{<}$$, M_start и M_end, определенные в доказательстве теоремы 10.2.

Задача 10.3. Докажите утверждение 1, сформулированное в доказательстве теоремы 10.2, используя индукцию по построению программы $$\Pi$$ и соответствующей м.Т. $$M_{\Pi }$$.

Задача 10.4. В доказательстве теоремы 10.3 рассмотрен случай, когда м.Т. $$\mathcal{ M} $$ вычисляет функцию от одного аргумента f(x) . Покажите, что теорема верна и в общем случае для функций f(x₁,...,x_n) при любом n.

Задача 10.5. Докажите, что отношение алгоритмической сводимости <=_m является рефлексивным и транзитивным.

Задача 10.6. Доказать алгоритмическую неразрешимость следующих проблем.

По произвольной программе $$\Pi$$ определить, является ли вычисляемая ей функция $$\Phi _{\Pi ,y}(x)$$ постоянной константой.

По произвольной программе $$\Pi$$ и числам a и b проверить равенство $$\Phi _{\Pi ,y}(a)=b$$.

По произвольной программе $$\Pi$$ определить, является ли множество значений вычисляемой ею функции $$\Phi _{\Pi ,y}(x)$$ бесконечным.

По произвольной паре программ $$\Pi$$ и $$\Pi '$$ проверить, что для всех x имеет место неравенство $$\Phi _{\Pi ,y}(x) > \Phi _{\Pi ',y}(x)$$.

Задача 10.7. Докажите, что

пересечение двух разрешимых множеств является разрешимым множеством.

объединение двух разрешимых множеств является разрешимым множеством.

Задача 10.8. Докажите, что для двух разрешимых множеств A и B их "сумма" $$A+B=\{ x+y | x\in A, y\in B\}$$ также является разрешимым множеством.

Задача 10.9. Пусть A - разрешимое множество, а g(x) и h(x) являются о.р.ф. Докажите, что функция

$$F(x) = \left \{\begin{array}{ll} g(x), \mbox{ если } x \in A\\ h(x), \mbox{ в противном случае} \end{array} \right.$$

также является общерекурсивной.

Страницы: