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

[manul91]

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

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

Будем считать, что о математической модели, чтобы избежать ненужных терминологически-философских споров.

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

Модель у вас недоопределена.

Что в ней "недоопределено"? Скажите прямо и конкретно.
Вот например, вы подаете на вход 17. "Штукенция Х" смотрит на свою ленту (память) записано ли там что-то навстречу 17 (есть ли запись типа 17->0, или 17->1). Это тривиальная конечная операция, может быть выполнена на стандартной МТ. Если найдет запись, то выдает соответное значение (0 или 1). Если не найдет, подбрасывает монетку, записывает результат на ленту (например 17->0 если выпала решка, пусть решка это 0) - это опять тривиальная конечная операция выполняемая на стандартной МТ; и выдает результат (0).
Что в этом "протоколе действий" "недоопределено", и в каком смысле?

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

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

Я не понимаю, о чем вы говорите. Причем тут $\{0, 1\}^\mahtbb N \times \mathbb N \to \{0, 1\}$ вообще?
Как "штукенция Х" строит соответствие $\mathbb N \to \{0, 1\}$ я объяснял несколько раз. Что именно там непонятно? Если нужно, распишу еще раз.
Далее вы говорите, что вы понимаете что-то, про "рандомизированных МТ". Я же говорю про "штукенции Х". На вопрос причисляете ли вы "штукенции Х" к тем что вы называете "рандомизированных МТ" или нет, вы не ответили. Поэтому даже если я бы понимал о чем вы говорите, то возможно мы говорим про разных вещей.
Потом, вы пишете "Я не понимаю, как по ней построить функцию $\mathbb N \to \{0, 1\}$ (последовательность)". Что для вас значит "понимать как построить функцию(последовательность)", тем более если если функция(последовательность) о которой речь невычислима? В определенном (конструктивном) смысле никакую невычислимую последовательность нельзя "понять" как она строится.

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

Пусть решка это $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$, то выдаем ответ, иначе бросаем опять.

Очень странно, если алгоритм будет (иногда, или всегда) зависать на каких-то входов то разве можно говорить что он якобы "производит какое-либо вычисление"? Далее, какую именно "последовательность" мы "вычислили" таким образом, "с вероятностью 0.2?". Если я правильно понял как это работает (на входе $n$, мы всегда выполняем $n$ бросков чтобы решить зависнуть или выдать результат $n$-того броска), то оно будет выдавать (не зависать на) целого класса последовательностей...(всех тех у которых бинарная запись после запятой <0.2)

[mihaild]

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

Что в ней "недоопределено"?

Не определено, что это вообще такое. Функция? Способ описания? Еще что-то?
Стандартная МТ - это кортеж из примерно 5 элементов, и ей легко сопоставить частичную функцию из натуральных чисел в натуральные числа. Рандомизированная МТ - это тоже кортеж из примерно 5 элементов, и ей легко сопоставить частичную функцию из пар (двоичная последовательность, натуральное число) в натуральные числа.
Всевозможные "принятия на вход", как правило, можно описать в таких или подобных терминах, но как это сделать в случае вашей "штукенции" - я не понимаю, поэтому сделайте это, пожалуйста.

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

Что для вас значит "понимать как построить функцию(последовательность)", тем более если если функция(последовательность) о которой речь невычислима?

Это значит дать более-менее строгое определение.

Вы просили пример

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

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

Ну вот описанный выше алгоритм (если в нём "выдаем ответ" заменить на "выписываем последовательность из одних нулей") с вероятностью $1/5$ вычисляет последовательность из одних нулей (а с вероятностью $4/5$ зависает).

[warlock66613]

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

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

Пример:

RFC 1750: Randomness Recommendations for Security писал(а):

A thermal noise or radioactive decay source and a fast, free-running oscillator would do the trick directly [GIFFORD]. This is a trivial amount of hardware, and could easily be included as a standard part of a computer system's architecture. Furthermore, any system with a spinning disk or the like has an adequate source of randomness [DAVIS].

[manul91]

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

Не определено, что это вообще такое. Функция? Способ описания? Еще что-то?
Стандартная МТ - это кортеж из примерно 5 элементов, и ей легко сопоставить частичную функцию из натуральных чисел в натуральные числа. Рандомизированная МТ - это тоже кортеж из примерно 5 элементов, и ей легко сопоставить частичную функцию из пар (двоичная последовательность, натуральное число) в натуральные числа.

Не только кортеж. Там есть еще и "бесконечная лента" с которой можно считывать/записывать значения. Это существенно для "интерпретации" как будет "действовать" кортеж как таблица переходов, и как соответно "производится вычисление".
Но в общем понятно какой уровень нужен.
Итак, "штукенцию Х" можно описать кортежем из "примерно 7-ми" элементов (на двух больше), на тот же самый маньер как стандартную МТ.
Почему на два елемента бОльше: будем считать, что у нее одна лента больше, чем у стандартной МТ. На первую ленту записывается вход (иначе она пуста), после того как машина "пошуршит", на той же ленты вход стерт и выдан результат. "Вторая лента" у нее "постоянная память", там она хранит что нужно между итераций.
Остался "источник случайности". Его можно включить в описание самой машиной (в кортеже таблицы переходов) наподобие как у недетерминированной МТ (на самом деле везде вероятности перехода будут 1, только в одном месте вероятности будут 0.5, с одном состоянии к двух разных состояний). Или, альтернативно, если так вам больше нравится, можете считать что у нее есть еще одна (третья) лента на которой записана наперед некая случайная двоичная последовательность; из этой этой ленте головка может только читать а не записывать (и никогда не возвращаясь к "прежней клетки" на которой уже была).
Поэтому, кортеж описываюший такой машины на 2 елемента больше чем стандартной МТ.
Такой уровень описания годится?

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

Ну вот описанный выше алгоритм (если в нём "выдаем ответ" заменить на "выписываем последовательность из одних нулей") с вероятностью $1/5$ вычисляет последовательность из одних нулей (а с вероятностью $4/5$ зависает).

Э нет... . Когда говорим что "стандартная МТ вычисляет последовательность" - то НЕ имеется ввиду, что она начинает выписывать какую-то бесконечную последовательность, не останавливаясь:)
Имеется ввиду, что она получая конкретное нат. число на входе (номер разряда), выдает конкретное нат. число на выходе - его значение (в данном случае 0 или 1 чтобы проще) и останавливается.
Поэтому я вообще не понимаю в каком смысле ваша машина выдает "бесконечную последовательность из одних нулей", с "вероятностью 0.2", и это считается "вычислением"? (тем более что она может зависать на входов)
И да, бинарная запись 0.2 это периодическая последовательность .001100110011... ; так что неясно почему ваша машина будет "вычислять" именно .00000000.... (последовательность из одних нулей) а не например, последовательность .001100000(дальше одни нули)... которая тоже меньше 0.2.

-- 04.11.2022, 18:16 --

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

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

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

Пример:

RFC 1750: Randomness Recommendations for Security писал(а):

A thermal noise or radioactive decay source and a fast, free-running oscillator would do the trick directly [GIFFORD]. This is a trivial amount of hardware, and could easily be included as a standard part of a computer system's architecture. Furthermore, any system with a spinning disk or the like has an adequate source of randomness [DAVIS].

И что, "thermal noise", "radioactive decay source" - это "неквантовый генератор"?
Это шутка такая?

[warlock66613]

manul91, проблема с вашей "конструкцией", что она — чтобы быть использованной повторно — требует бесконечной памяти. И не во время работы, как машина Тьюринга, а между запусками. То есть это совсем не рандомизированная машина Тьюринга, а что-то иное.

-- 04.11.2022, 18:19 --

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

И что, "thermal noise", "radioactive decay source" - это "неквантовый генератор"?

А что, там больше ничего в списке нет?

[mihaild]

Ой, я думал, вы знаете определение МТ.
Никакой бесконечной ленты в определении МТ нет, она появляется при определении, какую функцию МТ вычисляет.
Напишу нужный тут частный случай подробнее.
МТ с одной односторонне-бесконечной входной лентой и одной входной-рабочей, в алфавите $\{0, 1\}$ - это кортеж из четырех элементов, $(A, q_0, q_1, f)$, где $A$ - алфавит состояний, $q_0, q_1 \in A$ - начальное и конечные состояния, $f$ - функция перехода $(A \setminus \{q_1\}) \times \mathbb \{0, 1\} \times \mathbb \{0, 1, \#\} \to A \times \{0, 1, \#\} \times \{L, R, S\} \times \{L, R, S\}$ (если находимся в таком-то состоянии и видим такие-то символы на первой и второй ленте, то переходим в такое-то состояние, записываем на рабочую ленту такое-то значение, и сдвигаемся по каждой ленте куда-то). Состоянием такой МТ называется набор $(x, s, a, i, j)$, где $x$ - бесконечное двоичное слово, $s$ бесконечное слово в алфавите $\{0, 1, \#\}$, в котором лишь конечное число нулей и единиц, $i$ и $j$ - натуральные числа, $a \in A$.
Протоколом вычисления МТ на последовательности $x$ и входе $t$ называется последовательность состояний, начинающихся с $(x, t\#\#\ldots, q_0, 0, 0)$ и заканчивающаяся состоянием вида $(x, t'\#\#\ldots, q_1, 0, 0)$, где $t'$ не содержит $\#$, и где каждое следующее состояние получается из предыдущего с помощью функции перехода (надо писать, как?).
Доказывается, что если протокол вычисления МТ для данных $x$ и $t$ существует, то он единственный. Соответствующее $t'$ называется результатом работы МТ.

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

Когда говорим что "стандартная МТ вычисляет последовательность" - то НЕ имеется ввиду, что она начинает выписывать какую-то бесконечную последовательность, не останавливаясь

Есть два разных эквивалентных определения. Но давайте действительно возьмем с выписыванием одного запрошенного бита, чтобы не скакать.
Тогда выше нужно посмотреть на ленту со случайным входом, как описано, но если оказалось, что число на ней меньше $1/5$, то выписать $0$ и остановиться.

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

И да, бинарная запись 0.2 это периодическая последовательность .001100110011... ; так что неясно почему ваша машина будет "вычислять" именно .00000000

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

[manul91]

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

manul91, проблема с вашей "конструкцией", что она — чтобы быть использованной повторно — требует бесконечной памяти.

Что значит "быть использованной повторно"? Как я вижу вещи, в любом моменте времени она требует только конечную память.

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

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

Да, кажется вы тут нащупали самую суть! Я согласен. Стандартная МТ (как и недетерминированная МТ) не предполагают "сохранение памяти" между запусками, у них всегда в начале лента пустая (кроме входа который на ней записан). Про "рандомизированную МТ" не уверен, надо почитать определение, но наверное также.
Ну и что-ж. Пусть моя "конструкция X" не является ни одной из этих моделей. Но эти же модели не с неба упали, их выдумали люди (как и многолентовые МТ, и квантовые МТ и т.д.). Так что будем ее считать "новой моделью":)
Итак, слова "случайность ничего не дает в плане вычислимости" будут верными если подразумевать только те модели, но не и модели "конструкции Х" которая "дает" что-то в плане вычислимости.
Либо нужно произнести заклинание что то, что "Х может определять невычислимую последовательность" - "не считается чем-то", "в плане вычислимости".

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

А что, там больше ничего в списке нет?

Вы про "spinning disk or the like has an adequate source of randomness"? Слово "adequate" здесь используется в мутном смысле "достаточно хороший"... что далеко от "истинной случайности", и можно с тем же успехом так говорить и про каким-то стандартным навороченным ГПСЧ;)

-- 04.11.2022, 19:12 --

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

Никакой бесконечной ленты в определении МТ нет, она появляется при определении, какую функцию МТ вычисляет.

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

МТ с одной односторонне-бесконечной входной лентой и одной входной-рабочей, в алфавите $\{0, 1\}$ - это кортеж из четырех элементов, $(A, q_0, q_1, f)$, где $A$ - алфавит состояний, $q_0, q_1 \in A$ - начальное и конечные состояния, $f$ - функция перехода $(A \setminus \{q_1\}) \times \mathbb \{0, 1\} \times \mathbb \{0, 1, \#\} \to A \times \{0, 1, \#\} \times \{L, R, S\} \times \{L, R, S\}$ (если находимся в таком-то состоянии и видим такие-то символы на первой и второй ленте,

Интересно, если "ленты нет в определении", то как так ссылки на ленты (что они такое, как пользуются чтобы выделить соответный инстанс кортежа, что значат элементы кортежа и т.д.) возникли все-таки в вашем определении? Или, это еще не определение? : )

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

Но давайте действительно возьмем с выписыванием одного запрошенного бита, чтобы не скакать.
Тогда выше нужно посмотреть на ленту со случайным входом, как описано, но если оказалось, что число на ней меньше $1/5$, то выписать $0$ и остановиться.

Давайте. Я запросил 17-тый бит последовательности, машина посмотрела свою случайную ленту, число оказалось меньше $1/5$, она выписала $0$ и остановилась. Запросил 12-тый бит последовательности, она сделала то же самое с той же ленте, и опять в итоге $0$. И какую последовательность "вычислила" эта машина? Бесконечную последовательность нулями? Эти машины могут вообще значения разрядов каких-либо других последовательностей вычислять, кроме строго нулевыми? Это вообще, "не то".
У вас короче, вроде просто "девайс" который с определенную вероятность зацикливается, с определенную нет (и пишет ноль), вероятность зацикливания он берет из "случайной ленте" (можно ее считать источником "случайного числа" в интервале $(0,1)$). Это вроде вообще не то, чтобы "вычислять какую-то последовательность", в каком нибудь смысле (тем менее в смысле выше).

[mihaild]

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

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

То, что идет до слова "это" - не определение, а название:)

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

Эти машины могут вообще значения разрядов каких-либо других последовательностей вычислять, кроме строго нулевыми?

Не "эти машины", а "эта машина". Я привел описание конкретной МТ. Которая с вероятностью $1/5$ вычисляет последовательность из одних нулей, и с вероятностью $4/5$ не вычисляет ничего.

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

Это вроде вообще не то, чтобы "вычислять какую-то последовательность", в каком нибудь смысле

Это ровно оно и есть.
Скажем, что МТ $T$ (удовлетворяющая определению выше) вычисляет последовательность $r$ при случайном входе $x$, если результат её работы на последовательности $x$ и входе $[i]$ (двоичная запись числа $i$) равен $r_i$. Можно показать, что множество таких бесконечных двоичных последовательностей, что МТ на них вычисляет последовательность $r$, измеримо. Ну и вероятность этого множества естественно назвать вероятностью того, что МТ вычисляет эту последовательность.

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

Пусть моя "конструкция X" не является ни одной из этих моделей. Но эти же модели не с неба упали, их выдумали люди (как и многолентовые МТ, и квантовые МТ и т.д.). Так что будем ее считать "новой моделью"

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

-- 04.11.2022, 17:04 --

(сначала не совсем правильно распарсил вопрос)

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

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

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

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

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

[warlock66613]

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

можно с тем же успехом так говорить и про каким-то стандартным навороченным ГПСЧ;)

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

[Vozduh]

А причем здесь измеримость ? И, вообще, теория меры ?
Здесь же просто множества рассматриваются, еще до всяких..

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

Ой, я думал, вы знаете определение МТ.

Я тоже думал, что знаю. Оказалось, что определение излишне гибкое.

[Vozduh]

Почему, вдруг, Вы решили ввести на этих множествах меру ?

[mihaild]

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