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

[nikvic]

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

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

Потому, что это получилось красиво.

[cscscs]

Мне кажется я заметил что-то интересное (или тривиальное - кому как). $\{l(py)\mid p(y)=x\}=\bigcup_{n\in\mathbb{N}}\{l(py)\mid p(y)=x,s(py)\le n\}$. Обозначим $K^{(n)}(x)=\min_{py}\{l(py)\mid p(y)=x,s(py)\le n\}$. Очевидно, что $\{K^{(n)}(x)\}_{n\in\mathbb{N}}$ при фиксированном $x$ есть невозрастающая последовательность и $\lim_{n\to\infty}K^{(n)}(x) = K(x)$. Также очевидно (могу доказать, если не очевидно), что каждое $K^{(n)}$ есть вычислимая функция. Т.о. чем большее значение $n$ мы можем взять (фактически это показатель того насколько быстрыми компьютерами мы располагаем), тем ближе значение $K^{(n)}(x)$ будет к колмогоровской сложности.

-- 18.02.2014, 01:00 --

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

Потому, что это получилось красиво.

Мне казалось (после просмотра http://www.youtube.com/watch?v=n0cqOTFUo5E), что его заботила проблема определения случайности, а, следовательно, случайной последовательности знаков: если последовательность не сжимаемая, то она как бы случайна. А несжимаемая и означает, что имеет большую сложность. А что такое сложность? И тут всё заверте...

[cscscs]

(Оффтоп)

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

математика непротиворечива

Гёдель же доказал, что это нельзя доказать Так что не факт. Может и противоречива.