[Recent Entries][Archive][Friends][User Info]
| September 16th, 2013 | |
|---|---|
| 12:16 pm [Link] |     которая печатает это число. Она невычислима: есть тривиальная оценка K(n) < ln(n) + const, то есть существует только конечное число программ, которые нужно перебрать, чтобы найти нужную, однако программы могут работать очень долго, и мы хуй поймем напечатается ли в конце концов n или нет. Также, если программа работает квадриллион лет, но сама она маленькая, то мы и сложность соответствующего числа считаем маленькой (это странно(?)). Можно ввести "Колмогоровскую сложность со временем" KT например так: берется минимум не по длинам всех программ, а по длинам программ, умноженных на время их работы. Такое определение решает перечисленные выше "проблемы". Философскими аспектами К занимался(-ется) Ю. И. Манин. Ну например: Мы производим научные знания в порядке увеличения его Колмогоровской сложности, ни в каком-нибудь другом. Более того, эти знаменитые научные описания, которые являются вехами в истории человечества - эф равно эм один эм 2 на эр квадрат, е равно эм цэ квадрат, уравнения Максвелла - это компактнейшие описания огромной сжатой части Вселенной... Ок. А какой философской смысл KT? Для начала представим себе минимальную программу в обычном колмогоровском смысле. Допустим, там есть процедура, которая умножает чиселки. Если что, кроме как столбиком, есть еще куча хитрых алгоритмов которые перемножают числа за O(nlog(n)loglog(n)) и даже меньше операций. Какой метод будет реализован? Ответ: столбиком (время нас не ебет совершенно, а место нужно экономить). В KT же будет реализован самый охуенный алгоритм(ну если требуется перемножать достаточно большие числа). Вообще для K вся наука про то как быстро чего-нибудь посчитать оказывается совершенно бесполезной. Далее, можно придумать пример числа для которого K-сложность очевидно оч маленькая, а для KT это можно доказать только средствами сложных алгоритмов 21-го века. Я веду к тому, что Колмогоровская сложность отвечает за теоретическую науку, а Колмогоровская_сложность_со_временем за науку, пропущенную через призму реальности (и, как часто бывает, здесь все не так гладко, как в теории). То есть для Манина е давным давно равно эм цэ квадрат, а для реальности так будет только когда можно будет получить стопицот джоулей из любого куска дерьма. P. S. Активная нелюбовь чистых математиков к математике прикладной объясняется тем, что такие вещи совершенно бесполезны с точки зрения минимальных программ для K (написанием которых ученые-теоретики все время занимаются). P. P. S. Несмотря на вычислимость, KT оказалась гораздо более сложным объектом для исследований, чем K (со временем вообще никто толком работать не умеет). |