|
СЕМИНАРЫ |
Семинар «Глобус» (записи с 2011 года)
|
|||
|
Колмогоровская сложность и асимптотическая граница для кодов, исправляющих ошибки Ю. И. Манинab a Northwestern University, Evanston b Max Planck Institute for Mathematics |
|||
Аннотация: По множеству всех корректирующих кодов над фиксированным алфавитом из Существование асимптотической границы было доказано докладчиком в 1981 г., однако никаких подходов к её вычислению не существовало, и даже имеется предположение о её невычислимости в смысле конструктивного анализа. В докладе будет показано, что асимптотическая граница становится вычислимой при наличии оракула, выдающего коды в порядке возрастания их колмогоровской сложности. Более того, естестественная разделяющая функция, использующая сложность, позволяет проинтерпретировать асимптотическую границу как кривую, разделяющую две различные термодинамические фазы кодов. Доклад основан на совместной работе с М. Марколли (arXiv: 1203.0653). |