|
Проблемы передачи информации, 2005, том 41, выпуск 3, страницы 58–63
(Mi ppi107)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Большие системы
Неупрощаемые описания для условной колмогоровской сложности
М. А. Устинов Московский государственный университет им. М. В. Ломоносова
Аннотация:
Пусть некоторая программа p дает на входе a результат b. Будем искать
“упрощение” p – программу q, такую что q(a)=b, но более простую (имеющую
меньшую колмогоровскую сложность), причем легко получаемую по p
(это означает, что колмогоровская сложность K(q∣p) мала). Показано, что для
любых слов a и b (кроме вырожденных случаев) можно найти “неупрощаемую”
программу p любой наперед заданной сложности, большей K(a)+K(b∣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
|
Статистика просмотров: |
Страница аннотации: | 498 | PDF полного текста: | 125 | Список литературы: | 88 |
|