Теория алгоритмов: "аксиома протокола"

[Anton_Peplov]

Напомним, что областью применимости алгоритма $A(x)$ называется множество таких $x$, что $A(x)$ останавливается. Область применимости алгоритма совпадает с областью определения функции, которую он вычисляет. Например, алгоритм, вычисляющий функцию $ y = \frac{1}{1-x}$, при $x = 1$ не останавливается.

Назовем алфавитом конечное множество, для которого определен алгоритм проверки элементов на равенство.
Словом алфавита $\Pi$ назовем конечный упорядоченный набор его элементов. Множество всех слов алфавита $\Pi$ обозначим $\Pi^\infty$.

В книге В. А. Успенского "Теорема Геделя о неполноте" М.: Наука, 1982 на с. 35 вводится т.н. "аксиома протокола":

Для каждого алгоритма $A(x)$ существует алфавит $\Pi$ ("алфавит протоколов"), разрешимое подмножество $\Pi^\infty$ $P$ (“множество протоколов”) и определенные на $P$ вычислимые функции $a(p)$ и $z(p)$ такие, что $A(x) = y$ если и только если найдется такое $p$ из $P$, что $x = a(p)$, $y = z(p)$.

Из этого утверждения делаются сильные выводы – о перечислимости области применимости и области возможных результатов каждого алгоритма (перечисление соответственно функциями $x = a(p)$, $y = z(p)$), о перечислимости графика любой вычислимой функции.

Успенский «аксиому протокола» не доказывает, а постулирует (что не означает, что она недоказуема – просто у него не учебник теории алгоритмов). А меня вот до крайности смущает требование разрешимости множества протоколов. Я не могу себе представить, на что должен быть похож протокол, чтобы оно выполнялось.

Возьмем алгоритм $A$, областью применимости которого является некоторое собственное подмножество натурального ряда (не весь натуральный ряд). Попытаемся создать алфавит протоколов $\Pi$ и множество протоколов $P$ так, чтобы $P$ было разрешимо в $\Pi^\infty$, т.е. существовал алгоритм $R(p)$ такой, что $R(p) = 1$ если $p \in P$ и $R(p) = 0$ в противном случае.

Пусть, например, алфавит протоколов имеет вид $\Pi = \{begin, \to, 1, end\}$. Единица будет служить для записи натуральных чисел в унарной системе счисления. Обозначим $[x]$ запись числа $x$ в унарной системе. Например, $[3] = 111$. Пусть протокол, отвечающий переработке числа $[x]$ в число $[y]$, имеет вид $begin [x] \to [y] end$. Например, протокол, отвечающий переработке числа $5$ в число $2$, имеет вид $begin 11111 \to 11 end$.
Попытаемся создать алгоритм, выделяющий протоколы из всех остальных слов алфавита, то есть разрешающий $P$ в $\Pi^\infty$.
Написать алгоритм, выделяющий форму $begin [x] \to [y] end$ из всех остальных слов, несложно. Но чтобы она была протоколом алгоритма $A$, этого мало. Нужно, чтобы алгоритм действительно перерабатывал $x$ именно в $y$. Например, если $A(x)$ - алгоритм вычисления функции $y = x - 3$, то $begin 11 \to 11 end$ не является его протоколом.
Итак, алгоритм $R(p)$ выделения протоколов из всех остальных слов языка должен решать следующие задачи:
1) распознавать форму $begin [x] \to [y] end$
2) распознав эту форму, проверить, действительно ли $y = A(x)$.
Для выполнения второй задачи требуется запустить сам алгоритм $A$. Но если $x$ не лежит в области применимости $A$ (а мы не зря оговорились, что это не весь натуральный ряд), то $A(x)$ не остановится и, значит, не остановится (и не сможет выдать ни $0$, ни $1$) и $R(p)$!

Быть может, пометить протоколы определенным значком? Например, пусть алгоритм перерабатывает $5$ в $2$. Тогда $begin 11111 \to 11 end$ будет его протоколом, а $begin 11111 \to 1111 end$ - нет. Снабдим протоколы дополнительным значком $T$ ($begin 11111 \to 11 endT$) и по этому значку будем распознавать их. Увы, это не работает. Нам нужно распознать протокол среди множества $\Pi^\infty$ всех слов алфавита $\Pi$, то есть всех конечных упорядоченных наборов его букв. Наряду с $begin 11111 \to 11 end T$ там будут и $begin 11111 \to 1111 end T$, и $begin 11111 \to 1111111 end T$, то есть задача сводится к предыдущей.

Тогда, быть может, придумать алфавит $\Pi$ так, чтобы в нем можно было записать числа только из области применимости $A$ и нельзя – другие числа? Увы, и это невозможно. Потому что множество всех записей чисел должно быть разрешимо в $\Pi^\infty$, иначе алгоритм выделения протоколов $R(p)$ споткнется уже на этапе распознавания числа. А множество $\Pi^\infty$ эффективно счетно и, следовательно, эффективно счетно множество всех записей чисел как его разрешимое подмножество. Тогда «аксиому протокола» можно будет сформулировать только для алгоритма, область применимости которого эффективно счетна. А это не для всех алгоритмов так. Например, область применимости алгоритма $A(n) = A_n(n)$, где $ A_n $ - алгоритм с геделевским номером $n$, не является эффективно счетной. А для алгоритмов с эффективно счетной областью применимости и изобретать ничего не надо, достаточно использовать в качестве протокола эффективные номера точек из области применимости.

Так на что может быть похож протокол, какие есть версии?

И, кстати, нельзя ли доказать перечислимость области применимости любого алгоритма как-нибудь иначе?

[Anton_Peplov]

У меня появилось смутное ощущение, что где-то здесь я путаю необходимое с достаточным. Но я не могу понять, где.

[Xaositect]

Anton_Peplov в сообщении #918991 писал(а):

Пусть, например, алфавит протоколов имеет вид $\Pi = \{begin, \to, 1, end\}$. Единица будет служить для записи натуральных чисел в унарной системе счисления. Обозначим $[x]$ запись числа $x$ в унарной системе. Например, $[3] = 111$. Пусть протокол, отвечающий переработке числа $[x]$ в число $[y]$, имеет вид $begin [x] \to [y] end$. Например, протокол, отвечающий переработке числа $5$ в число $2$, имеет вид $begin 11111 \to 11 end$.
Попытаемся создать алгоритм, выделяющий протоколы из всех остальных слов алфавита, то есть разрешающий $P$ в $\Pi^\infty$.
Написать алгоритм, выделяющий форму $begin [x] \to [y] end$ из всех остальных слов, несложно. Но чтобы она была протоколом алгоритма $A$, этого мало. Нужно, чтобы алгоритм действительно перерабатывал $x$ именно в $y$. Например, если $A(x)$ - алгоритм вычисления функции $y = x - 3$, то $begin 11 \to 11 end$ не является его протоколом.
Итак, алгоритм $R(p)$ выделения протоколов из всех остальных слов языка должен решать следующие задачи:
1) распознавать форму $begin [x] \to [y] end$
2) распознав эту форму, проверить, действительно ли $y = A(x)$.
Для выполнения второй задачи требуется запустить сам алгоритм $A$. Но если $x$ не лежит в области применимости $A$ (а мы не зря оговорились, что это не весь натуральный ряд), то $A(x)$ не остановится и, значит, не остановится (и не сможет выдать ни $0$, ни $1$) и $R(p)$!

Суть протоколов как раз в том, что алгоритм проверки протокола не обязан вычислять $A(x)$.
Не помню, что пишет по этому поводу Успенский, но протокол по идее это запись процесса работы алгоритма. Соответственно, если этот процесс конечен, то протокол будет существовать, а если алгоритм на некотором входе не останавливается - то протокола с этим входом вообще не будет существовать.
Разрешимость получается из того, что каждый шаг алгоритма по идее должен быть какой-то простой операцией и можно проверить, что одно состояние работы алгоритма получается из другого одним шагом.

Например, рассмотрим такой алгоритм: Получаем на вход пару чисел, первое число удваиваем, пока оно не станет равно второму, результат - количество таких удваиваний. Можно построить такое множество протоколов: язык $1, *, \rightarrow$, пара чисел $(m, n)$ кодируется как $1^m*1^n$ протокол состоит из всех пар, получающихся в процессе работы алгоритма, в том порядке, в котором они получаются, пары разделяются $\rightarrow$. Например, на входе $1, 8$ протокол будет такой: $1*11111111\rightarrow11*11111111\rightarrow1111*11111111\rightarrow11111111*11111111$. Алгоритм проверки протокола должен проверить, что протокол - это последовательность пар, разделенных стрелочками, что каждая следующая пара получается из предыдущей с помощью удвоения первого элемента, и что в последней паре компоненты равны. Все это разрешимо. Если входная пара не входит в область применимости алгоритма, то правильного протокола, начинаюющегося с этой пары, существовать не может.

[Lukin]

Xaositect в сообщении #919203 писал(а):

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

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

[Xaositect]

Lukin в сообщении #919242 писал(а):

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

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

[Anton_Peplov]

Xaositect в сообщении #919203 писал(а):

протокол по идее это запись процесса работы алгоритма.

Елки да ежи, как просто-то! Предлагаю универсальную схему построения и распознавания протоколов для фиксированного алгоритма $A$.

Пусть $\Pi$ - алфавит машины Тьюринга, реализующей $A$, с добавлением $\to$ для обозначения границ между словами. Пусть протокол переработки входных данных $x_0$ (где $x_0$ - слово на ленте машины до ее запуска) имеет вид $ x_0 \to x_1 \to …. x_n$.
Разрешающий алгоритм $R(p)$ будет выглядеть следующим образом:
1) $p$ - это последовательность слов алфавита машины, разделенных стрелочками? Если нет, то это не протокол. Если да, идем дальше.
2) Запустим машину с начальной конфигурацией $ x_0$ и дадим ей сделать один шаг. На ленте появилось $ x_1$? Если нет, то $p$ - не протокол. Если да, идем дальше.
3) Таким же образом проверяем $ x_2$, $x_3$,… $x_n$. Если на каком-то $k$-том шаге выявилось различие между словом на ленте после этого шага и $x_k$, то $p$ - не протокол.
4) Если мы благополучно добрались до $x_n$, остается задать один вопрос: машина, записав $x_n$, остановилась? Если нет, то $p$ - не протокол, финиш, все свободны. Если же да, то $p$ - протокол, ура, пьем шампанское.

И этот наш алгоритм ни при каком $p$ не может зациклиться. Даже если очень захочет.

Я правильно рассудил?

[Xaositect]

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

[Lukin]

Посмотрел Успенского, дословно написано следующее (в электронном варианте стр.35):
"1) для каждого алгоритма $A$ имеется некоторый алфавит $\Pi_0$ (алфавит протоколов) и всевозможные протоколы, фиксирующие работу $A$ при различных исходных данных из его области применимости, образуют подмножество $P_0$, множества $\Pi_0$".
ТС невнимательно читал, и получилось, что задал вопрос не про "аксиому протокола", а про другое.

[Anton_Peplov]

Xaositect в сообщении #919330 писал(а):

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

Да, я имел в виду машину, у которой до начала работы на ленте лишь конечное число символов. И по окончании, соответственно, тоже.

А что касается "записывать позицию головки и состояние машины", то, если вместе с алгоритмом фиксировать и реализующую его машину Тьюринга, зачем их записывать?

-- 15.10.2014, 22:34 --

Lukin в сообщении #919334 писал(а):

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

Это Вы обо мне или о себе?

[Lukin]

Anton_Peplov в сообщении #919337 писал(а):

Это Вы обо мне или о себе?

Пусть $\Pi$ - алфавит Тьюринг - полного языка, $R$ - алгоритм, разрешающий $P$ в $\Pi^\infty$ относительно $A$ (например, приведенный Вами). Пусть $A=R$.
Что можно сказать об области применимости данного алгоритма ? Какое-нибудь слово (или пару из протокола) ?

[Anton_Peplov]

Lukin в сообщении #919372 писал(а):

Пусть $\Pi$ - алфавит тьюринг-полного языка

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

[Anton_Peplov]

Lukin в сообщении #919372 писал(а):

Что можно сказать об области применимости данного алгоритма ?

Область применимости вышеописанного алгоритма $R(p)$ - все $\Pi^\infty$. Проверяя цепочку $x_0 \to x_1 \to ... \to x_n$, он запускает машину Тьюринга, выполняющую $A$, не более чем на $n$ шагов. Если на $n$-ном шаге машина остановилась сама, $R(p)$ печатает $1$ и останавливается. Если на $n$-ном шаге машина алгоритма $A$ не остановилась, $R(p)$ останавливает ее принудительно, после чего печатает $0$ и останавливается. Как можно зациклить такой алгоритм? Буду благодарен, если подскажете.

Я понимаю, что Вы имеете в виду проблему остановки. Именно она возникает, когда алгоритм работает с собственным описанием или вообще когда это универсальный алгоритм. Но нам не требуется запускать $A(x_0)$ и ждать, что он когда-нибудь сам остановится. Мы его выполним максимум до $n$-го шага, после чего остановим в любом случае. Поэтому число шагов по выполнению алгоритма $R(p)$ будет конечным при любых, подчеркиваю - любых входных данных.

Я в чем-то не прав?

[Xaositect]

Anton_Peplov в сообщении #919337 писал(а):

А что касается "записывать позицию головки и состояние машины", то, если вместе с алгоритмом фиксировать и реализующую его машину Тьюринга, зачем их записывать?

Потому что следующее слово зависит от состояния машины и положения головки.

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

-- Чт окт 16, 2014 08:36:42 --

Lukin в сообщении #919372 писал(а):

Пусть $\Pi$ - алфавит Тьюринг - полного языка, $R$ - алгоритм, разрешающий $P$ в $\Pi^\infty$ относительно $A$ (например, приведенный Вами). Пусть $A=R$.
Что можно сказать об области применимости данного алгоритма ? Какое-нибудь слово (или пару из протокола) ?

Anton_Peplov в сообщении #919385 писал(а):

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

Верно. Lukin, не путайте человека.

[Anton_Peplov]

Xaositect в сообщении #919422 писал(а):

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

Пробую. Пусть $A$ - алгоритм добавления к слову из подряд идущих единиц еще двух единиц справа. Будем считать, что машина Тьюринга перед стартом обозревает крайнюю левую единицу (это называется стандартной начальной конфигурацией, если я ничего не путаю).
Программа:
Команда 1. $q_1 1 \to q_1 1 R$ (если встретилась единица, не трогаем ее и переходим в следующую ячейку)
Команда 2. $q_1 * \to q_2 1 R$ (если встретился разделитель, меняем его на единицу, переходим в следующую ячейку и готовимся на следующем шаге завершить программу)
Команда 3. $q_2 \to q_z 1$ (меняем любое содержимое ячейки на единицу и останавливаемся).

Составим протокол работы программы с исходными данными $11*$.
Слова на ленте машины будут иметь следующий вид.
До запуска: $11*$
После первого шага: $11*$ (обозрели первую единицу и выполнили команду 1: улыбнулись и сдвинулись вправо).
После второго шага: $11*$ (обозрели вторую единицу и снова выполнили команду 1: улыбнулись и сдвинулись вправо).
После третьего шага: $111$ (обозрели разделитель и выполнили команду 2: заменили его на единицу и сдвинулись вправо).
После четвертого шага: $1111$ (выполнили команду 3: дописали единицу и остановились).
Итого протокол будет иметь вид $ p = 11* \to 11* \to 11* \to 111 \to 1111$.

Запускаем $R(p)$.
1) $p$ - это последовательность $1$ и $*$, разделенных $\to$? Да.
2) Запускаем $A(11*)$ и даем ей сделать один шаг. Слово на ленте - $11*$? Да.
3) Даем машине сделать второй шаг. Слово на ленте - $11*$? Да.
4) Даем машине сделать третий шаг. Слово на ленте - $111$? Да.
5) Даем машине сделать четвертый шаг. Слово на ленте - $1111$? Да.
6) Машина, сделав четвертый шаг, остановилась? Да.
Готово, $p$ - протокол, печатаем $1$.

Что не так?

[Xaositect]

Anton_Peplov в сообщении #919461 писал(а):

Что не так?

Все так. Я просто неправильно понял Ваше объяснение алгоритма проверки, я думал Вы для каждого слова $x_1, x_2$ и т.д. собирались заново запускать машину.