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

[Anton_Peplov]

Вот спасибо Вам большое человеческое! Не знаю, сколько бы я еще ломал мозг об этот просто открывающийся ларчик.

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

Я просто неправильно понял Ваше объяснение алгоритма проверки.

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

[Lukin]

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

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

Не требуется. Это не важно. Возьмем алфавит $\Pi=\{0,1\}$, в нем кодируются любые конечные алфавиты, в т.ч. описания $x_0$, УМТ, всех протоколов и т.д.

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

Как можно зациклить такой алгоритм? Буду благодарен, если подскажете.

Примем, для простоты, что в ячейке ленты записано слово из $\Pi^\infty$ (это допустимо, т.к. эта ячейка эквивалентна блоку из протокола для МТ), а переходы состояний МТ по ячейкам заменим эквивалентными переходами по этим блокам.
Допустим, $A=R(p)$. Чтобы разрешить $(x_0, x_1)$, УМТ запускает саму себя, и сравнивает, соответствует ли $x_1$ протоколу (состоянию ленты и ее собственному состоянию на входе $x_0$). Это может потребовать конечной, а может и бесконечной рекурсии.

(Оффтоп)

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

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

Исключительно, здоровья для.

[Xaositect]

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

Примем, для простоты, что в ячейке ленты записано слово из $\Pi^\infty$ (это допустимо, т.к. эта ячейка эквивалентна блоку из протокола для МТ), а переходы состояний МТ по ячейкам заменим эквивалентными переходами по этим блокам.
Допустим, $A=R(p)$. Чтобы разрешить $(x_0, x_1)$, УМТ запускает саму себя, и сравнивает, соответствует ли $x_1$ протоколу (состоянию ленты и ее собственному состоянию на входе $x_0$). Это может потребовать конечной, а может и бесконечной рекурсии.

Я не понимаю эту конструкцию. Если задана некоторая машина $M$, некоторое слово $x$ и натуральное число $k$, то всегда можно вычислить результат работы $k$ шагов машины $M$ на слове $x$, никакой бесконечной рекурсии не требуется.

[Lukin]

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

Я не понимаю эту конструкцию.

Я не знаю.
Есть ссылка :

tenmin в сообщении #885661 писал(а):

Можно ли написать программу, которая "говорит" передали ей, или нет, её собственный код ? Т.е. такая программа $X$, что $X(X)=1$ и $X(P)=0$ для любых $P\neq X$.

Закончилось ли это, чем-то содержательным, мне не известно…
Допустим, да. Я не знаю. В нашей теме, вопрос, более общий, код зависит от стадии исполнения, и меняется с исполнением…

[Xaositect]

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

Есть ссылка...

Там все существует, по теореме о неподвижной точке.

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

В нашей теме, вопрос, более общий, код зависит от стадии исполнения, и меняется с исполнением…

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

[Anton_Peplov]

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

Все так.

Или у меня глюк, или я опять чего-то не понимаю. Потому что у меня получается, что из аксиомы протокола следует, будто область применимости любого алгоритма $A$ эффективно счетна.

Напомним, что биекция $f\colon X\to Y$ называется взаимно вычислимой, если вычислима как сама биекция $f\colon X\to Y$, так и обратная к ней $f^{-1} \colon Y\to X$ (кстати, а видел кто-нибудь вычислимую биекцию, обратная к которой не вычислима? Я на такого зверя не отказался бы посмотреть).

Теорема. Если есть взаимно вычислимая биекция $f\colon X\to Y$, и множество $X$ эффективно счетно, то эффективно счетно и множество $Y$.

Алгоритм приписывания номера элементу $y \in Y$:
1) найти $ x = f^{-1}(y)$
2) найти номер этого $x$ в эффективной нумерации $X$ $n = n(x)$
3)считать этот номер номером $y$.

Алгоритм восстановления элемента $y \in Y$ по номеру $n$:
1) Найти $x_n$ в эффективной нумерации множества $X$
2) Вычислить $y = f(x_n)$

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

Множество протоколов $P$ эффективно счетно как разрешимое подмножество эффективно счетного $\Pi^\infty$. Теперь остается доказать, что есть взаимно вычислимая биекция из $P$ в область применимости алгоритма $X$.

По определению, $x_0 = a(p)$ - вычислимая функция, определенная на $P$. Чтобы она была определена на $P$ и только на $P$, достаточно составить ее алгоритм, используя уже построенный $R(p)$: "если $p$ - протокол, выделить $x_0$ (как слово перед первой стрелкой) и остановиться; если $p$ - не протокол, не останавливаться". Обратная к ней функция определена на всей области применимости $A$ и только на ней и сводится к "запустить $A(x_0)$" - то есть это та самая функция, которую вычисляет $A$.

Итак, $x_0 = a(p)$ - взаимно вычислимая биекция между эффективно счетным $P$ и областью применимости алгоритма $X$. Из чего следует, что $X$ эффективно счетно. Но я еще в первом посте приводил пример алгоритма с не эффективно счетной областью применимости ($A(n) = A_n(n)$, где $n$ - номер алгоритма $A_n$ в геделевской или любой другой фиксированной эффективной нумерации всех алгоритмов).

Таким образом, где-то в мои рассуждения вкралась ошибка. Но где?

[Xaositect]

Эффективно счетно - это у вас что? Там точно не требуется, чтобы обратная функция была тотально вычислимой?

[Anton_Peplov]

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

Эффективно счетно - это у вас что?

Множество $X$ называется эффективно счетным, если существует взаимно вычислимая биекция между $X$ и множеством всех натуральных чисел. Сама эта биекция называется также эффективной нумерацией множества $X$.

[Xaositect]

А как у нас определяются вычислимые функции на множестве $X$?

У нас ведь такая ситуация, что $X$ - это подмножество множества слов в некотором алфавите. Что должна делать вычислимая биекция $X\to \mathbb{N}$, если на вход ей подали слово не из $X$? Если она может быть не определена, то любое бесконечное перечислимое множество является эффективно счетным, и область применимости $n\mapsto A_n(n)$ в том числе.

[Anton_Peplov]

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

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

А как у нас определяются вычислимые функции на множестве $X$?

Функция $y = f(x)$ , определенная на множестве $X$, называется вычислимой, если существует такой алгоритм $A$, что для любого $x \in X$ $y = A(x)$, а для любого $x \notin X$ $A(x)$ не останавливается.

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

любое бесконечное перечислимое множество является эффективно счетным

Почему? Как это доказать?

[Xaositect]

Ну по сути Вы это и доказали в предыдущем сообщении.

[Anton_Peplov]

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

Ну по сути Вы это и доказали в предыдущем сообщении.

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

Кстати, доказалась следующая красивая теорема.


Теорема. Если $y = f(x)$ вычислима и существует обратная к ней $x = f^{-1}(y)$, то $x = f^{-1}(y)$ тоже вычислима.

Алгоритм вычисления $x = f^{-1}(y)$:
1) Найти в $\Pi^\infty$ протокол $p$ такой, что $z(p) = y$.
Т.к. $\Pi^\infty$ эффективно счетно, а $P$ разрешимо, перебирая элементы $\Pi^\infty$ в порядке возрастания эффективных номеров и для всех протоколов вычисляя $z(p)$, мы рано или поздно найдем такой протокол $p$, что $z(p) = y$ – если он существует. Если же его не существует, то поиск не остановится – как и должно быть для алгоритма, вычисляющего$x = f^{-1}(y)$, когда ему подали $y$ не из области ее определения.
2) Вычислить $x = a(p)$.

Получается, что понятие взаимно вычислимой биекции, которое вводится в учебнике Матроса и Поднебесной, избыточно, т.к. не существует биекции, которая была бы вычислима, но не взаимно вычислима. Так?

[Xaositect]

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

Всякое (бесконечное) множество слов алфавита эффективно счетно, т.к. можно приписывать словам номера в алфавитном порядке. Так?

Нет, не всякое, только перечислимое.

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

Получается, что понятие взаимно вычислимой биекции, которое вводится в учебнике Матроса и Поднебесной, избыточно, т.к. не существует биекции, которая была бы вычислима, но не взаимно вычислима. Так?

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

Если Вас более подробно интересует теория вычислимости, я бы посоветовал сначала почитать Роджерса "Теория рекурсивных функций и эффективная вычислимость"

[Anton_Peplov]

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

Нет, не всякое, только перечислимое.

Да, свалял ваньку. Меня сбило то, что множество $T^\infty$ всех слов алфавита $T$ эффективно счетно. Но для него-то легко строится алгоритм нумерации: сначала все однобуквенные слова в алфавитном порядке, потом все двухбуквенные и т.д. А вот для неразрешимого в $T^\infty$ множества $M$ алгоритма нумерации может и не существовать. И, в частности, вышеуказанный алгоритм не годится, потому что заранее неизвестно, какие в $M$ есть однобуквенные слова, какие двухбуквенные и т.д. Для множества слов, отвечающего текстам всех тотальных алгоритмов, алгоритма нумерации точно не существует, это доказано.

Но послушайте, тогда я не понимаю, как доказать эффективную счетность перечислимого множества. Множество перечислимо, если оно является областью значений некоторой вычислимой функции, определенной на всем натуральном ряду. Но эта функция не обязана иметь обратную. Вы хотите сказать, что если есть вычислимая сюръекция $N \to Y$, то есть и вычислимая биекция? Я пытался это доказать, но у меня не вышло.

Другой подход к тому же вопросу - аксиома протокола. Будь $y = z(p)$ биекцией, из этого бы следовало, что область результатов всякого алгоритма эффективно счетна - в силу эффективной счетности множества протоколов $P$. Но для алгоритма, вычисляющего функцию, не имеющую обратной, $y = z(p)$ - не биекция. Ибо есть много протоколов с одним и тем же $y$. Всегда ли можно построить вычислимую биекцию $P \to Y$? Уже звучавший вопрос с другого бока. Тоже пытался доказать, что всегда, и тоже не вышло.

Так как же все-таки доказать?

[Xaositect]

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

Вы хотите сказать, что если есть вычислимая сюръекция $N \to Y$, то есть и вычислимая биекция? Я пытался это доказать, но у меня не вышло.

Да, это правда. Пусть алгоритм $A\colon \mathbb{N}\to Y$ перечисляет множество $Y$. Построим алгоритм $B$, который запускает $A$ сначала с аргументом 0, полученное значение сохраняет, потом запускает $A(1)$, полученное значение сравнивает с сохраненным, если оно новое, то сохраняет его тоже, и так далее - каждый раз очередное значение $A(k)$ сравнивается с предыдущими и отбрасывается, если оно уже встречалось. Если на вход алгоритма $B$ было подано число $n$, то он останавливается после получения $n$-го значения и выводит его.