понятие вычислимой/невычислимой функции

[manul91]

manul91 в сообщении #1513715 писал(а):

На практике исследующий алгоритм $A$ является своего рода супервизором над исследуемым алгоритмом $B$, т.е. $B$ ничего не знает про $A$ и потому не может использовать результат его работы.

home-mik в сообщении #1513716 писал(а):

Не знаю, разрешимая алгоритмически или нет, но то, что практически реализуемая, это уж точно : как я писал выше, нужно, чтобы исследуемая программа не получала результата работы исследующей, т.е. исследуемый алгоритм $B$ не принимает в качестве аргумента возвращаемое значение $A$. Ну, и контексты их работы, разумеется, изолированы, но это сугубо практическое замечание, для реализации на ЭВМ - для чистых функций, рассматриваемых в математике, это вроде само собой разумеется.

Нет.
Из того, что $A$ пытается "супервайзить" $B$ отнюдь не следует что $B$ не может реализировать в себе каким-нибудь образом весь функционал самого $A$ ("знать" $B$ или "не знать" про $A$ - это пустые антропоморфизмы). Для этого нет необходимости, чтобы $B$ на самом деле "вызывал" $A$ (аппаратно или еще как). В записи "возвращаемое значение $A$" - это просто обозначение что где-то в коде $B$ эффективно делает то же что и $A$ (вызывает или сам реализирует как-то, совершенно неважно).
Короче, $A$ по-любому можно подсунуть на вход любой алгоритм $B$.
Как вы будете определять, "реализует" или "не реализует" $B$ функционал $A$ каким-нибудь образом где-то в своих внутренностях? (чтобы "извинить" $A$ за то, что облажался когда ему подсунули $B$?)

[home-mik]

manul91 в сообщении #1513717 писал(а):

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

Так ну и пусть $B$ реализует в себе какой угодно код, в том числе и код $A$. Важно, что результат работы этого кода не будет интерпретироваться как вывод, остановится сам $B$ или нет. А так пусть $B$ делает, что хочет. Получает какой-то результат из этого кода, что-то с ним потом делает. Код ведь это просто набор инструкций, он - ничто без соответствующей интерпретаций.

Т.е. запись "возвращаемое значение $A$" не есть просто обозначение, что где-то в коде $B$ делает то же что и $A$. В данном случае это обозначение "возвращаемое значение $A$, интерпретируемое как вывод, остановится $B$ или нет".

Противоречия же могут получаться только после интерпретации кода. В самом коде противоречий нет - ему по-барабану

[manul91]

home-mik в сообщении #1513718 писал(а):

Так ну и пусть $B$ реализует в себе какой угодно код, в том числе и код $A$. Важно, что результат работы этого кода не будет интерпретироваться как вывод, остановится сам $B$ или нет. А так пусть $B$ делает, что хочет. Получает какой-то результат из этого кода, что-то с ним потом делает. Код ведь это просто набор инструкций, он - ничто без соответствующей интерпретаций.
Т.е. запись "возвращаемое значение $A$" не есть просто обозначение, что где-то в коде $B$ делает то же что и $A$. В данном случае это обозначение "возвращаемое значение $A$, интерпретируемое как вывод, остановится $B$ или нет".
Противоречия же могут получаться только после интерпретации кода. В самом коде противоречий нет - ему по-барабану

Непонятно о каких противоречий и интерпретаций вы говорите...
Очевидно, алгоритм $A$ не может являться универсальным определителем "остановочности" ибо таких не существует.
Другими словами, $A$ будет лажать для каких-то алгоритмов $B$.
В этом никакого противоречия нет.
Повторяю вопрос: Как вы будете определять, "реализует" или "не реализует" $B$ функционал $A$ каким-нибудь образом где-то в своих внутренностях? Т.е. является ли $B$ "хитрожопым" или нет? (чтобы "извинить" $A$ за то, что облажался когда ему подсунули $B$?)
Ведь весь смысл вашего предложения и состоит в том, чтобы "исключать хитрых" от рассмотрения.
Как конкретно исключать будем? :)
Вот берем какой-то алгоритм $B_1$ и оказывется что $A$ на нем ошибся.
Я говорю $A$ "плохой" определитель, он ошибся на $B_1$ - а не должен был, ибо $B_1$ "не хитрый".
Вы говорите - нет, $B_1$ "хитрый" и поэтому его нужно исключить, а $A$ (пока) "достаточно хорошо определяет".
Как узнать, кто из нас прав?

[home-mik]

manul91 в сообщении #1513719 писал(а):

Ведь весь смысл вашего предложения и состоит в том, чтобы "исключать хитрых" от рассмотрения.
Как конкретно исключать будем? :)

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

Вы, видимо, в рассуждениях просто не отделяете форму алгоритма от его содержания, т.е. интерпретации: раз формы, т.е. последовательности команд одинаковые, значит и означают они одно и то же. Но один и тот же код можно интерпретировать по-разному. Тот же парадокс лжеца, реализованный в коде, может интерпретироваться как генератор меандра, т.е. последовательности 0,1,0,1,0,1 ... . И никакого парадокса в нем при этом, само собой, нет.

На практике Вы алгоритмом $A$ вызываете любой алгоритм $B$ (но не наоборот) и определяете останавливается он или нет.

При такой формулировке условий, кстати, получается, что хитрых алгоритмов вообще нет, и ничто не мешает результату работы $A$ быть верным. Странно.. Надо подумать.

[epros]

arseniiv в сообщении #1513672 писал(а):

Тут прямее всего по идее должно быть уже упомянутое сравнение мощностей

Небольшое отступление:

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

Так что для меня утверждение о существовании не рекурсивной всюду определённой функции $\mathbb{N} \to \mathbb{N}$ становится достаточно убедительным только после предъявления примера. А рассуждение с нумерацией общерекурсивных функций я интерпретирую не так, что их якобы "меньше", чем всех функций $\mathbb{N} \to \mathbb{N}$ , а так, что существование не пронумерованной функции является следствием неконструктивного предположения о существовании нумерации всех общерекурсивных функций.

arseniiv в сообщении #1513672 писал(а):

Если мы исключим каким-то хитрым способом один случай, мы всё равно ничего не исправим.

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

[manul91]

home-mik в сообщении #1513721 писал(а):

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

Не пойму в чем разница.
Если вы то, что "алгоритм $B$ где-то у себя внутри просто выполняет последовательность команд, совпадающих с последовательностью команд алгоритма $A$", решили обозвать "вызовом алгоритма определения собственной остановки" - это самого алгоритма $B$ не меняет. Ему от этого ни жарко ни холодно. Хоть горшком назови - важно что $B$ делает, а не как это обзывать.
Иначе я обозву одним способом, вы обозвете другим - как узнать, кто прав?
Кстати из того что $B$ где-то внутри реализирует функционал $A$, отнюдь не следует, что в $B$ обязательно должна существовать "последовательность команд совпадающая с последовательностью команд алгоритма $A$". По моему это очевидно (существуют самые разные последовательности команд осуществляющие один и тот же функционал). Так что на хорошего критерия проверки "на хитрость", это не годится.

home-mik в сообщении #1513721 писал(а):

Вы, видимо, в рассуждениях просто не отделяете форму алгоритма от его содержания, т.е. интерпретации: раз формы, т.е. последовательности команд одинаковые, значит и означают они одно и то же. Но один и тот же код можно интерпретировать по-разному.

По-моему совершенно очевидно, что если последовательности команд (машины тьюринга) одинаковые, то они делают одно и то же (обратное разумеется, неверно). Причем тут какие-то интерпретации? Если вы ежа обозвете орлом то он от этого не полетит.

[epros]

home-mik в сообщении #1513721 писал(а):

Если алгоритм $B$ сам вызывает алгоритм определения собственной остановки $A$, значит он хитрый.

Как бы то ни было, Вы пока никак не определили способ "исключения". Сказать, например, что алгоритм должен быть таким, чтобы при предъявлении собственного кода останавливаться и печатать: "Не могу разрешить вопрос о собственной остановке", - недостаточно. Потому что добавление пары пустых операторов делает код "другим", позволяя легко обойти это ограничение. А способ определения "сути" алгоритма по его коду, опять же, пока не придумали.

[home-mik]

epros в сообщении #1513728 писал(а):

Как бы то ни было, Вы пока никак не определили способ "исключения".

Самое интересное, что формулировка доказательства несуществования общего алгоритма определения останова, сама исключает из рассмотрения все варианты, кроме рассматриваемого в доказательстве. Который затем приводит к абсурду. Она же по сути только приводит пример программы, для которой такого алгоритма нет точно. Потому что если есть, то получается абсурд (доказательство от противного). Про остальные программы она ничего не говорит. Она не говорит, что для всех программ или для каких-нибудь классов программ нельзя доказать, остановятся они или нет. Она говорит только, что единого общего алгоритма для вообще всех программ нет точно, а какие-то частные, для каких-то отдельных классов может и есть.

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

-- 10.04.2021, 12:15 --

Тут меня еще Верещагин-Шень немного в недоумение ввел таким примером: пишет, что функция $\sin{x}$ вещественного аргумента вычислима, в то время как функция $sign(x)$, которая при $x < 0$, $x = 0$, $x > 0$ принимает значения соответственно -1, 0, 1, невычислима (при разумном расширении понятия вычислимости до вещественных чисел).

Вот это откуда? Функция определения знака что, алгоритмически не разрешима?

[epros]

home-mik в сообщении #1513731 писал(а):

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

Вы что-то путаете. Никакого примера нет. Есть только предположение о его существовании, которое опровергнуто.

home-mik в сообщении #1513731 писал(а):

Она не говорит, что для всех программ или для каких-нибудь классов программ нельзя доказать, остановятся они или нет.

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

home-mik в сообщении #1513731 писал(а):

функция $sign(x)$, которая при $x < 0$, $x = 0$, $x > 0$ принимает значения соответственно -1, 0, 1, невычислима (при разумном расширении понятия вычислимости до вещественных чисел).

Вот это откуда? Функция определения знака что, алгоритмически не разрешима?

Именно так. Просто можно таким образом определить вещественное число, что будет неизвестно, равно оно нулю или нет. Функцию $\operatorname{sign}(x)$ от такого аргумента, разумеется, вычислить не удастся. Теорема всего лишь говорит, что какая бы продвинутая у нас ни была математика, всегда найдётся такое число $x$, для которого $\operatorname{sign}(x)$ вычислить не удастся, потому что общего алгоритма не существует.

[home-mik]

epros в сообщении #1513739 писал(а):

home-mik в сообщении #1513731 писал(а):

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

Вы что-то путаете. Никакого примера нет. Есть только предположение о его существовании, которое опровергнуто.

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

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

-- 10.04.2021, 13:58 --

epros в сообщении #1513739 писал(а):

home-mik в
[quote="home-mik в сообщении #1513731 писал(а):

функция $sign(x)$, которая при $x < 0$, $x = 0$, $x > 0$ принимает значения соответственно -1, 0, 1, невычислима (при разумном расширении понятия вычислимости до вещественных чисел).

Вот это откуда? Функция определения знака что, алгоритмически не разрешима?

Именно так. Просто можно таким образом определить вещественное число, что будет неизвестно, равно оно нулю или нет. Функцию $\operatorname{sign}(x)$ от такого аргумента, разумеется, вычислить не удастся. Теорема всего лишь говорит, что какая бы продвинутая у нас ни была математика, всегда найдётся такое число $x$, для которого $\operatorname{sign}(x)$ вычислить не удастся, потому что общего алгоритма не существует.

А как тогда $\sin{x}$ вычисляется, если мы точно не знаем равен его аргумент нулю или нет? Проблема то одна и та же в обоих случаях получается: мы не можем точно определить вещественное число.

[epros]

home-mik в сообщении #1513745 писал(а):

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

Говорят, что если часы пробили 13 раз, то это порождает сомнение не только в последнем ударе, но и в 12-ти предыдущих.

Мы предположили, что алгоритм правильно разрешает вопрос остановки по любому предъявленному ему коду алгоритма. Нет никакого разумного способа отделить "неправильные" случаи работы разрешающего алгоритма от "правильных". Либо весь алгоритм в целом правильный, либо мы не можем полагаться на выдаваемые им результаты. Дописывать к разрешающему алгоритму какие-то проверки того, не предъявлен ли ему "его собственный" код, очевидно бессмысленно. Потому что если разрешающий алгоритм существует, то он должен как-то анализировать логику "зацикливания", независимо от того, чей это код - его собственный или нет. Отказ анализировать какие-то конкретные коды просто ничего не даст.

-- Сб апр 10, 2021 15:12:14 --

home-mik в сообщении #1513745 писал(а):

А как тогда $\sin{x}$ вычисляется, если мы точно не знаем равен его аргумент нулю или нет? Проблема то одна и та же в обоих случаях получается: мы не можем точно определить вещественное число.

С синусом всё, как ни странно, проще. Это аналитическая функция. Просто берём разложение синуса в степенной ряд около нуля и для любого аргумента (который сам по себе является некой фундаментальной последовательностью рациональных чисел) находим фундаментальную последовательность рациональных чисел, которая сходится к значению функции.

Вообще, есть какая-то теорема о том, что любая вычислимая функция $\mathbb{R} \to \mathbb{R}$ является непрерывной.

[arseniiv]

Я только напомню, что есть несколько вычислимых аналогов $\mathbb R$ разной силы. Убедитесь, что говорите об одном и том же.

manul91 в сообщении #1513709 писал(а):

Если не помните, откуда знаете что не единственный?

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

home-mik в сообщении #1513714 писал(а):

Не совсем понял, почему мощность множества вычислимых функций $A \to B$ точно меньше, чем множество счетных. Можете пример привести?

Ну вот то же $\mathbb N \to \mathbb N$ — континуальное, а множество вычислимых из них — счётное, потому что как бы мы ни формализовали понятие алгоритма, это будет так, и часто это будет подмножество некоторого $\Sigma^*$ для какого-то очевидного конечного или счётного $\Sigma$.

(Например)

Например для (обычной необобщённой) машины Минского мы имеем какое-то конечное множество $R$ регистров, конечное множество состояний $S$, начальное состояние $s_0$ из $S_H := S \cup \{ \mathtt{HALT} \}$ и функцию перехода $d \colon S \to (R \times S_H) \cup (R \times R \times S_H) \cup (R \times R \times S_H \times S_H)$. При выполнении машина преобразует память $m \colon R \to \mathbb N$ следующим образом за один шаг. Если машина находится в состоянии $\mathtt{HALT}$, она прекращает работу. Пусть машина находится в состоянии $s \in S$, тогда рассмотрим $d(s)$:
• если $d(s) = (r_1, s_1)$, мы присваиваем $m(r_1) := 0$ и переходим в состояние $s_1$;
• если $d(s) = (r_1, r_2, s_1)$, мы присваиваем $m(r_2) := m(r_1) + 1$ и переходим в состояние $s_1$;
• если $d(s) = (r_1, r_2, s_1, s_2)$, смотрим, что находится в $m(r_1)$: если там 0, переходим в $s_1$, а если там некоторое $n + 1$, то присваиваем $m(r_2) := n$ и переходим в $s_2$.

Для простоты для таких машин полагают, что изначально $m(r) = 0$ для всех $r$, (хотя корректнее будет считать их неопределёнными и приводящими к неопределённому результату работы, если из подобного регистра читают до записи; но мне здесь лень определять такую корректность, удлиннит пост). Машине можно сопоставить функцию $\mathbb N^m \to \mathbb N^n$, пронумеровав некоторые из регистров числами $1..m$ как входные и числами $1..n$ как выходные; для вычисления такой функции от $(x_1, \ldots, x_m)$ мы помещаем в соответствующие входные регистры эти значения, выполняем машину до её завершения и после этого значением функции считаем кортеж значений выходных регистров (в заданном нами же порядке). Итого алгоритм вычисления функции задаётся набором $(R, S, s_0, d, I, O)$, где $I \colon 1..m \to R$ инъекция и $O \colon 1..n \to R$ нумеруют входные и выходные регистры. Такой набор тривиально кодируется строкой над алфавитом например $R \sqcup S \sqcup \{ \mathtt{HALT}, \texttt{|} \}$, где палка используется для разделения записей заранее неизвестной длины.

[epros]

(Оффтоп)

arseniiv в сообщении #1513760 писал(а):

Я только напомню, что есть несколько вычислимых аналогов $\mathbb R$ разной силы. Убедитесь, что говорите об одном и том же.

Я про:

epros в сообщении #1513748 писал(а):

фундаментальную последовательность рациональных чисел

ибо другие аналоги $\mathbb R$ полагаю недостаточно аналогичными.

[arseniiv]

(Оффтоп)

epros
Просто фундаментальную или ещё и с «регулятором сходимости»?

[svv]

epros в сообщении #1513748 писал(а):

Вообще, есть какая-то теорема о том, что любая вычислимая функция $\mathbb{R} \to \mathbb{R}$ является непрерывной.

У дилетанта тогда сразу возникает вопрос: что, и $\operatorname{sign}(x)$ невычислима?