Вероятность остановки программы

[cscscs]

Известно, что проблема остановки неразрешима. Применение нормального алгоритма к слову даёт другое слово и, если был знак завершения, то конец, а если не было, то применяем алгоритм к полученному слову. Пусть $\{X_i\}$ - последовательность слов на каждом шаге работы программы. Очевидно, что если там $X_i=X_j$, то программа зациклится и мы это обнаружим за конечное число действий. Но может оказаться, что все $X_i$ попарно различны - это тот случай, когда мы не можем знать наверняка. Допустим, что мы просмотрели первые $N$ членов этой последовательности и все они оказались попарно различными. Какова вероятность (и можно ли её вообще посчитать), что при этом условии программа завершится? Задавался ли уже кто-нибудь этим вопросом?

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

tl;dr Можно ли написать программу, которая бы по произвольной проге и входной строке выдавала вероятность её остановки на данной строке?

[ИСН]

Как Вы собираетесь считать эту вероятность? Чему равно, например, среднее из 45 нулей, 40 единиц и 15 "не знаю"?

[cscscs]

ИСН в сообщении #826353 писал(а):

Как Вы собираетесь считать эту вероятность? Чему равно, например, среднее из 45 нулей, 40 единиц и 15 "не знаю"?

А причём тут "среднее из 45 нулей, 40 единиц и 15 "не знаю""? Как эту вероятность считать я не знаю. Поэтому и спрашиваю. Может $1/\log_2{(N+1)}$ (взял с потолка только ради примера; очевидно, что тут не только от $N$ зависимость). Может можно вообще аксиоматически задать.

[Xaositect]

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

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

[svv]

cscscs в сообщении #826352 писал(а):

это тот случай, когда мы не можем знать наверняка

Я думаю, что, по мнению cscscs, если мы не можем знать наверняка значение величины, значит, это случайная величина и она может рассматриваться с точки зрения теории вероятностей.

[cscscs]

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

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

Да, видимо это не будет вероятностью в классическом смысле.

А вообще, я понял, что важно ведь не только насколько сильно мы сжимает строку, но и сколько времени и памяти потребуется декомпрессору для того чтобы восстановить исходную строку, т.е. количество шагов выполнения $\{X_i\}$. Поэтому колмогоровская сложность (из-за которой мне собственно и стала интересна проблема остановки) $K(x)=\min_{py}\{l(py)|p(y)=x\}$ не совсем адекватна. Я придумал другую сложность $C(x)=\min_{py}\{l(py)\cdot s(py)|p(y)=x\}$, где $s(py)$ - количество шагов выполнения $p(y)$. Очевидно, что $C$ есть верхняя оценка $K$, т.е. $K(x)\le C(x)$. Известно, что $K(x)\le l(x)+c$, т.е. есть такое $p_0 y_0$ (которое всегда легко построить), что $l(p_0 y_0)=l(x)+c$. Т.о. мы получаем условие для поиска $l(py)\cdot s(py)<l(p_0 y_0)\cdot s(p_0 y_0)$. Мало того, что мы отсюда найдем конечные множества программ $P$ и слов $S$ для поиска, но ещё мы сможем избежать необходимости решения проблемы остановки, т.к. не нужно будет проверять остановится $p(y)$ или нет если число шагов её выполнения на данный момент превысило $l(p_0 y_0)\cdot s(p_0 y_0)$. Значит $C$ вычислимая функция.

[nikvic]

cscscs в сообщении #827529 писал(а):

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

...а также времени/памяти, чтобы найти "зип" строки

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

[cscscs]

nikvic в сообщении #827575 писал(а):

...а также времени/памяти, чтобы найти "зип" строки

Тут одно от другого зависит.
Мне непонятно почему колмогоровская сложность вообще не учитывает вычислительные ресурсы. Ведь если их принять во внимание, то, внезапно, сложность строки становится вычислимой. Вообще для меня понятие "невычислимая" все больше становится синонимом "бредовая".
На практике же вычислительные ресурсы всегда учитываются, как, например, вот в этом соревновании http://www.hutter1.net/prize/index.htm

[Sonic86]

cscscs в сообщении #827714 писал(а):

Мне непонятно почему колмогоровская сложность вообще не учитывает вычислительные ресурсы

По определению (не надо путать четкие термины и представления о реальных объектах)

cscscs в сообщении #827714 писал(а):

Ведь если их принять во внимание, то, внезапно, сложность строки становится вычислимой.

Не доказано. Нет доказательства - нет мультиков. И, кроме того, даже бессмысленно - для того, чтобы это увтерждение стало осмысленным, надо определить эту Вашу новую сложность, учитывающую вычислительные ресурсы. У Вас есть это определение? Без определения мультиков тоже нет. Вы имеете ввиду $C(x)$? Если да, то можете входящие подтермины определить или хотя бы пояснить, а то непонятно, о чем Вы говорите.

cscscs в сообщении #827714 писал(а):

Вообще для меня понятие "невычислимая" все больше становится синонимом "бредовая".

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

cscscs в сообщении #827529 писал(а):

$K(x)=\min_{py}\{l(py)|p(y)=x\}$

Здесь у Вас $l$ - длина, $y$ - какой-то аргумент (а откуда он? его в определении колмогоровской сложности нет), $p$ - текст программы, $x$ - строка, сложность которой считаем? В частности, Вы здесь не различаете функции и их программы (т.е. неявно предполагается, что язык программы фиксирован, кроме того, неявно предполагается, что можно для любых $p,y$ разделить конкатенацию $py$ на $p$ и $y$, что в общем случае неверно для произвольного языка).

cscscs в сообщении #827529 писал(а):

Т.о. мы получаем условие для поиска $l(py)\cdot s(py)<l(p_0 y_0)\cdot s(p_0 y_0)$.

Условие для чего?

cscscs в сообщении #827529 писал(а):

мы отсюда найдем конечные множества программ $P$ и слов $S$ для поиска

для какого поиска? Для поиска чего?

cscscs в сообщении #827529 писал(а):

но ещё мы сможем избежать необходимости решения проблемы остановки

тоже фараза непонятная. Откуда берется необходимость решения проблемы остановки? Заставили что-ли? Не хотите - не решайте, никто не заставляет.

[cscscs]

Sonic86 в сообщении #827733 писал(а):

Вы имеете ввиду $C(x)$?

Да. Только как пример.

Sonic86 в сообщении #827733 писал(а):

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

http://www.mccme.ru/free-books/shen/kolmbook.pdf См. определение колмогоровской сложности при данном способе описания $D$ на странице 9 и теорему 1 на 10 странице. Под колмогоровской сложностью я понимаю колмогоровскую сложность при данном способе описания $D$ как в теореме 1, т.е. $D(py)=p(y)$.

Sonic86 в сообщении #827733 писал(а):

Здесь у Вас $l$ - длина, $y$ - какой-то аргумент (а откуда он? его в определении колмогоровской сложности нет), $p$ - текст программы, $x$ - строка, сложность которой считаем? В частности, Вы здесь не различаете функции и их программы (т.е. неявно предполагается, что язык программы фиксирован, кроме того, неявно предполагается, что можно для любых $p,y$ разделить конкатенацию $py$ на $p$ и $y$, что в общем случае неверно для произвольного языка).

См. http://www.mccme.ru/free-books/shen/kolmbook.pdf

[Sonic86]

(Оффтоп)

cscscs в сообщении #827746 писал(а):

См. http://www.mccme.ru/free-books/shen/kolmbook.pdf

Вах, какая книга! Спасибо! Почитаю...

[cscscs]

Sonic86 в сообщении #827733 писал(а):

Условие для чего?

Sonic86 в сообщении #827733 писал(а):

для какого поиска? Для поиска чего?

Для поиска подходящих $p$ и $y$. Т.е. таких, что $l(py)\cdot s(py)=\min_{py}\{l(py)\cdot s(py)|p(y)=x\}$.

Sonic86 в сообщении #827733 писал(а):

тоже фараза непонятная. Откуда берется необходимость решения проблемы остановки? Заставили что-ли? Не хотите - не решайте, никто не заставляет.

Для подсчета колмогоровской сложности перебором нужно отобрать среди $p\in P$ и $y\in S$ (не знаю почему я $S$ тогда написал, ведь хотел $Y$, но раз уже написал...) такие, что $p(y)$ завершается. Потом из оставшихся отобрать те, что $p(y)=x$. И, наконец, отобрать из них те, что $l(py)$ минимально.

-- 17.02.2014, 19:27 --

Sonic86 в сообщении #827733 писал(а):

По определению (не надо путать четкие термины и представления о реальных объектах)

Определения обычно не берут с потолка. Есть какие-то мотивы.

[Sonic86]

(занудный оффтоп)

cscscs в сообщении #827755 писал(а):

Sonic86 писал(а):

По определению (не надо путать четкие термины и представления о реальных объектах)

Определения обычно не берут с потолка. Есть какие-то мотивы.

Ну да. Я и не против - Вы вполне можете определить некоторую свою сложность строки, доказать о ней какие-то теоремы, доказать, что она вычислима (если она таковой окажется) и абстрактно вполне можно допустить, что предложенную Вами сложность будут изучать и использовать. Но - это будет другая сложность, это не будет колмогоровская сложность (кстати, в этой книжке этих сложностей минимум 4 штуки - колмогоровская, префиксная, монотонная и еще какая-то - и все разные). Колмогоровская сложность определена, для нее доказана, что она невычислима и останется таковой навсегда. Вообще любая сложность и даже любая функция либо вычислима, либо невычислима. Она не может до какого-то момента быть невычислимой, а потом

cscscs в сообщении #827714 писал(а):

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

- ничего подобного не бывает никогда, математика непротиворечива.

Я книжку немного почитаю и потом, может быть, что-то более вменяемое отвечу...

cscscs в сообщении #827755 писал(а):

Для подсчета колмогоровской сложности перебором нужно отобрать среди $p\in P$ и $y\in S$ (не знаю почему я $S$ тогда написал, ведь хотел $Y$, но раз уже написал...) такие, что $p(y)$ завершается. Потом из оставшихся отобрать те, что $p(y)=x$. И, наконец, отобрать из них те, что $l(py)$ минимально.

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

[cscscs]

Sonic86 в сообщении #827837 писал(а):

А, это Вы утверждаете, что можете решить проблему остановки? Или я неправильно понял?

Нет. Не утверждаю.

Sonic86 в сообщении #827837 писал(а):

- ничего подобного не бывает никогда, математика непротиворечива.

А $C(x)$ не равно $K(x)$. Поэтому если $C$ вычислима, а $K$ нет, то это еще не противоречие.

-- 17.02.2014, 21:40 --

Sonic86 в сообщении #827837 писал(а):

Но - это будет другая сложность, это не будет колмогоровская сложность

Так я и не говорю, что будет.

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

[Sonic86]

(Оффтоп)

cscscs в сообщении #827858 писал(а):

А $C(x)$ не равно $K(x)$. Поэтому если $C$ вычислима, а $K$ нет, то это еще не противоречие.

А, все, я понял: Вы ввели свою сложность и ее исследуете.