[Recent Entries][Archive][Friends][User Info]
| Time | Text |
|---|---|
11:48 pm![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small} tinyprince[Link] | Возвращаясь к прошлому: http://lj.rossia.org/users/tinyprince/1 Итак, у нас была максимально нестохастическая строчка длины n с колмогоровской сложностью k. Оказалось, что по любым её k битам, находящимся в простых местах её можно восстановить. Кстати эти k бит оказались ни чем иным, как первыми битами знаменитого Омега. Так вот, оказалось, что такое кодирование существует для любых k бит: для любой строки А длины k и для любого n > k существует такая строчка B, что по любым простым k битам B можно восстановить A (ну и B если n = O(k)). Мое доказательство чисто алгоритмическое, а Шень придумал вероятностное (и очень прикольно понять связь). Из всего этого несложно следует, что существует строчка длины n, по любым k битам которой можно восстановить первые k бит Омеги, но которая является стохастической. Формула красоты утекла сквозь пальцы просто. |
| Reply: | |