Аннотация:
По множеству всех корректирующих кодов над фиксированным алфавитом из q символов можно построить рекурсивно перечислимое множество рациональных точек в единичном квадрате, координаты на котором суть скорость передачи и относительное минимальное расстояние. Предельные точки этого множества суть все точки под графиком некоторой непрерывной невозрастающей функции, называемой асимптотической границей.
Существование асимптотической границы было доказано докладчиком в 1981 г., однако никаких подходов к её вычислению не существовало, и даже имеется предположение о её невычислимости в смысле конструктивного анализа.
В докладе будет показано, что асимптотическая граница становится вычислимой при наличии оракула, выдающего коды в порядке возрастания их колмогоровской сложности. Более того, естестественная разделяющая функция, использующая сложность, позволяет проинтерпретировать асимптотическую границу как кривую, разделяющую две различные термодинамические фазы кодов.
Доклад основан на совместной работе с М. Марколли (arXiv: 1203.0653).
Обратная связь: