К концу XIX - началу XX века в математике накопилось некоторое количество вычислительных задач, для которых ученые, несмотря на упорные попытки, не могли предложить методов решения. Одной из таких задач является задача о разрешимости диофантова уравнения. В докладе Д.Гильберта, прочитанном на II Международном конгрессе математиков в августе 1900 года, она звучит следующим образом:
"Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах".
Неудачные попытки математиков решить эту и другие подобные задачи привели к мысли о том, что метода их решения может и не существовать. Но, чтобы доказывать подобного рода утверждения, необходимо иметь математическое определение метода, то есть для интуитивных понятий разрешимости и вычислимости необходимо иметь их формальные эквиваленты. Одним из важнейших достижений математики XX века является формирование математических понятий, которые раскрывают сущность интуитивных представлений о том, что такое метод (алгоритм) решения той или иной задачи, что такое вычислимая функция.
Важность этих понятий вытекает не только из общенаучных проблем развития математики, но также из практических задач общества, использующего вычислительную технику в производстве, экономике, инженерных расчетах и нуждающегося в адекватном представлении о возможностях вычислительных автоматов. Приведем краткие исторические сведения о возникновении теории алгоритмов.
В 1932-1935 годах А.Черч и С.К.Клини ввели понятие $$\lm$$ -определимой функции, которое сыграло важную роль в определении объема интуитивного понятия вычислимой функции.
В 1934 году К.Гедель, на основе идей Дж.Эрбрана, рассмотрел класс функций, названных общерекурсивными, а в 1936 году А.Черч и С.К.Клини доказали, что этот класс совпадает с классом $$\lm$$ -определимых функций.
В 1936 году А.Тьюринг ввел свое понятие вычислимой функции, а в 1937 году доказал, что оно совпадает с понятием $$\lm$$ -определимой функции.
В 1943 году Э.Пост, основываясь на своей неопубликованной работе 1920-1922 годов, выдвинул еще один формальный эквивалент понятия вычислимой функции.
Еще одну формулировку дает теория алгоритмов Маркова (1951 г.).
Любое из упомянутых здесь уточнений интуитивного понятия вычислимой функции можно принять за математическое определение класса вычислимых функций. Основными доводами для этого являются эквивалентность различных формулировок и естественно-исторический опыт, показывающий, что все изучавшиеся до сих пор функции, которые принято считать вычислимыми, являются таковыми в смысле любого из упомянутых выше определений.
Еще один подход к моделированию вычислений развивается в рамках так называемого логического программирования. При таком подходе условия решаемой задачи и ее цель формулируются с помощью предложений формального логического языка. Затем осуществляется автоматический поиск доказательства цели, сопровождаемый вычислением неизвестных в задаче величин.
Заметим, что разрабатываемые в настоящее время алгоритмические языки, составляющие математическое обеспечение современных вычислительных устройств, также можно использовать для определения понятия вычислимости. Более того, можно проследить тесную связь между упомянутыми здесь теоретическими моделями вычислений и реальным программированием. Так, $$\lm$$ -исчисление Черча является прообразом функционального программирования, реализованного в известном программистам языке ЛИСП, разработанном в 1961 году Дж.Маккарти, а модель Поста содержит идеи, реализованные в операторных языках типа Фортран, Алгол. Методы логического программирования реализованы в настоящее время в нескольких версиях языка Пролог.
Однако реальные языки программирования из-за своей громоздкости и избыточности выразительных средств малопригодны для теоретического анализа понятия вычислимости. Отметим также модели вычислительных устройств, получившие название РАМ (Равнодоступная Адресная Машина) и РАСП (Равнодоступная Адресная Машина С хранимой Программой). Эти модели в большей степени, чем, например, модель Тьюринга, отражают структуру современных вычислительных устройств.
Описанная ниже модель несущественно отличается от модели, предложенной Тьюрингом.
Представление информации (модель памяти). Будем считать, что информация представляется словами, то есть конечными последовательностями, составленными из букв конечного алфавита, и записывается на неограниченной в обе стороны ленте, разделенной на ячейки. Слово записывается в идущих подряд ячейках по одной букве в ячейке.
В ячейку может быть ничего не записано, в этом случае говорим, что ячейка содержит пробел. Для обозначения пробела используем символ $$\ast$$. Конечную последовательность, составленную из символов алфавита $$A = \{a_1, a_2\dts a_t\}$$ и символа пробела, называем псевдословом. Считаем, что слева от первой буквы псевдослова и справа от последней записаны пробелы, кроме того, один из символов псевдослова будем помечать стрелкой. Множество всех конечных последовательностей символов из алфавита $$A$$ обозначается через $$A^\ast$$.
Если псевдослово имеет вид $$X\ast u_t\ast u_{t-1}\ast \ldots \ast u_{1}\ovs{\ast}{\downarrow}$$, где $$u_i \in A^\ast$$, $$X \in (A \cup \{\ast\})^\ast$$, то $$u_1$$ называем его первым словом, $$u_2$$ — вторым и т.д. Слова $$u_i$$ могут быть и пустыми. Пустые слова не занимают места на ленте. При необходимости будем считать, что между двумя идущими подряд пробелами записано пустое слово.
Поскольку на ленте в каждый момент времени будет находиться не более чем конечное число символов, отличных от пробела, постольку для любого $$n$$ в псевдослове будет определено его $$n$$ -е слово, возможно пустое.
Преобразователь информации. Преобразователь информации можно представить как некоторое устройство, снабженное головкой, обозревающей в каждый момент времени одну из ячеек ленты, которое по заранее намеченному плану (программе) может выполнять операции следующего вида:
Определение программы. Программу преобразования информации будем представлять в виде ориентированного графа, вершины которого помечены символами из множества $$A\cup \{\ast, r, l, s\}$$, а дуги — символами из множества $$A$$ так, что разным дугам, выходящим из одной вершины, приписаны разные символы. Одна вершина графа выделена в качестве входной, на рисунках будем отмечать ее входящей стрелкой. Предполагаем, что $$A \cap \{\ast, r, l, s\} = \varnothing$$.
Действие программы осуществляется следующим образом. В начальный момент
головка вычислительного устройства обозревает одну из ячеек ленты.
Просматривается
Вершину $$v$$, для которой найдется хотя бы одна буква из $$A$$, не используемая в качестве метки на дугах, выходящих из $$v$$, будем называть выходной. Выходные вершины будем помечать выходящими "в никуда" стрелками, помеченными буквами, не использованными на других дугах.
Согласно данному описанию, программу можно задать как набор:$$\eq*{ P = (Q, A, q_0, \varphi, \psi), }$$ в котором $$Q$$ — множество вершин графа; $$A$$ — алфавит символов, печатающихся на ленте; $$q_0$$ — входная вершина ( $$q_0 \in Q$$ ); $$\varphi$$ — отображение $$Q$$ в $$A \cup \{\ast, r, l, s\}$$ ; $$\psi$$ — частичное отображение $$A\x Q$$ в $$Q$$.
Чтобы не загромождать чертежи большим количеством стрелок и надписей при изображении программ, мы используем следующие соглашения. Если из вершины $$q$$ в вершину $$q'$$ ведет несколько дуг, будем заменять их одной дугой с надписанными над ней буквами, соответствующими заменяемым дугам; одну из дуг, выходящих из данной вершины, будем оставлять неподписанной, считая при этом, что она помечена всеми буквами алфавита $$A$$, которые не использованы на других дугах, выходящих из вершины $$q$$. Такая дуга может оказаться единственной, выходящей из вершины $$q$$. Ввиду большой близости введенного нами понятия программы с понятием машины Тьюринга будем называть наши программы тьюринговыми. Множество выходных вершин программы $$P$$ обозначим через $$V$$.
Пример. Пусть $$A = \{0, 1\}$$ и на ленте записано псевдослово $$\ast a_1 a_2 \ldots$$ $$a_k\ovs{\ast}{\downarrow}$$, где $$a_i \in A$$, $$i=1,2,\ldots,k$$, а стрелка над символом $$\ast$$ показывает положение головки в начальный момент. Рассматривая слово $$a_1 a_2\ldots a_k$$ как двоичную запись натурального числа $$n$$, требуется составить программу, которая на ленте оставляет псевдослово $$\ast b_1 b_2 \ldots$$ $$b_s\ovs{\ast}{\downarrow}$$, являющееся двоичной записью числа $$n + 1$$. Нетрудно увидеть, что поставленную задачу решает программа, представленная на рис. 11.1.
(рис 11.1) Здесь входная и выходная вершины помечены, соответственно, входящей и выходящей стрелками.
Для записи программ в виде формульных выражений введем обозначения для некоторых элементарных программ и операций, позволяющие строить из уже созданных программ более сложные.
Элементарными вычисляющими программами будем называть программы вида
Обозначать их будем, соответственно, символами $$r, l, s, a$$ где $$a \in A$$.
Программы, у которых множество выходов разбито на два непустых
подмножества: подмножество
Элементарными распознающими программами будем считать программы вида
Обозначать такую программу будем через $$\langle a\rangle$$.
Правила композиции. Введем несколько правил, которые позволят нам из уже построенных программ создавать более сложные.
Сокращения. Программы вида
$$\eq*{ T_1 \vee T_2 \vee \ldots \vee T_k }$$будем сокращенно записывать в виде
$$\eq*{ \bigcup_{i=1}^{k} T_{i}, }$$а программы вида
$$\eq*{ [T_1, T_2\ldots T_k] }$$в случае, когда $$T_1 = T_2 = \ldots = T_k = T$$ — в виде $$T^k$$.
В контексте со словами "если", "пока", "до" угловые скобки в записи элементарного распознающего оператора $$\langle a\rangle$$ будем опускать.
Приведем несколько программ, для которых введем обозначения, и в дальнейшем будем использовать их для построения более сложных программ. Они будут составлять начальное математическое обеспечение программирования.
В таблице приведены их схемы в предположении, что алфавит $$A$$ состоит из символов $$a_1, a_2\ldots a_t$$ ; а символ $$\ast$$ обозначен через $$a_0$$.
Кроме того, считаем, что $$X$$ и $$Y$$ — произвольные псевдослова над алфавитом $$A$$ ; $$u_1, u_2\dts u_n$$, $$u$$ — слова в алфавите $$A$$ ; $$a$$ — произвольный символ из $$A \cup \{*\}$$ ; $$u^1$$ — слово, полученное из слова $$u$$ путем изменения порядка символов на противоположный; $$n = 1, 2, \ldots$$.
Программы $$R$$ и $$L$$, описанные в начале таблицы, используются в последующих программах.
Сдвиг головки влево до ближайшего пробела.Обозначение $$L$$
| Вход | $$X\ast u \ovs{a}{\downarrow}\,Y$$ |
| Выход | $$X \ovs{\ast}{\downarrow} ua\, Y$$ |
| Программа | $$l\ (\t{до}\ \ast)$$ |
Сдвиг головки вправо до ближайшего пробела.Обозначение $$R$$
| Вход | $$X \ovs{a}{\downarrow} u \ast\, Y$$ |
| Выход | $$X a u \ovs{\ast}{\downarrow} \, Y$$ |
| Программа | $$r\ (\t{до}\ \ast)$$ |
Копирование $$n$$ -го слова.Обозначение $$K_n$$
| Вход | $$X \ast u_n \ast u_{n-1} \ldots \ast u_{1}\ovs{\ast}{\downarrow}$$ |
| Выход | $$X \ast u_n \ast u_{n-1} \ldots \ast u_1 \ast u_{n}\ovs{\ast}{\downarrow}$$ |
| Программа | $$L^n,\ r,[\cup_i\ (\t{если}\ a_i) [\ast,\ R^{n+1},\ a_i,\ L^{n+1}, a_i, r]]\ (\t{до}\ \ast),\ R^n$$ |
Удаление буквы со сдвигом. Обозначение $$S$$
| Вход | $$X \ovs{a}{\downarrow} u \ast Y$$ |
| Выход | $$X u \ast \ovs{\ast}{\downarrow} Y$$ |
| Программа | $$[r, \cup_i\ (\t{если}\ a_i) [l,\ a_i],\ r]\ (\t{до}\ \ast)$$ |
Циклический сдвиг $$n$$ слов. Обозначение $$Z_n$$
| Вход | $$X \ast u_n \ast u_{{n}-1}\ast \ldots \ast u_{1} \ovs{\ast}{\downarrow}$$ |
| Выход | $$X \ast u_{n-1} \ast \ldots \ast u_1 \ast u_{n}\ovs{\ast}{\downarrow}$$ |
| Программа | $$R,\ [L^{n+1},\ r, \cup_i\ (\t{если}\ a_i)[S^n, a_i]](\t{до}\ \ast)$$ |
Удаление $$n$$ -го слова. Обозначение $$\Lambda_n$$
| Вход | $$X \ast u_n \ast u_{{n}-1}\ast \ldots \ast u_{1}\ovs{\ast}{\downarrow}$$ |
| Выход | $$X \ast u_{n-1} \ast \ldots \ast u_1 \ovs{\ast}{\downarrow}$$ |
| Программа | $$Z_n,\ [\ast, l]\ (\t{до}\ \ast)$$ |
Рассматриваемая методика предназначена для доказательства правильности алгоритмов, представленных в виде графов, вершинам которых поставлены в соответствие операторы над памятью, а дугам — переходы от оператора к оператору. Одну из вершин назовем входной, ей соответствует оператор, с которого начинается выполнение алгоритма, а выходных вершин может быть несколько. Считаем, что входная и выходная вершины помечены, соответственно, входящей и выходящей стрелками. Такие представления алгоритмов называют блок-схемами. Доказать правильность алгоритма — это значит доказать следующее утверждение:
На практике такое утверждение часто разбивают на два.
Алгоритм, для которого доказано утверждение 1, называется частично правильным или частично корректным. Если же доказаны утверждения 1 и 2, то алгоритм называется правильным или корректным.
Заметим, что когда доказательство утверждения 2 представляет
непреодолимые трудности, то ограничиваются доказательством
утверждения 1. Таковы, например,
Остановимся на доказательстве
Если все индуктивные шаги доказаны, то, используя принцип математической
индукции, можно утверждать частичную корректность алгоритма. Для
доказательства
Упорядоченный набор из $$n$$ слов в алфавите $$A$$ называется $$n$$ -местным набором над $$A$$. Множество всех $$n$$ -местных наборов над $$A$$ обозначим через $$(A^\ast)^n$$. Любое подмножество $$R$$ множества $$(A^\ast)^n$$ называется $$n$$ -местным словарным отношением.
Любое, возможно частичное, отображение $$f: (A^\ast)^n \to A^\ast$$ называется $$n$$ -местной словарной функцией. Область определения функции $$f$$ обозначается через $${\rm Def}(f)$$.
Результатом работы программы $$T$$ на входном псевдослове $$x$$ называется псевдослово $$T(x)$$, которое появляется на ленте в момент остановки программы; если программа работает бесконечно, то результат не определен.
Программу, которая в процессе работы над любым псевдословом $$x$$ не сдвигает головку левее пробела, расположенного слева от $$n$$ -го слова псевдослова $$x$$, будем называть $$n$$ -программой.
Словарное $$n$$ -
Словарное $$n$$ -
Словарная $$n$$ -местная функция $$f:(A^\ast)^n \to
A^\ast$$ называется
Вычислимые по Тьюрингу функции уместно было бы назвать полувычислимыми, а полувычислимые с разрешимой областью определения — вычислимыми, но это противоречит установившимся традициям.
Чтобы вычислять значения числовых функций с помощью тьюринговых программ, необходимо выбрать способ кодирования на ленте аргументов и значений функции. Мы рассматриваем функции из $$N^n$$ в $$N$$, где $$N$$ — множество натуральных чисел, включая $$0$$, а $$n \ge 1$$.
Значения функции и ее аргументов будем записывать в бинарном, унарном или каком-либо ином коде, для чего нам потребуется, соответственно, алфавит $$A = \{1\}$$, $$A = \{0, 1\}$$ и т.д. Значения аргументов перед вычислением должны быть представлены на ленте в виде псевдослова$$\eq*{ \ast x_n \ast x_{n-1}\ast \ldots \ast x_1 \ovs{\ast}{\downarrow}, }$$ где $$x_i$$ — код $$i$$ -го аргумента $$(i = 1, 2\dts n)$$.
После вычисления содержимое ленты должно иметь вид$$\eq*{ \ast x_n \ast x_{n-1}\ast \ldots \ast x_1 \ast y \ovs{\ast}{\downarrow}, }$$ где $$y$$ — код значения функции при заданных значениях аргумента.
Упражнения
Пытаясь выяснить содержание интуитивного понятия вычислимой функции, А.Черч в 1936 году рассмотрел класс так называемых рекурсивных функций, а Клини расширил его до класса частично-рекурсивных функций. В то же время впервые была высказана естественно-научная гипотеза о том, что интуитивное понятие вычислимой частичной функции совпадает с понятием частично рекурсивной функции. Эту гипотезу называют тезисом Черча. Здесь мы напомним понятие частично-рекурсивной функции и покажем, что любая частично-рекурсивная функция вычислима по Тьюрингу. Набор аргументов $$x_1, x_2\dts x_m$$ обозначим через $${\bs x}$$.
Функция $$f({\bs x})$$ называется
Говорят, что $$(n + 1)$$ -местная функция $$f({\bs x},y)$$
получена
Говорят, что $$n$$ -местная функция $$f({\bs x})$$
получена
Часто обозначают $$f({\bs x})$$ через $$\mu y(g(y, {\bs x}) = 0)$$.
Заметим, что суперпозиция и примитивная рекурсия, примененные к всюду определенным функциям, дают всюду определенные функции, тогда как минимизация, примененная к всюду определенной функции, может дать частичную функцию.
Числовая функция $$f\colon N^n \to N$$ называется частично рекурсивной, если она является одной из базисных функций:
а) $$O(y) = 0$$ (при всех $$y \in N$$ ),
б) $$S(y) = y + 1$$ (при всех $$y \in N$$ ),
в) $$I_m^n (x_1, x_2\dts x_n) = x_m(n = 1, 2,\ldots;\ 1 \le m \le n)$$
или получена из них с помощью конечного числа применений суперпозиции,
Теорема. Любая частично-рекурсивная функция вычислима по Тьюрингу.
Доказательство теоремы заключено в следующих четырех леммах, с
использованием
Лемма 1 (о базисных функциях). Базисные функции $$O(y)$$, $$S(y)$$, $$I_m^n(x_1, x_2 \dts x_n)$$ вычислимы по Тьюрингу.
Действительно, функцию $$S(y)$$ вычисляет программа $$[K_m, 1, r]$$, функцию $$O(y)$$ — программа $$[r]$$, функцию $$I_m^n(x_1, x_2\dts x_n)$$ — программа $$K_m$$.
Лемма 2 (о суперпозиции). Если функции $$g_1 ({\bs x}), g_2 ({\bs x})\dts$$ $$g_m({\bs x})$$ и $$h(y_1, y_2\dts y_m)$$ вычислимы, соответственно, программами $$G_1, G_2,\ldots$$, $$G_m$$ и $$H$$, то функцию
$$\eq*{ f({\bs x})=h(g_1({\bs x}), g_2 ({\bs x})\dts g_m ({\bs x})) }$$вычисляет программа:
$$\eq*{ [G_m, (Z_{n + 1})^n, G_{{m}-1}, (Z_{n + 1})^n\dts G_1, (Z_{n + 1})^n, (Z_{n + m})^{n}, H, (\Lambda_2)^m]. }$$Доказательство. Чтобы убедиться в справедливости этого утверждения, достаточно выписать псевдослова, которые появляются на ленте после выполнения отдельных частей программы. Сначала на ленте находится псевдослово
$$\eq*{ \ast x_n \ast x_{{n}-1} \ast \ldots \ast x_1 \ovs{\ast}{\downarrow}, }$$после выполнения $$G_m$$ на ленте будет
$$\eq*{ \ast x_n \ast x_{{n}-1} \ast \ldots \ast x_1 \ast g_m \ovs{\ast}{\downarrow}, }$$после $$[G_m, (Z_{n + 1})^n]$$ —$$\eq*{ \ast g_m\ast x_n \ast x_{{n}-1} \ast \ldots \ast x_1 \ovs{\ast}{\downarrow}, }$$
после $$[G_m, (Z_{n + 1})^n, G_{{m}-1}]$$ —$$\eq*{ \ast g_m \ast x_n \ast x_{n-1} \ast \ldots \ast x_1 \ast g_{m-1}\ovs{\ast}{\downarrow}, }$$
и т.д.
После $$[G_m, (Z_{n + 1})^n, G_{{m}-1}, (Z_{n + 1})^n\dts G_1, (Z_{n + 1})^n]$$ —$$\eq*{ \ast g_m \ast g_{{m}-1} \ast \ldots \ast g_1 \ast x_n \ast x_{{n}-1}\ast \ldots \ast x_1 \ovs{\ast}{\downarrow}, }$$ после $$[G_m, (Z_{n + 1})^n, G_{m-1}, (Z_{n+1})^n \dts G_1, (Z_{n+1})^n, (Z_{n+m})^n, H]$$ —$$\eq*{ \ast x_n \ast x_{n-1}\ast \ldots \ast x_1 \ast g_m \ast g_{m-1} \ast \ldots \ast g_1 \ast f \ovs{\ast}{\downarrow}, }$$
и, наконец, после выполнения всей программы получим
$$\eq*{ \ast x_n \ast x_{n-1}\ast \ldots \ast x_1 \ast f \ovs{\ast}{\downarrow}. }$$Лемма 3 (о примитивной рекурсии).
Если функции $$h$$ $$(x_1$$, $$x_2 \dts x_n)$$ и $$g (y_1, y_2\dts y_{n+2})$$ вычислимы соответственно
программами $$H$$ и $$G$$, то функция $$f(x_1, x_2\dts x_n, y)$$,
полученная по схеме
Доказательство. Представим программу, предлагаемую для вычисления функции $$f(x_1, x_2\dts x_n, y)$$, блок-схемой, изображенной на рисунке.
Пунктирными стрелками показаны контрольные дуги, для которых будут сформированы соответствующие индуктивные утверждения $$P_1, P_2, P_3$$.
Утверждение $$P_1$$ соответствует входной дуге и поэтому должно описывать содержимое ленты в начальный момент. Утверждение $$P_3$$ соответствует выходной дуге и должно описывать содержимое ленты в момент завершения работы программы. Утверждение $$P_2$$ относится к дуге, разрезающей единственный имеющейся в блок-схеме цикл, поэтому должно быть сформулировано так, чтобы ему удовлетворяло содержимое ленты каждый раз, когда в программе реализуется переход по рассматриваемой дуге.
Напомним, что основное требование, предъявляемое к утверждениям $$P_1, P_2, P_3$$, заключается в том, чтобы была возможность доказательства индуктивных шагов:$$\eqa*{ P_1 \to P_2,\ \t{если реализуется путь}\ [H; L^{n+1}; l; \ast; R^{n+2}; G];\\ P_1 \to P_3,\ \t{если реализуется путь}\ [H; L_{n+1}; l; R^{n+2}];\\ P_2 \to P_2,\ \t{если реализуется путь}\ [\Lambda_2; L^{n+2}; 1; l; \ast; R^{n+2}; G];\\ P_2 \to P_3,\ \t{если реализуется путь}\ [\Lambda_2; L_{n+2}; 1; l; R_{n+2}]. }$$
Пусть $$x_1, x_2\dts x_n$$, $$y$$ — исходные значения аргументов из множества $$N$$, тогда требуемые утверждения можно сформулировать следующим образом:
P_1 — содержимое ленты равно
$$\eq*{ \ast 1^{y}\ast 1^{x_{n}} \ast 1^{x_{n-1}} \ast \ldots \ast 1^{x_{1}} \ovs{\ast}{\downarrow}, }$$$$P_2$$ — существует $$y_1 \ge 1, y_2, g_1, g_2 \ge 0$$ такие, что содержимое ленты равно
$$\begin{gather*} \ast 1^{y_{2}} \ast 1^{y_{2}} \ast 1^{x_{n}} \ast 1^{x_{n-1}} \ast \ldots \ast 1^{x_{1}} \, 1^{g_{1}} \, 1^{g_{2}}\ \t{и}\\ y_1 + y_2 + 1 = y,\\ g_1 = g(f(x_1, x_2\dts x_n, y_1 - 1), x_1, x_2 \dts x_n, y_1 - 1),\\ g_2 = g(f(x_1, x_2\dts x_n, y_1), x_1, x_2\dts x_n, y_1), \end{gather*} $$
$$P_3$$ — содержимое ленты равно
$$\eq*{ \ast 1^{y} \ast 1^{x_{n}} \ast 1^{x_{n-1}} \ast \ldots \ast 1^{x_{1}} \ast 1^{z} \ovs{\ast}{\downarrow}\ \t{и}\ z = f(x_1, x_2\dts x_n, y). }$$Доказательство индуктивных шагов легко получить, выписывая содержимое ленты после каждого оператора в соответствующем пути. Читателю предоставляется возможность проделать это самостоятельно и убедиться в правильности программы, предлагаемой в формулировке леммы 3. Не забудьте доказать завершаемость исследуемой программы.
Лемма 4 (о минимизации). Если функция $$g(y, x_1, x_2\dts x_n)$$ вычислима программой $$G$$, то функция $$f(x_1, x_2\dts x_n)$$, полученная из нее по схеме минимизации, вычисляется программой$$\eq*{ [r, G, l, (\t{пока}\ 1)[r, \Lambda_1, 1, r, G, l]. }$$
Доказательство. Представим программу, предлагаемую для вычисления функции $$f(x_1, x_2\dts x_n)$$, блок-схемой c указанными контрольными точками $$P_1$$, $$P_2$$, $$P_3$$.
Пусть $$x_1, x_2\dts x_n$$ — исходные значения
аргументов, тогда для доказательства
$$P_1$$ — содержимое ленты равно$$\eq*{ \ast 1^{x_{n}} \ast 1^{x_{n-1}} \ast \ldots \ast 1^{x_{1}} \ovs{\ast}{\downarrow}, }$$
$$P_2$$ — существуют $$k, z \ge 0$$, такие, что содержимое ленты равно$$\eq*{ \ast 1^{x_{n}} \ast 1^{x_{n-1}} \ast \ldots \ast 1^{x_{1}} \ast 1^{k} \ast 1^{z} \ovs{\ast}{\downarrow},\ \t{где}\ z = g (k, x_1, x_2\dts x_n), }$$
$$P_3$$ — содержимое ленты равно$$\eq*{ \ast 1^{x_{n}} \ast 1^{x_{n-1}} \ast \ldots \ast 1^{x_{1}} \ast 1^{z} \ovs{\ast}{\downarrow},\ \t{где}\ z = f(x_1, x_2\dts x_n). }$$ Требуется доказать следующие индуктивные шаги.$$\eqa*{ P_1 \to P_2,\ \t{если реализуется путь}\ [r, G];\\ P_2 \to P_2,\ \t{если реализуется путь}\ [l; r; \Lambda_1; 1; r; G];\\ P_2 \to P_3,\ \t{если реализуется путь}\ [l],\ \t{и головка остановится на}\\ \qq \t{символе}\ \ast. }$$
Доказательство индуктивных утверждений и завершаемости программы мы оставляем читателю в качестве упражнений.
Заметим, что в доказательствах лемм 3 и 4 при рисовании блок-схемы мы несущественно отступили от текстов программ, данных в их формулировках, а при доказательстве леммы 2 не выписывали индуктивных утверждений, так как в представлении программы блок-схемой нет циклов. Обращаем внимание на то, что правильность блоков, из которых составлены программы, мы не подвергаем сомнению.
В этом параграфе речь пойдет об универсальной тьюринговой программе $$U$$, которая может имитировать любую программу, работающую над фиксированным алфавитом $$A = \{a_1, a_2 \dts a_n\}$$. Эта программа $$U$$, получив на входе псевдослово, содержащее в определенном виде код произвольной программы $$T$$ и псевдослово $$X$$, должна оставить на ленте код программы $$T$$ и псевдослово $$T(X)$$ — результат работы программы $$T$$ на псевдослове $$X$$.
Читатель, построивший универсальную программу, может считать себя изобретателем компьютера.
Пусть $$\Psi_n$$ — множество всех функций из $$N$$ в $$N$$ таких, что каждая из них определена в точке 0 и вычислима программой, состоящей не более чем из $$n$$ тьюринговых команд. Рассмотрим функцию $$s(n) = \max f(0)$$, где максимум берется по всем функциям из $$\Psi_n$$. Очевидно, $$s(n)$$ всюду определена и монотонна. Более того, справедлива
Теорема. Для любой всюду определенной вычислимой функции $${f\colon N {\to} N}$$ существует $$k \in N$$ такое, что при любом $$m \ge k$$ выполняется неравенство $$f(m) < s(m)$$.
Действительно, пусть $$f(n)$$ — произвольная всюду определенная функция из $$N$$ в $$N$$, тогда очевидно, что функция$$\eq*{ F(n) = \max(f(3n), f(3n + 1), f(3n+ 2)) + 1 }$$ будет также всюду определенной и вычислимой. Пусть в унарном коде ее вычисляет программа $$T_F$$, состоящая из $$k$$ команд. Рассмотрим программу $$T = [[1, r]^n, T_F]$$, которая сначала записывает на ленте число $$n$$, а затем работает как $$T_F$$. Очевидно, что она состоит из $$2n + k$$ команд и вычисляет некоторую функцию $$F\in \Psi_{2n+k}$$.
По определению $$F'$$ и $$s$$ имеем $$F(n) = F'((0) \le s(2n + k)$$. Используя монотонность функции $$s$$, получим $$F(n) \le s(3n)$$ при всех $$n \ge k$$, следовательно, $$f(3n+i) < s(3n+i)$$, $$(i = 0, 1, 2)$$. Отсюда следует, что при $$m \ge 3k$$ выполняется неравенство $$f(m) < s(m)$$, что и требовалось доказать.
Следствие. Функция $$s(n)$$ невычислима, так как она растет быстрее, чем любая вычислимая функция.
Заметим, что при любом фиксированном $$n$$ значение $$s(n)$$ можно попытаться вычислить путем перебора всех программ длины $$\le n$$ и определения для каждой из них времени работы до момента остановки или доказательства ее незавершаемости. Но вопрос о завершаемости программ в общем виде алгоритмически неразрешим. Уточним основные моменты этого утверждения.
Пусть $$T$$ — тьюрингова программа, работающая в алфавите $$A$$, и пусть $${\rm kod}(T)$$ — слово в алфавите $$A$$, кодирующее программу $$T$$ (на деталях кодирования не останавливаемся).
Программа $$T$$ называется самоприменимой, если при подаче ей на вход ее собственного кода она через конечное число шагов остановится, в противном случае программа называется несамоприменимой. Пусть $$M$$ — множество кодов самоприменимых программ.
Теорема. Множество $$M$$ алгоритмически неразрешимо.
Доказательство. Пусть $$M$$ — алгоритмически разрешимо. Тогда существуют две программы $$T_1$$ и $$T_2$$ такие, что $$T_1$$ останавливается только на словах из $$M$$, а $$T_2$$ — только на словах из $$A^\ast \backslash M$$.
Тогда, если $$T_2$$ на собственном коде остановится, то $${\rm kod}(T_2) \in M$$ по определению $$M$$, но $${\rm kod}(T_2) \not \in M$$ по определению $$T_2$$.
Если же $$T_2$$ на своем коде не остановится, то по определению $$M$$ $${\rm kod}(T_2)\not\in M$$, а по определению $$T_2$$ $${\rm kod}(T_2) \in M$$. Итак, в любом случае имеем противоречие.
Еще одним примером алгоритмически неразрешимого множества является множество $$M_1$$ кодов программ, которые останавливаются при пустом входе. Легко показать, что если бы $$M_1$$ было разрешимым, то множество $$M$$ тоже было бы разрешимым.
При практическом решении многих интересных задач с помощью вычислительных автоматов существенную роль играет время работы и объем памяти, которые требуются для их решения соответствующими алгоритмами. Упомянутые характеристики называются, соответственно, временной и пространственной сложностью алгоритма.
Временной и пространственной сложностью задачи в классе алгоритмов (или автоматов) называется время и объем памяти, необходимые "лучшему" в данном классе алгоритму (автомату) для решения рассматриваемой задачи.
Вопрос о нахождении сложностных характеристик задач весьма труден. Трудности, как правило, связаны с логической сложностью рассматриваемых задач и обилием алгоритмов в любом универсальном классе.
Рассмотрим некоторые подробности на примере тьюринговых программ. Будем считать, что задача представлена двухместным словарным предикатом $$R(u, v)$$ над некоторым алфавитом $$A$$ и заключается в нахождении по заданному слову $$u \in A^\ast$$ слова $$v \in A^\ast$$ такого, что $$R(u, v)$$ истинно.
Слово $$v$$ будем считать решением задачи $$R$$ при входном слове $$u$$. Чтобы пустоту слова $$v$$ трактовать как отсутствие решения, наложим на $$R$$ следующие ограничения:
$$\begin{gather*} R(\lm, \lm),\\ \forall u\, \exists v\, R(u,v)\\ \forall u[R (u,\lm) \to \forall v[v \ne \lm \to \neg R (u, v)]]. \end{gather*}$$
Результат работы тьюринговой программы $$T$$ на входном слове $$u$$ обозначим $$T(u)$$, считая $$T(u)$$ равным выходному слову.
Будем говорить, что тьюрингова программа $$T$$ решает задачу $$R$$, если на любом входном слове $$u$$ она останавливается через конечное число шагов и $$\forall u\, R(u, T(u))$$.
Через $${\rm time}(T, u)$$ обозначим число элементарных тьюринговых команд, которые будут выполнены программой $$T$$ от начального момента до момента остановки при работе на входном слове $$u$$. Если при входном слове $$u$$ программа $$T$$ выполняет бесконечное число шагов, то считаем $${\rm time}(T, u) = \fy$$.
Величину $${\rm time}(T, u)$$ будем называть временем работы программы $$T$$ на слове $$u$$. В большинстве случаев эта величина существенно зависит от длины слова $$u$$, поэтому представляет интерес функция $$t(T, n) = \max {\rm time}(T, u)$$, где максимум вычисляется по всем словам длины $$n$$.
Заметим, что эта ситуация не является общей; в некоторых случаях величина $${\rm time}(T, u)$$ не зависит от длины слова $$u$$. Например, пусть требуется определить четность числа, представленного в двоичном коде. Для этого достаточно посмотреть на его младший разряд.
Важным и интересным для практики является вопрос о верхних и нижних оценочных функциях для времени работы конкретных алгоритмов.
Заметим, что получение нижних нетривиальных оценок каждый раз представляет собой сложную математическую задачу. Известно, например, что временная сложность задачи распознавания симметрии слова тьюринговыми программами оценивается снизу функцией $$cn^2$$, где $$n$$ — длина слова, а $$c$$ — некоторая константа.
Для многих интересных с практической точки зрения задач известные верхние оценки носят экспоненциальный характер, что часто свидетельствует о больших затратах времени при выполнении соответствующих алгоритмов на вычислительных установках.
Если для задачи $$R$$ имеется полиномиальная от $$n$$ верхняя оценочная функция, то говорят, что $$R$$ разрешима в полиномиальное время.
Для многих задач не удается установить существование верхних
полиномиальных оценочных функций. Однако при этом распознавание на паре
слов $$u$$, $$v$$, является ли слово $$v$$ решением
задачи $$R$$ на входе $$u$$, решается за полиномиальное от длины
слова $$u$$ время
и, кроме того, для каждого $$u$$ существует ответ $$v$$,
длина которого ограничена некоторым полиномом от длины $$u$$. Это так
называемые задачи с проверяемым за полиномиальное время ответом.
Такой задачей является, например, задача о выполнимости
Задачи с проверяемым за полиномиальное время ответом называются переборными с гарантированным экспоненциальным перебором. Действительно, пусть $$R(u, v)$$ такая задача и длина возможного ответа $$v$$ ограничена полиномом $$p$$ от длины входа $$u$$, то есть $$|v| \le p (|u|)$$. Пусть, далее $$q$$ — полином, являющийся верхней оценкой времени работы программы, проверяющей ответ, тогда, перебирая всевозможные $$2^{{p}(|u|)}$$ слов длины $$p(|u|)$$ и затрачивая на проверку каждого не более $$q(|u|)$$ тактов времени, получим алгоритм с верхней оценкой $$q(u)\cdot 2^{p(|u|)}$$.
Задача $$R$$ полиномиально сводится к задаче $$R'$$, если существуют работающие полиномиальное время тьюринговы программы $$T_1$$ и $$T_2$$ такие, что$$\eq*{ \forall u \forall v' [R' (T_1(u), v') \to R(u, T_2 (v'))]. }$$
Из этого определения следует, что для решения задачи $$R$$ на входе $$u$$ достаточно
Таким образом, имеем следующую схему получения ответа $$v$$:$$\eq*{ u \to u' \to v' \to v. }$$
Оказывается, что среди задач с полиномиально проверяемым ответом существует задача, к которой полиномиально сводится любая другая задача с полиномиально проверяемым ответом. Такие задачи получили название универсальных переборных задач.
Исторически существование универсальных переборных задач обнаружено в 1971 году американским математиком C.A.Куком, когда он доказал, что задача выполнимости булевой формулы является универсальной переборной задачей. Тогда же было доказано, что и многие другие широко известные задачи являются универсальными переборными задачами.
Круг таких задач в настоящее время постоянно расширяется. По данному вопросу имеется обширная литература[3].
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.