Главная Промышленная автоматика.

гл. 0. гтрЕдв.арительные математические СВЁД1,НИЯ

Отображение множества частных случаев проблемы во множество {да, нет) называется решением проблемы. Если это отображение можно задать алгоритмом, то проблема называется (алгоритмически) разрешимой. Если алгоритма, определяющего это отображение, нет, то проблема называется (алгоритмически) неразрешимой.

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

Пример 0.19. Исследуем проблему: „Является лн частичный алгоритм Р (всюду определенным) алгоритмом?" Анализ этой проблемы покажет, почему некоторые проблемы оказываются неразрешимыми. Сначала предположим, что все частичные алгоритмы описываются в некоторой формальной системе вроде тех, что были упомянуты ранее в этом разделе.

В любом формальном языке, предназначенном для задания алгоритмов, можно, оказывается, описать только счетное число алгоритмов. Хотя мы не можем доказать это здесь в общем виде, рассмотрим один пример формализма - язык „абсолютных" машинных программ, а другие упомянутые формализмы отложим до упражнений. Любая программа в абсолютном машинном языке представляет собой конечную последовательность нулей и единиц (которые можно представлять себе сгруппированными в машинные слова по 32, 36, 48 или другому числу знаков).

Допустим, у нас есть цепочка из нулей и единиц, представляющая программу в машинном языке. Этой программе можно приписать натуральное число (номер), соответствующее ее положению в некотором полном упорядочении всех цепочек из нулей и единиц. Одно такое упорядочение можно получить, расположив цепочки по возрастанию их длин, а цепочки равной длины упорядочив лексикографически (при этом каждая цепочка рассматривается как двоичное число). Так как число цепочек любой заданной длины конечно, то любой цепочке из множества {О, 1} * будет поставлено в соответствие некоторое целое положительное число. Первые несколько пар этого биективного соответствия приведены в табл. 0.1. Таким образом, мы вндим, что для каждой программы в машинном языке можно однозначно найти соответствующее целое положительное число и для каждого такого числа можно найти некоторую программу.

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

0,4. алгоритмы (частичные и всюду определенные)

алгоритмическом формализме. Более того, это соответствие между алгоритмами и числами достаточно просто, так что по данному числу t можно записать соответствующий алгоритм, а по данному алгоритму найти соответствующее число.

Предположим, что существует частичный алгоритм Pj, который является (всюду определенным) алгоритмом, на его вход

Таблица 0.1

Число

Цепочка

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

Алгор итм Pf.

Вход. Любой частичный алгоритм Я, имеющий одну входную переменную.

Выход. (1) „Нет", если (а) Р не является алгоритмом или (6) Р является алгоритмом и Р (Р) =,>да". (2) ,Да" в остальных случаях.

/Запись Р {Р} означает, что мы применяем частичный алгоритм Р к описанию его самого.

Метод. (1) Если Яу(Я)=„да", то перейти к шагу (2); в противном случае выдать на выходе „нет" и остановиться.

(2) Если Р-алгоритм и его входы-описания частичных алгоритмов, а выходы-ответы ,да" и „нет", то алгоритЯ применяет алгоритм Р к самому себе, т. е. к своему описацню.



) Кодирование алгоритмов натуральными числами часто наливают нумерацией алгоритмов. Одна такая нумерация упоминается в упр. 0,.4.10. „Стандартным" кодированиям соответствуют так называемые главные «.аи допустимые нумерации частично рекурсивных функций (см, [Мальцен, 1965], [Роджерс, 1967]).- Прим. перев.

0,4.6. Проблема соответствий Поста

В этом разделе мы приведем один пример неразрешимой проблемы, а именно проблему соответствий Поста. Далее эта проблема будет применяться для доказательства неразрешимости других проблем.

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

Пример 0.20. Рассмотрим следующий частный случай проблемы соответствий над алфавитом {а, Ь}:

{{abbb, b), (а, aab), (ba, b))

Последовательность {a, aab), (a, aab), (ba, b), {abbb, b) -решающая, так как

(a) (a) (ba) (abbb) = (aab) (aab) (b) (b)

Частный случай {{ab, aba), (aba, baa), {baa, aa)} проблемы соответствий не имеет решающих последовательностей, так как любая такая последовательность должна начинаться парой (аЬ, aba), а тогда общее число букв а в первых компонентах пар, входящих в последовательность, будет меньше числа букв а во вторых компонентах. □

Существует частичный алгоритм, который в некотором смысле „решает" проблему соответствий. А именно, можно линейно упорядочить всевозможные последовательности пар цепочек, которые можно построить по данному частному случаю проблемы. Затем можно начать проверять для каждой последовательности, является ям она решающей. Обнаружив первую решающую последовательность, алгоритм остановится и ответит „да". Если решающей последовательности не окажется, то этот частичный алгоритм будет работать бесконечно.

Однако всюду определенного алгоритма, решающего проблему соответствий ) (т. е. выдающего правильный ответ „да" или „нет" для любого частного случая проблемы), не существует - можно

Ивд адвзитом X, содержащим не менее двух символов.-У7р«ж. перев,

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

(3) выдает „нет" или „да", если Р выдает ,да" или „нет" соответственно. □

Мы видим, что Pf-(всюду определенный) алгоритм, если /-алгоритм. При этом Pf имеет одну входную переменную. Но что же делает Р, когда он сам подается на свой вход? По предположению алгоритм Pj определяет, что Pf - алгоритм (т.е. Ру (Я) = „да"), затем Я моделирует себя на себе, т.е. свое поведение на своем описании, взятом в качестве входа. Но тогда Я не может дать непротиворечивый результат. Если Я устанавливает, что моделирование дает результат „да", то Я дает на выходе результат „нет". Но алгоритм Я определен так, что в применении к самому себе он должен давать ответ ,да". Аналогичный парадокс возникает, если Я обнаруживает, что моделирование дает результат „нет". Отсюда мы должны заключить, что предположение о существовании алгоритма Яу ошибочно, и, следовательно, проблема „является ли Я алгоритмом?" неразрешима для любого известного алгоритмического формализма. □

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

Следует особо отметить, что очень важную роль играет кодирование частных случаев проблемы. Обычно подразумевается некоторое „стандартное" кодирование (кодирование, для которого существует алгоритм, отображающий коды описаний алгоритмов в эквивалентные программы машин Тьюринга). Если используются нестандартные кодирования, то неразрешимые проблемы могут стать разрешимыми. Но в таких случаях не существует алгоритма, с помощью которого можно перейти от стандартного кодирования к нестандартному (см. упр. 0.4.21)).



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

УПРАЖНЕНИЯ

0.4.1. Совершенное wco-ЭТО натуральное число, равное сумме всех своих делителей (включая 1, но исключая само число). Например, 6 = 1+2 + 3 и 28 1+2 + 4 + 7+14~первые два совершенных числа (следующие три: 496, 8 128 и 33550336), . Постройте частичный алгоритм, который для входа i выдает иа выходе i-e совершенное число. (До сих пор неизвестно, конечно или бесконечно множество совершенных чисел.)

0.4.2. Докажите корректность алгоритма Евклида (пример 0.15).

0.4.3. Опишите алгоритм сложения двух п-значных десятичных чисел. Сколько времени и места требует этот алгоритм (т. е. каковы соответствующие функции от л)? (См. [Виноград, 1965], где обсуждается временная сложность сложения.)

0.4.4. Опишите алгоритм умножения двух л-знзчных чисел. Сколько времени и места требует этот алгоритм? (См. [Виноград, 1967] и [Кук и Аандераа, 1969], где обсуждается временная сложность умножения.)

0.4.5. Дайте алгоритм умножения двух целочисленьтых (пусп)-матрнц. Предположим, что каждую целочисленную арифметическую операцию можно выполнить за од;и1 шаг. .Какова тогда скорость (число шагов) Вашего алгоритма? Если она пропорциональна п, посмотрите работу Штрассена [1969], где дается асимптотически более быстрый алгоритм.

0.4.6. Пусть L{a,b\*. Характеристической функцией множества L называется такое отображение {а, 6}*-{0, 1}, что fi{w)\, если wL, я fi{w) - OB противном случае. Покажите, что L рекурсивно тогда и только тогда, когда -общерекурсив-иая функция.

0.4.7. Покажите, что L - рекурсивное множество тогда н

только тогда, когда оба множества L и L рекурсивно перечислимы.

0.4.8. Пусть Р - частичный алгоритм, определяющий рекурсивно перечислимое множество L{a,b}*. С помощью Я постройте алгоритм Р, который порождает все элементы множества L и только их, т. е, его выходом должна быть бесконечная цепочка вида # ..где L = {л\, х, ...}. Указание:

Постройте алгоритм Р так, чтобы для каждой пары (i, /) из

некоторого разумного упорядочения всех пар натуральных чисел он применял частичный алгоритм Р к у-й цепочке из множества \а, Ь}* в течение i шагов.

Определение. Машина Тьюринга состоит нз конечного множества состояний (Q), конечного множества символов ленты (Г) и функции 6 {функции переходов, или программы), которая отображает некоторое подмножество произведения Q х Г в множество Q X Т X {L, R\ В множестве Г выделяется подмножество 2 входных символов и один символ из г - 2 называется пустым. Одно состояние (Jq называется начальным. Машина Тьюринга работает на ленте, разделенной на ячейки, одну из которых обозревает головка. В любой момент времени все ячейки, кроме конечного числа, заняты пустыми символами. Конфигурацией машины Тьюринга называется пара ((/,аР), где q - состояние, ар - непустая часть ленты, а ( - специальный символ, показывающий, что головка обозревает ячейку, расположенную непосредственно справа от него (символ не является символом ленты и не занимает ячейки).

Следующая конфигурация (после {q, а f Р)) определяется с помощью символа А, обозреваемого головкой (это самый левый символ цепочки ft или пустой символ, если р -е), и значения функции b{q,A). Допустим, что {q, А)- {р. А, D), где р - состояние, А-символ леиты и D{L, Я]. Тогда следующей конфигурацией будет {р, ар), где аР образуется из ар заменой символа А, стоящего справа от t, на Л и сдвигом символа t на одну позицию в направлении D (влево, если D~L, и вправо, если D-R). Для того чтобы передвинуть символ 1, стоящий иа конце, может оказаться необходимым добавить на этом конце пустой символ.

Машину Тьюринга можно представлять себе как формальную систему, определяющую частичный алгоритм. Входом этого алгоритма может быть любая конечная цепочка wZ*. Алгоритм работает, начиная с конфигурации {q, \w) и последовательно , вычисляя следующие конфигурации. Если машина Тьюринга оатшавливается, т.е. достигает конфигурации, для которой следующий шаг невозможен (напомним, что функция б опреде-лена не обязательно для всех пар из Q X Г), то выходом является непустая часть ее ленты.

*0.4.9. Постройте машину Тьюринга, которая для данного входа w{0, !}* напишет на ленте слово ДА, если w-палиндром (т, е. ww), и НЕТ в противном случае, причем в любом случае остановится.

*в.4.10. Предположим, что каждая машина Тьюринга использует в качестве состояний и символов ленты конечное подмно-





0 1 2 3 4 5 [6] 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0019