Недоказуемое

[пианист]

manul91
А что Вы называете "вычислимой последовательностью"?

[manul91]

пианист в сообщении #1568877 писал(а):

manul91
А что Вы называете "вычислимой последовательностью"?

Последовательность типа 1,0,1,1,0,0,1,0...... (в данном случае) для которой существует алгоритм (реализированный на стандартной МТ) такой, что для любого натурального $k$ на входе (номера члена/разряда) он "коректно отрабатывает" выдавая за конечное время значение соответного члена/разряда последовательности 0 или 1.
Например цифры после запятой числа $\pi$ (в данном примере в двоичной базе) - вычислимая последовательность.

[пианист]

А, так согласен.
Не то чтобы по определению, но да, несложно написать соответствующую конструкцию.

[mihaild]

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

Еще вопрос насколько вообще осмысленно говорить про "конкретных" невычислимых последовательностей; что понимать под словом "конкретная".

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

[manul91]

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

mihaild в сообщении #1568886 писал(а):

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

Я просто хотел обратить внимание на некоторую принципиальную "эзотеричность" подобных утверждений/выражений - когда мы говорим про "эта последовательность", "конкретную последовательность" в связи с невычислимых последовательностей.

mihaild в сообщении #1568886 писал(а):

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

Ну да, вроде именно так и есть. Я не уверен что в этом есть смысл... Не совсем ясно как формализировать "МТ, выдающая эту последовательность с вероятностью больше 0,". Как дефинировать "вероятность над домене рандомизированных МТ выдающих каких-то последовательностей"? (а множество "рандомизированных МТ" даже и не счетно, на отличие от множества стандартных МТ).
Утверждение похоже на "вероятность выбрать реальное число в интервале (0,1) больше 0 если число вычислимо"...
И как это стыкуется с "штукенции Х" чье описание я привел выше в явном виде? Она класифицируется как "рандомизированная МТ" или нет и почему? Мне кажется, "она выдает невычислимую последовательность с вероятностью равной 1".

И кстати - еще ремарка к теме того, что якобы "истинная случайность ничего нового не дает" - в области криптографии/шифрования разница между "истинной" и "псевдо" случайностью существенна. Если как источника случайных чисел мы используем ГПСЧ (какой бы не навороченный он был) всегда есть принципиальная возможность его хакнуть (т.е. предсказать выдаваемые величины с вероятностью отличную от штатной) и тем самым скомпрометировать стойкость шифра; если используется источник "истинно случайных чисел" такое принципиально невозможно.

[mihaild]

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

Не совсем ясно как формализировать "МТ, выдающая эту последовательность с вероятностью больше 0,". Как дефинировать "вероятность над домене МТ выдающих последовательностей"?

Любая МТ с дополнительным бесконечным входом вычисляет частичную измеримую функцию. Соответственно она задает распределение вероятностей, относительно которого можно посмотреть на вероятность конкретной последовательности.
Например, МТ которая игнорирует этот дополнительный вход и просто выписывает какую-то последовательность - дает дельта-распределение. А МТ, которая копирует этот вход на выход - равномерное.

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

И кстати - еще ремарка к теме того, что якобы "истинная случайность ничего нового не дает"

Случайность ничего не дает в плане вычислимости. Что она дает в плане сложности - вопрос другой, и открытый. А криптография - вообще третий вопрос.

[manul91]

mihaild в сообщении #1568894 писал(а):

Случайность ничего не дает в плане вычислимости.

А как быть с "штукенции Х"? Она выдает невычислимую последовательность исключительно благодаря "источника случайности", если бы это была стандартная МТ то она не смогла бы выдать невычислимую последовательность.
Или это почему-то не считается "в плане вычислимости"?

mihaild в сообщении #1568894 писал(а):

Любая МТ с дополнительным бесконечным входом вычисляет частичную измеримую функцию. Соответственно она задает распределение вероятностей, относительно которого можно посмотреть на вероятность конкретной последовательности.
Например, МТ которая игнорирует этот дополнительный вход и просто выписывает какую-то последовательность - дает дельта-распределение. А МТ, которая копирует этот вход на выход - равномерное.

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

[mihaild]

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

Она выдает невычислимую последовательность исключительно благодаря "источника случайности"

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

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

как именно частично измеримая функция над бесконечной последовательности задает распределение вероятностей?

Не на последовательности, а на множестве последовательностей. Стандартным образом: вероятность множества относительно этого распределения равна вероятности его прообраза относительно исходного распределения.

[manul91]

mihaild в сообщении #1568898 писал(а):

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

Она выдает невычислимую последовательность исключительно благодаря "источника случайности"

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

Так насчет "штукенции Х" я уже несколько раз уточнял, что это значит - над любым натуральным $k$ (номера разряда последовательности) она выдает за конечное время значение 0 или 1 этого разряда, и подробно пояснял ее алгоритм работы в деталях, он тривиальный. Точно также задает и какую-то (вычислимую) последовательность стандартная МТ. Все в прежних сообщений, притом повторял несколько раз. Что именно осталось непонятным?
"Штукенция Х" классифицируется как то что вы называете "рандомизированными МТ", и если нет - почему?
Выдача "конкретной последовательности" вроде это тоже распределение, дельта-функция.

mihaild в сообщении #1568898 писал(а):

Не на последовательности, а на множестве последовательностей. Стандартным образом: вероятность множества относительно этого распределения равна вероятности его прообраза относительно исходного распределения.

Хорошо, какова численно вероятность чтобы стандартная МТ (или рандомизированная МТ) вычисляла вычислимую последовательность двоичных цифр $\pi$ (в двоичной записи) после запятой, и почему?
Какова численно вероятность чтобы какая-та из двух типов машин вычисляла невычислимую последовательность Чаитина, и почему?

[mihaild]

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

Что именно осталось непонятным?

Осталось непонятным, как определяется "штуковина что-то вычисляет". Т.е. ок, вы описали штуковину, теперь мы хотим проверить, удовлетворяет ли она некоторому определению ("вычисляет невычислимую последовательность"). Я не понимаю, какое тут берется определение слова "вычисляет". Потому что по классическому определению ваша штуковина (и вообще любая существенно рандомизированная МТ) не вычисляет вообще никакой последовательности.

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

Выдача "конкретной последовательности" вроде это тоже распределение, дельта-функция.

Да, но это очень специфическое распределение, про которое можно сказать много того, что нельзя сказать про произвольное (например взять $i$-й бит).

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

Хорошо, какова численно вероятность чтобы стандартная МТ (или рандомизированная МТ) вычисляла вычислимую последовательность двоичных цифр $\pi$ (в двоичной записи) после запятой, и почему?

Это зависит от МТ. Для стандартной это либо $0$ либо $1$, для рандомизированной - видимо, эта вероятность может быть как минимум произвольным перечислимым снизу числом. А что?

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

Какова численно вероятность чтобы какая-та из двух типов машин вычисляла невычислимую последовательность Чаитина, и почему?

Для стандартной - очевидно, $0$. Для рандомизированной - тоже $0$, потому что если есть рандомизированная МТ, выдающая константу Чайтина с вероятностью больше $0$, то из неё легко делается рандомизированная МТ, выдающая константу Чайтина с вероятностью $0.99$, а каждый бит она выдает, прочитав лишь конечное число битов случайного числа, так что запуская нашу рандомизированную МТ на всех возможных входах и дожидаясь, пока она остановится в достаточно большом количестве случаев, мы голосованием получаем константу Чайтина стандартно (и вроде я доказал, что если вероятность выдачи какой-то последовательности какой-то рандомизированной МТ больше нуля, то эта последовательность вычислима).

[warlock66613]

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

в области криптографии/шифрования разница между "истинной" и "псевдо" случайностью существенна. Если как источника случайных чисел мы используем ГПСЧ (какой бы не навороченный он был) всегда есть принципиальная возможность его хакнуть (т.е. предсказать выдаваемые величины с вероятностью отличную от штатной) и тем самым скомпрометировать стойкость шифра; если используется источник "истинно случайных чисел" такое принципиально невозможно.

Именно так. При этом неквантовые генераторы случайных чисел в этом контексте причисляются к "истинно случайным".

[manul91]

mihaild в сообщении #1568901 писал(а):

Осталось непонятным, как определяется "штуковина что-то вычисляет". Т.е. ок, вы описали штуковину, теперь мы хотим проверить, удовлетворяет ли она некоторому определению ("вычисляет невычислимую последовательность"). Я не понимаю, какое тут берется определение слова "вычисляет".

"Вычисляет" (двоичную) последовательность в следующем смысле: на вход подается любой натуральный номер $k$ разряда последовательности, за конечное время она выдает значение разряда, 0 или 1.
В том же самом смысле, считается что стандартная МТ "вычисляет" какую-то двоичную последовательность - если для любого натурального $k$ (номера разряда) на входе, она за конечное время выдает значение данного разряда, 0 или 1.

mihaild в сообщении #1568901 писал(а):

Потому что по классическому определению ваша штуковина (и вообще любая существенно рандомизированная МТ) не вычисляет вообще никакой последовательности.

Приведите классическое определение которым вы пользуетесь, по которому считается что стандартная (не "рандомизированная") МТ вычисляет какую-то последовательность.

mihaild в сообщении #1568901 писал(а):

Это зависит от МТ. Для стандартной это либо $0$ либо $1$, для рандомизированной - видимо, эта вероятность может быть как минимум произвольным перечислимым снизу числом.

Хорошо, вот описание конкретной МТ, на вход подается $k$ (номер разряда):
Она вычисляет $k$-тый разряд двоичной записи $\pi$ после запятой (0 или 1 соответно) обычным образом, пусть будет $b_k$. Что потом, зависит от того если $k = 0 \pmod{3}$. Если $k \ne 0 \pmod{3}$ то выдает то что и получила т.е. $b_k$. Если $k = 0 \pmod{3}$, то подкидывает монетку - если решка выдает $b_k$, если орел то инвертирует и выдает $\tilde{b_k}$.
Короче, каждый третий разряд с 50% вероятностью правилен (а все остальные точно правильны).
Теперь-то можно сказать, численно "с какой вероятностью эта рандомизированная МТ вычисляет последовательности двоичной записи разрядов $\pi$ после запятой"? И сколько будет эта вероятность, и почему?

mihaild в сообщении #1568901 писал(а):

Для стандартной - очевидно, $0$. Для рандомизированной - тоже $0$,

А можно конкретный пример (или ссылку на него) где вероятность "вычислить конкретную последовательность" не 0 и не 1, а например 0.20?

-- 04.11.2022, 15:43 --

warlock66613 в сообщении #1568904 писал(а):

Именно так. При этом неквантовые генераторы случайных чисел в этом контексте причисляются к "истинно случайным".

Можно конкретный пример что конкретно и кем считается "неквантовым генератором", и кем такие "неквантовые генераторы" причисляются к "истинно случайным"?

[mihaild]

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

"Вычисляет" (двоичную) последовательность в следующем смысле: на вход подается любой натуральный номер $k$ разряда последовательности, за конечное время она выдает значение разряда, 0 или 1.

Но ведь выдаст или нет, и что именно выдаст, зависит от бросков монетки. Т.е. вы сфорулировали нормальное определение "рандомизированная МТ вычисляет данную последовательность при таком-то случайном входе". Но всё еще непонятно, что значит "рандомизированная МТ вычисляет данную последовательность" (без фиксации входа).

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

Приведите классическое определение которым вы пользуетесь, по которому считается что стандартная (не "рандомизированная") МТ вычисляет какую-то последовательность.

Стандартная МТ вычисляет последовательность $x$, если для любого натурального числа $i$ существует протокол вычисления этой МТ на входе $i$, заканчивающийся $x_i$-м символом этой последовательности. Легко показать, что любая детерменированная МТ вычисляет не более одной последовательности.
Для рандомизированной МТ сюда надо еще куда-то впихнуть случайность.

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

Теперь-то можно сказать, численно "с какой вероятностью эта рандомизированная МТ вычисляет последовательности двоичной записи разрядов $\pi$ после запятой"?

С нулевой, естественно. Потому что вероятность того, что за бесконечное число бросков ни разу не выпадет орел, равна нулю.

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

А можно конкретный пример (или ссылку на него) где вероятность "вычислить конкретную последовательность" не 0 и не 1, а например 0.20?

Бросаем монетку, записываем результат как двоичное число, рано или поздно с вероятностью $1$ понимаем, больше это число $0.2$ или меньше. Если больше - зависаем, если меньше - выдаем ответ какой нужно.

[manul91]

mihaild в сообщении #1568907 писал(а):

Но ведь выдаст или нет, и что именно выдаст, зависит от бросков монетки

Всегда выдаст, для любого $k$ на входе - это следует из определения как "штукенция Х" работает.

mihaild в сообщении #1568907 писал(а):

Т.е. вы сфорулировали нормальное определение "рандомизированная МТ вычисляет данную последовательность при таком-то случайном входе".

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

mihaild в сообщении #1568907 писал(а):

Но всё еще непонятно, что значит "рандомизированная МТ вычисляет данную последовательность" (без фиксации входа).

Что за "фиксация входа"? Что значит "без фиксации входа", "с фиксации входа"? Стандартная МТ вычисляет последовательность "с фиксации входа" или "без фиксации входа"?

mihaild в сообщении #1568907 писал(а):

Стандартная МТ вычисляет последовательность $x$, если для любого натурального числа $i$ существует протокол вычисления этой МТ на входе $i$, заканчивающийся $x_i$-м символом этой последовательности. Легко показать, что любая детерменированная МТ вычисляет не более одной последовательности.
Для рандомизированной МТ сюда надо еще куда-то впихнуть случайность.

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

mihaild в сообщении #1568907 писал(а):

Бросаем монетку, записываем результат как двоичное число, рано или поздно с вероятностью $1$ понимаем, больше это число $0.2$ или меньше.

Как это..? Бросаем монетку - выпала решка, записываем как "двоичное число" например 1 (пусть решка это 1, орел это 0). Оно (1) больше $0.2$ и мы это сразу "понимаем", почему чтобы "понять" нужно ждать и чего? : ) В общем ничего не понял :((

[mihaild]

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

Перечитайте определение работы "штуковины Х" которое я расписал в деталях в прежних сообщений.

И там я не понял, вы хотите говорить о физическом устройстве, или о математической модели.
Модель у вас недоопределена. А физическое устройство нереализуемо.

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

Что значит "без фиксации входа", "с фиксации входа"?

Перечитайте предложение перед тем, которое вы цитируете:)
Я понимаю, как по рандомизированной МТ построить частичную функцию $\{0, 1\}^\mahtbb N \times \mathbb N \to \{0, 1\}$. Я не понимаю, как по ней построить функцию $\mathbb N \to \{0, 1\}$ (последовательность).

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

Как это..? Бросаем монетку - выпала решка, записываем как "двоичное число" например 1 (пусть решка это 1, орел это 0).

После запятой записываем.
Пусть решка это $1$, орел это $0$, $a_i$ - результат $i$-го броска. Тогда, если после $n$ бросков, $\sum_{i=1}^n a_i 2^{-i} > 0.2$, то зависаем, если $\sum_{i=1}^n a_i 2^{-i} + 2^{-n-1} < 0.2$, то выдаем ответ, иначе бросаем опять.