Вероятностная машина на бесконечности

[Alex_semenov]

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

Известно, что классы задач, решаемые детерминированными машинами Тьюринга (ДМТ), недетерминированными (НДМТ) и вероятностными (ВМТ) совпадают. То есть любая решаемая одним типом машин задача решается и машинами двух других типов. Если задача не решается каким-то типом, то и любые два других типа ее решить не могут.

Доказывается это так. Во-первых. Так как НДМТ и ВМТ есть расширение ДМТ (ДМТ есть частный случай двух других), то, очевидно, что любая задача, решаемая ДМТ, решается на НДМТ и ВМТ.
Во-вторых. Возьмем произвольную ВМТ. Существует эквивалентная ей НДМТ, которая на шаге, где ВМТ делает случайный выбор между $n$ альтернативами, разделяется на $n$ "клонов". В итоге, когда ВМТ остановится один из "клонов" НДМТ тоже остановится. То есть любая задача вычислимая на ВМТ вычислима, на НДМТ.
Теперь вспомним, что любая НДМТ эмулируется некоторой ДМТ. Отсюда, если остановилась ВМТ, то остановится и ДМТ, эмулирующая эквивалентную той НДМТ. То есть, если задача вычисляется на некоторой ВМТ, то она вычисляется на некоторой ДМТ. Таким образом, вычислительная эквивалентность ДМТ, НДМТ и ВМТ очевидна.

Но что случиться, если число шагов вычислений будет не конечным а бесконечным? Рассмотрим простейшую ВМТ, которая печатает бесконечную последовательность совершенно случайных единиц и нулей:

100101011000010101010111010100001010…

Если мы начнем эмулировать на ДМТ эквивалентную такой ВМТ НДМТ, то каждый шаг ВМТ приведет к удвоению виртуальных "клонов" НДМТ. На $n$-том шаге ВМТ, ДМТ должна эмулировать $2^{n}$ виртуальных "клонов". И в случае бесконечного числа шагов ВМТ для ДМТ мы приходим к "кардинальному парадоксу". Чтобы вычислить столько же нулей и единиц что и ВМТ, ДМТ должна эмулировать континуум, ($2^{\infty }=\mathfrak{c}$), "клонов" эквивалентной НДМТ. Но у ленты ДМТ, даже актуально бесконечной, не может быть более чем счетного числа ячеек, $\aleph_{0}$. То есть на бесконечности все клоны "не поместятся" на ленту ДМТ. Принцип эквивалентности машин нарушается.
Значит, должны существовать такие бесконечные задачи, которые вычислимые на ВМТ но не вычислимые на ДМТ

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

Прежде всего, почему такая задача не вычислима на ДМТ диагональным методом Кантора? Потому что существует Проблема Остановки. Мы можем, опираясь на универсальную МТ, $U(i,n)$, в лексикографическом порядке перечислить все программы $p_{i}(n)$, вычисляющие все вычислимые функции типа $p: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$ и значит теоретически можем выстроить бесконечную вправо и вниз таблицу всех вычислимых бесконечных цепочек из единиц и нулей. Но мы не можем "взять" из этой таблицы диагональ и инвертировать ее $\neg U( n, n)=\neg p_{n}(n)$ методом Кантора, потому что некоторые $p_{n}$ на некоторых $n$ невычислимые и мы не можем механически это узнать (Проблема Остановки). В итоге у выстраиваемой анти-диагонали на такой $n$-той позиции надо поставить $1$, но в этой "дырке" таблицы, анти-диагональ в лучшем случае тоже будет иметь "дырку" и таким образом идея воспользоваться диагональным методом Кантора терпит неудачу.
Невычислимое остается невычислимым.
Однако, то же самое можно "попробовать" вычислить иначе, подбрасывая "честную монету" бесконечное число раз. То есть с помощью простейшей ВМТ.
Пускай, мы собираемся подбросить монету $n$ раз. Существует $2^{n}$ равновероятных исходов ожидаемого события. Если вы имеете цепочку-образец из нулей и единиц длиной $n$, то вероятность того, что случайная последовательность совпадет с образцом $P=2^{-n}$. Если вы имеете $m$ несовпадающих друг с другом таких образцов, то вероятность того, что какая-то из этих цепочка совпадает со случайной, возрастает в $m$ раз: $P=m 2^{-n}$. При этом $m\leqslant 2^{n}$, иначе условие уникальности каждого из образцов соблюсти не получится. Но в любом случае:

$P=\left\{\begin{matrix}m 2^{-n}&, m \leqslant 2^{n}\\ 1 &, m> 2^{n}\end{matrix}\right\ }\ $

Если теперь $m$ приять равным $n$ и устремит к бесконечности, то вероятность того, что в выстроенной бесконечной вниз таблице из уникальных бесконечных вправо бинарных цепочек встретиться наша бесконечная случайная цепочка, так же устремиться к $0$:

$P_{\infty }=\lim\limits_{n \to \infty } n {2^{-n}}=0$

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

$P_{\infty }=\lim\limits_{^{m \to 2^{\infty}}_{n \to \infty }} m {2^{-n}}=\frac{2^{n}}{2^{n}}=1$

Но $m$ - число строк бесконечной таблицы, и оно не может стремиться к $2^{\infty}$, так как это континуум. Бесконечная таблица - дискретная структура как и лента МТ. Строк в ней может быть только счетная бесконечность.
Получается что ВМТ может построить "вероятностную диагональ" которую невозможно построить с помощью ДМT.
"Залог успеха" ВМТ - несопоставимость мощности континуума и счетной бесконечности. Рассмотрим такую наглядную геометрическую аналогию. Имеется площадь $S$, внутри которой выделена некоторая площадь $s'$. На $S$ равновероятно падает точка. Вероятность того, что точка попадет в область $s'$ равна отношению площадей: $P =s'/S$. Если площадь $s'$ сжать в точку, то вероятность попадания точкой в точку:

$P=\lim\limits _{s'\rightarrow 0 }\frac{s'}{S}=0$

Это невозможное событие. Непопадание - достоверное.
Чуть иная ситуация. По площади $S$ разбросано бесконечное, но счетное множество точек. Какова вероятность того что случайно брошенная точка попадет в одну ин них?
Предположим, что вероятность этого больше $0$. Это возможно, если суммарная площадь всех точек $s' >0$. Но это же означало бы, что $s'$ содержит континуум точек, что противоречит условию. То есть, вероятности попасть точкой в какую-то точку бесконечного, но счетного множества точек на $S$ тоже равна нулю. Этот пример - геометрическая аналогия рассуждений о вычислении на ВМТ невычислимого на ДМТ.
______________

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

A-G-T-С-G-A-….-G-A-T

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

[Someone]

Alex_semenov в сообщении #563448 писал(а):

Но что случиться, если число шагов вычислений будет не конечным а бесконечным?

Мы никогда не дождёмся конца этих вычислений, так что ничего интересного не увидим.

[Alex_semenov]

Someone в сообщении #563462 писал(а):

Alex_semenov в сообщении #563448 писал(а):

Но что случиться, если число шагов вычислений будет не конечным а бесконечным?

Мы никогда не дождёмся конца этих вычислений, так что ничего интересного не увидим.

Вы считаете, что в подобных рассуждениях о машинах недопустима актуализация бесконечности?
Гм…
Понятно, что с бесконечностью надо быть осторожным. Очень рекомендуется не использовать актуальную там, где можно использовать потенциальную, и не использовать потенциальную там, где можно обойтись без бесконечности вообще. "От греха подальше". Но это ведь чисто методологический совет, не более.
В данном случае без актуализации никак не обойтись. Вопрос лишь в том, насколько корректно она здесь проведена?
Мне казалось, что со времен Кантора актуализация бесконечности должна вызывать куда меньше сомнений. В конце концов, оставим Кантора в покое и давайте возьмем пример проще. Сумма бесконечного ряда:

$1/2+1/4+1/8+ . . .+1/2^{n}+. . . =1$



Мы никогда не дождемся конца этого ряда, поэтому "ничего интересного не увидим"? Не можем судить о его сумме?
Почему в случае бесконечно работающей ВМТ и ДМТ мы не можем позволить себе подобное заключение, если оно сделана корректно?
Что значит "корректно"?
Если подобный прием не ведет к противоречию с уже установленным в математике (говоря по простонародному). На ноль делить нельзя не потому что кто-то запретил нам это делать в третьем классе, а потому что это ведет к выводам типа 2=3, то есть к противоривости так некорректно расширенной системы аксиом.

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

[epros]

Alex_semenov в сообщении #563668 писал(а):

Сумма бесконечного ряда:

$1/2+1/4+1/8+ . . .+1/2^{n}+. . . =1$

…

Мы никогда не дождемся конца этого ряда, поэтому "ничего интересного не увидим"?

Как Вы определяете, что «задача решена»? Я вижу несколько возможных вариантов:

1) Добавлено последнее слагаемое - в этом случае задача никогда не будет решена.
2) Очередное слагаемое оказалось меньше заданной величины - в этом случае задача будет решена, но решение не будет доказывать, что сумма ряда равна единице.
3) Задача считается решенной только тогда, когда доказано существование и найдено значение предела суммы - будет решена задача или нет зависит от схемы доказательства существования предела, которую Вы заложите в решающий алгоритм.
4) Ещё варианты?

[Someone]

Alex_semenov в сообщении #563668 писал(а):

Сумма бесконечного ряда:

$1/2+1/4+1/8+ . . .+1/2^{n}+. . . =1$

...

Мы никогда не дождемся конца этого ряда, поэтому "ничего интересного не увидим"? Не можем судить о его сумме?

А мы для вычисления суммы ряда не будем "дожидаться конца". Мы вычислим $n$-ную частичную сумму ряда

$$S_n=\frac 12+\frac 1{2^2}+\frac 1{2^3}+\ldots+\frac 1{2^n}=1-\frac 1{2^n}$$

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

$$S=\lim\limits_{n\to\infty}S_n=\lim\limits_{n\to\infty}\left(1-\frac 1{2^n}\right)=1.$$

Если Вы думаете, что для вычисления предела нужно "пройти последовательность до конца", то Вы тоже заблуждаетесь. Есть определение предела последовательности, оно вполне себе конечно и для своего использования требует конечной последовательности рассуждений.

Alex_semenov в сообщении #563668 писал(а):

Вы считаете, что в подобных рассуждениях о машинах недопустима актуализация бесконечности?

Причём здесь машины? В математике вообще нет никаких бесконечных текстов, формул или рассуждений. Всё конечно, и любое доказательство должно быть конечным текстом.

Alex_semenov в сообщении #563668 писал(а):

На ноль делить нельзя не потому что кто-то запретил нам это делать в третьем классе, а потому что это ведет к выводам типа 2=3, то есть к противоривости так некорректно расширенной системы аксиом.

Ерунду пишете. Если Вам позарез хочется делить на ноль - делите, только сначала внятно определите эту операцию. Упомянутые Вами противоречивые "выводы" получаются не потому, что поделили на ноль, а потому, что эту операцию предварительно не определили. Использование не определённой операции даёт неопределённый результат, которому в одном случае было приписано одно значение, а в другом - другое, что и привело к противоречию.

Alex_semenov в сообщении #563668 писал(а):

Но если мы запустим детерминированную машину Зенона на эмуляцию бесконечной ВМТ, то дождемся таки за конечное время того, о чем я говорю. "Увидим" нечто интересное.

Здесь такая же ситуация: результат работы этой самой "машины Зенона" не определён. Сначала определите, что Вы будете понимать под результатом, а потом пользуйтесь на здоровье. Но Ваше определение будет конечным и не будет требовать "прохождения до конца".

[Alex_semenov]

Someone в сообщении #563710 писал(а):

Сначала определите, что Вы будете понимать под результатом, а потом пользуйтесь на здоровье. Но Ваше определение будет конечным и не будет требовать "прохождения до конца".

То есть, для начала надо четко определить понятие бесконечного вычисления.
Какие-то яркие примеры "не катят". Надо четко (конструктивно?) определить что считается результатом такого вычисления, чем такое вычисление отличается от "простого" зацикливания и т.д. Да так, чтобы такие "размытые" термины как "бесконечность" там не фигурировали.
Так?
Гм…
Буду думать.
Вы только вот что мне подскажите.
Мы хотим сказать: "машина на данном входе вошла в бесконечный цикл". То есть "зациклилась". Обычная "классическая" ситуация. Как этот факт строго определить так как вы говорите, чтобы не требовалось "прохождение до конца"?

[muzeum]

Забудем на время, что автору темы не удалось сформулировать понятие бесконечно долго работающей машины (не важно детерминированной или нет).
Отметим только одно:

Цитата:

"Залог успеха" ВМТ - несопоставимость мощности континуума и счетной бесконечности.

- это еще не означает, что ДМТ не может эмулировать работу ВМТ. Для записи континуума возможных исходов вполне хватает счетного числа символов. Так бинарное дерево содержит запись всех двоичных последовательностей (из нулей и единиц).
Другое дело, что проблему "останова" автор темы трактует только как основу получения старого результата Черча, а между тем это скорее проблема определения процесса вычисления: надо указать, что именно является результатом такого процесса. Можно предложить (кажется автор это и имел ввиду), что по совершении бесконечного числа шагов наступает шаг $\omega$, на котором автоматически устанавливается конечное состояние. Это означает, что принадлежность бесконечной последовательности множеству результатов устанавливается путем проверок ее начальных конечных отрезков, что позволяет строить детерминированную машину, которая за бесконечное время нарисует дерево исходов недетерминированной машины. Если же на шаге $\omega$ проверяется принадлежность уже выписанной бесконечной последовательности к некоторому заданному заранее множеству А, то здесь вопрос уже не о бесконечном времени.

[vicvolf]

Alex_semenov в сообщении #563810 писал(а):

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

Ошибка в алгоритме. Если нет ошибки в алгоритме, то такого быть не должно!

[hurtsy]

vicvolf в сообщении #564167 писал(а):

Если нет ошибки в алгоритме, то такого быть не должно!

Бесконечные циклы, т.е. переменная цикла может быть неограниченной бывают, только в таком цикле должна быть хотя бы одна команда

break;

. Можете не верить , но такое бывает. С уважением,

[epros]

Alex_semenov в сообщении #563810 писал(а):

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

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

Но в частном случае, когда речь идёт о сумме ряда, доказательство того, что процесс суммирования не остановится, тривиально.

[vicvolf]

hurtsy в сообщении #564268 писал(а):

vicvolf в сообщении #564167 писал(а):

Если нет ошибки в алгоритме, то такого быть не должно!

Бесконечные циклы, т.е. переменная цикла может быть неограниченной бывают, только в таком цикле должна быть хотя бы одна команда

break;

. Можете не верить , но такое бывает. С уважением,

Конечно бывает! Например, ранее в ЭВМ была команда безусловного перехода сама на себя. Использовалась для ожидания прерывания от какого либо внешнего устройства. Но все равно этот цикл заканчивался получением и отработкой прерывания!

[Alex_semenov]

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

Alex_semenov в сообщении #563810 писал(а):

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

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

Разумеется.
Но вы слишком широко трактуете мой вопрос.
Я говорил о любом совершенно конкретном примере. "Тривиальном"
Если, например, мы подадим $0$ машине которая считает $y=x-1$, она не остановится.
Как строго записать этот факт? "Не остановится". Именно для этой конкретной машины. У математики УЖЕ есть средства это выразить?

Как я понимаю ваше требование устрожить рассуждения?
Например, факт того, что множество простых чисел бесконечно, нельзя объявить используя термин или значок "бесконечно". Надо это сделать как-то финитно, конструктивно. Идеально утверждение "существует бесконечное множество простых чисел" надо записать так:

$\forall a:\exists b: \neg\exists c:\exists d: (a+Sb)=(SSc\cdot SSd)$

Для всякого числа $a$, существует число $b$ такое, что… и так далее. Это еще древние греки изобрели. Просто до кванторов не додумались. Как по мне, "избавление" от бесконечности тут чем-то похоже на "уборку" методом заметания пыли под кровать. Мы спрятали, "замели" ее под кванторы "для всякого", "существует". Но бесспорно то, что мы ЧЕТКО, формально выразили мысль, не допуская двузначных интерпретаций (и семантической противоречивости). У нас есть конечная цепочка символов однозначно выражающая ранее "мутную" мысль: "простых чисел бесконечно много".

Как я понимаю вставшую передо мной проблему? В теории алгоритмов до сих пор зацикливание ВСЕГДА обозначало невычислимость. Поэтому в учебниках всегда говорится "человеческим языком": "зациклится", "уйдет в бесконечный цикл". Никому в голову не приходит уточнять что это такое. Нет смысла. Это однозначно ясно всем. Успенский на некоторых своих лекциях (выложенных в сети) наотрез отказывается строго определять даже что такое алгоритм. Мол, и так всем давно уже ясно что это такое. Мол, слава богу, все работают с алгоритмами с детства и знают интуитивно о чем речь. Мол, формализация этого понятие занятие нудное и не будем тратить время.
Но!
В данном случае ситуация обратная. Я собрался РАЗЛИЧАТЬ виды зацикливаний. Правильно-зацикленную (вычислимую на бесконечности) и неправильно зацикленную программу (невычислимую… даже на бесконечности). Вы абсолютно правы. Если так, то нужно четко определиться с теремном "бесконечные вычисления". И первый шаг на этом пути (пока не важно увенчается ли он успехом) - начать с формализации достоверного, тривиального. Давайте для начала разберемся с термином "зацикливание" в обычной теории алгоритмов. Оставим в стороне мои мутные рассуждения.
Мы можем выразить термин "зациклилась" как-то так же как это вы требуете от моих сомнительных идей?
Давайте для начала возьмем совершенно тривиальный пример. Как более строго, через конечные понятия выразить что как-то описанная машина, считающая $y=x-1$ никогда не остановится, получив на вход $0$? Ведь ясно, что это как-то должна же делаться, раз зацикливание имеет место в классической теории алгоритмов.
Я, как нематематик, прошу у вас "козу", на тривиальном примере.
Насколько я понимаю, любая конкретная машина Тьюринга может быть описана в терминах формальной теории чисел и значит любое утверждение об этой машине может быть выражено как утверждение о натуральных числах. В том числе и утверждение о зацикливании конкретной машины на конкретном входе.
Как?
Должна быть ключевая идея. Как у древних греков с "заметанием" бесконечности под кванторы.