|
Проблемы передачи информации, 2005, том 41, выпуск 3, страницы 58–63
(Mi ppi107)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Большие системы
Неупрощаемые описания для условной колмогоровской сложности
М. А. Устинов Московский государственный университет им. М. В. Ломоносова
Аннотация:
Пусть некоторая программа $p$ дает на входе $a$ результат $b$. Будем искать
“упрощение” $p$ – программу $q$, такую что $q(a)=b$, но более простую (имеющую
меньшую колмогоровскую сложность), причем легко получаемую по $p$
(это означает, что колмогоровская сложность $K(q\mid p)$ мала). Показано, что для
любых слов $a$ и $b$ (кроме вырожденных случаев) можно найти “неупрощаемую”
программу $p$ любой наперед заданной сложности, большей $K(a)+K(b\mid a)$.
Поступила в редакцию: 06.12.2004 После переработки: 24.05.2005
Образец цитирования:
М. А. Устинов, “Неупрощаемые описания для условной колмогоровской сложности”, Пробл. передачи информ., 41:3 (2005), 58–63; Problems Inform. Transmission, 41:3 (2005), 237–242
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi107 https://www.mathnet.ru/rus/ppi/v41/i3/p58
|
Статистика просмотров: |
Страница аннотации: | 424 | PDF полного текста: | 92 | Список литературы: | 59 |
|