Колмогоровская сложность и наши поиски смысла

[S_A]

Думаю, русские математики часто пишут не хуже… только почему-то мало подобного можно прочесть в оригинале на русском. Обидно.

Из подобного на русском вспоминается только Арнольд, и его лекции по жестким и мягким мат. моделям.

Что касается поисков закономерностей, тут всё не так просто, или так скажем, публицистично. В реальном мире важна часто не оптимальность, а вычислимость как таковая. На этом вобщем-то всё и держится…

[evkochurov]

Думаю, русские математики часто пишут не хуже… только почему-то мало подобного можно прочесть в оригинале на русском. Обидно.

На эту тему Непейвода интересно в свое время писал.

nepejvoda-n-n.livejournal.com/tag/%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%20%D0%A7%D0%B5%D0%B9%D1%82%D0%B8%D0%BD%D0%B0

[Exchan-ge]

4 – интересное число, потому что 4 = 2 × 2 и 4 = 2+2. В таком роде можно продолжать дальше

Продолжайте. Интересно.
Итак, 5 — это интересное число, потому что…

[SLY_G]

… это сумма первого чётного и первого нечётного простого чисел.

[Exchan-ge]

… это сумма первого чётного и первого нечётного простого чисел.

Это уже ближе к софистике, а не к математике.
(это действительно сумма первого чётного и первого нечётного простого чисел, но является ли этот факт интересным?)

[fireSparrow]

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

[Exchan-ge]

Тем самым сделав его интересным

Начнем с начала.
Дайте определение понятию «интересное натуральное число» и укажите критерии интересности.
Желательно, не используя примеры, взятые из вики.

[Gorushan]

Под присутствием интереса к числу подразумевают наличие связанных с этим числом фактов.

[Refridgerator]

Продолжение есть в этой книге.

[koldyr]

Колмогоровская сложность определяется с точностью до константы.
Для любой конечной последовательности существует язык, в котором она кодируется программой длинной в один бит.
И наконец, если я правильно это понял, в любом языке почти все конечные последовательности имеют описание не короче их самих.

[worldmind]

не короче или не длиннее?

[maslyaev]

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

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

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

[claygod]

Перепишем архиватор, и закодируем этот новый роман битом «1» ))

[maslyaev]

Тема "кодирование" плотно связана с передачей сообщений. Поэтому рассмотрим ситуацию, когда учительница литературы Алиса Степановна посылает романы для прочтения ученику Боре. У Бори уже есть заранее полученный от Алисы Степановны разархиватор, который разворачивает "0" в текст "Войны и мира". Но в нём нет и не может быть такого вот суперсжатия для того, что вышло после релиза разархиватора. Когда выходит очередной роман, например, Стивена Кинга, Алиса Степановна собирает и рассылает ученикам новый релиз разархиватора. После этого можно передать Боре аж целый длинный роман Стивена Кинга, просто послав ему что-нибудь вроде "8492307“. Красота? Была бы красота, если бы не надо было сначала включать текст романа в релиз и пересылать его Боре.

[alextavgen]

<<мы сможем определить, выводит ли она требуемую строку.>> Hет, в общем виде не можем. Автор статьи не до конца понимает. Теорема Райса говорит что не существует общего доказательства того, что программа делает то что надо(выводит нужную строку), которая следует из проблемы остановки машины Тьюринга, которая в свою очередь следует из теоремы о неполноте Геделя. Отсюда вся эта армия тестировщиков в ИТ и бесконечно обновляющийся Windows без определенного времени, что обновление закончится через 2 минуты и не больше…

[themen2]

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

[worldmind]

Вроде немного не так — она либо полна, но противоречива, либо непротиворечива и неполна.

[Kirhgoff]

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

[koldyr]

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

[Throwable]

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

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

[YegorVin]

И число которое задает эту позицию будет больше чем заданное число.

[zuborg]

У цифр числа Пи энтропия большая (они (цифры) подобны случайным), тогда как у самого числа Пи она не большая.

[worldmind]

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

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

[worldmind]

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

[FlowerPots]

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

здесь именно

хаотичным, незамысловатым законам физики

Хаотичные законы.
Как звучит, а?!