[Recent Entries][Archive][Friends][User Info]
| April 8th, 2014 | |
|---|---|
| 11:48 pm [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 бит Омеги, но которая является стохастической. Формула красоты утекла сквозь пальцы просто. |