sergey писал(а):
Victor N писал(а):
Уже давным давно была представлена простейшая программа для вывода байта.
И было подчеркнуто, что точная длина зависит от выбранного компилятора.
Да, но там вы не написали сколько байт в вашей программе. Написали бы 10...15 я бы задал следующий вопрос.
А это не имеет значения.
Я же подчеркнул, что величина зависит от
выбранного компилятора. Фактически, может быть любой.
Определенного значения просто не существует.
(для нашего класса возможных декомпрессоров)
см. ниже.
sergey писал(а):
Victor N писал(а):
Кстати, декомпрессор может быть и простейшим - просто транслирующим вход на выход.
Именно этот. Я бы попросил сверить ваш результат с Шенноном. Вы бы пришли именно к этому декомпрессору.
И сделали бы наконец именно это вывод:
Victor N писал(а):
Для него KS одного байта будет равна 1 байту. А одного бита - одному биту
Браво! Сколько страниц я вас уговаривал. Теперь вижу вы наконец прочитали литературу, которую нам рекомендовали.
Victor N писал(а):
Но такой «декомпрессор» никакого практического значения не имеет.
Не торопитесь. Именно он нам выдал КS(1)=1,
Тут вы ошибаетесь. Если бы вы внимательно читали рекомендованную литературу,
то могли бы заметить, что декомпрессор не обязан воспринимать любые значения.
Буквально сказано следующее:
Цитата:
Мы не требуем, чтобы декомпрессор был определён на всех словах. При
некоторых x вычисление D(x) может зацикливаться (не останавливаться) и не
давать результата.
Так вот, тривиальный декомпрессор, тупо транслирующий вход на выход,
да еще и для одного байта, тем более одного бита... у нас это абсурд.
Декомпрессор такого рода
в нашей задаче просто невозможен.
Я вам предлагаю вернуться к теме.
Мы с вами пытаемся создать модель эволюции. Верно?
Общая модель эволюции должна создавать модели живых существ.
И сложность этих моделей должна в основном монотонно возрастать.
(из этого правила могут быть лишь редкие исключения)
Общая модель эволюции и модели живых существ,
которые она порождает, являются компьютерными программами.
Есть возражения против такой формулировки задачи?
Если их нет, предлагаю вам самостоятельно подумать,
что у нас является входными данными, декомпрессором.
Могут ли данные быть размером 1 байт. или 1 бит.
Может ли декомпрессор просто транслировать вход на выход.
sergey писал(а):
Кстати вы согласны, что именно это наименьшее значение KS? Т.е. по определению KS(1)=1 И с Шенноном прекрасно согласовывается H(1)=1. (Считать умеете?) Стало быть KS(1) вычислима.
Теперь можем двигаться дальше. Прошу сосчитайте KS(2).
Я же в самом начале темы о Колмогоровской сложности говорил,
что есть тривиальные случаи, когда ее можно определить.
KS невычислима именно в общем случае.
Но в нашем классе задач данных, которые вы предлагаете, просто не существует.
И декомпрессоров транслирующих вход на выход - тоже.
Так что в нашем классе возможных декомпрессоров у KS(1), KS(2)
просто нет определенного значения.
Вход
FAQ
Поиск
