2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Теория алгоритмов: "аксиома протокола"
Сообщение14.10.2014, 21:30 
Заслуженный участник
Аватара пользователя


20/08/14
8062
Напомним, что областью применимости алгоритма $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$, не является эффективно счетной. А для алгоритмов с эффективно счетной областью применимости и изобретать ничего не надо, достаточно использовать в качестве протокола эффективные номера точек из области применимости.

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

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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 00:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 14:48 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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$. Алгоритм проверки протокола должен проверить, что протокол - это последовательность пар, разделенных стрелочками, что каждая следующая пара получается из предыдущей с помощью удвоения первого элемента, и что в последней паре компоненты равны. Все это разрешимо. Если входная пара не входит в область применимости алгоритма, то правильного протокола, начинаюющегося с этой пары, существовать не может.

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 17:07 


06/07/11
192
Xaositect в сообщении #919203 писал(а):
Если входная пара не входит в область применимости алгоритма, то правильного протокола, начинаюющегося с этой пары, существовать не может.

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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 17:14 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Lukin в сообщении #919242 писал(а):
Тут вот какое дело. Как разрешающий алгоритм определит, в область применимости какого алгоритма она не входит ? В одном и том же алфавите записаны протоколы разных алгоритмов. Как определить по произвольному входу (паре из протокола) применимость произвольного алгоритма. Это же проблема останова. :|
В "аксиоме протокола" этого и не требуется. Нужно только уметь проверять, что протокол корректен, и определять вход и выход алгоритма по протоколу.

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 20:52 
Заслуженный участник
Аватара пользователя


20/08/14
8062
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$ не может зациклиться. Даже если очень захочет.

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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 20:58 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 21:09 


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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 21:33 
Заслуженный участник
Аватара пользователя


20/08/14
8062
Xaositect в сообщении #919330 писал(а):
Только надо записывать не только слово на ленте, а еще позицию головки и состояние машины. Ну и в зависимости от определения МТ может потребоваться сказать пару слов про то, что бесконечная лента не нужна и после конечного числа шагов нас интересует только ограниченная область ленты.


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

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

-- 15.10.2014, 22:34 --

Lukin в сообщении #919334 писал(а):
невнимательно читал, и получилось, что задал вопрос не про "аксиому протокола", а про другое.


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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 23:24 


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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение15.10.2014, 23:56 
Заслуженный участник
Аватара пользователя


20/08/14
8062
Lukin в сообщении #919372 писал(а):
Пусть $\Pi$ - алфавит тьюринг-полного языка

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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение16.10.2014, 01:54 
Заслуженный участник
Аватара пользователя


20/08/14
8062
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)$ будет конечным при любых, подчеркиваю - любых входных данных.

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

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение16.10.2014, 07:34 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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, не путайте человека.

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение16.10.2014, 10:46 
Заслуженный участник
Аватара пользователя


20/08/14
8062
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$.

Что не так?

 Профиль  
                  
 
 Re: Теория алгоритмов: "аксиома протокола"
Сообщение16.10.2014, 10:50 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Anton_Peplov в сообщении #919461 писал(а):
Что не так?
Все так. Я просто неправильно понял Ваше объяснение алгоритма проверки, я думал Вы для каждого слова $x_1, x_2$ и т.д. собирались заново запускать машину.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 31 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group