20
правок
Изменения
→Доказательство корректности
# Покажем, что в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление нуля или единицы) уже были использованы. Рассмотрим первое такое противоречие, то есть уже было два слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.
# Покажем, что невозможно вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова. Допустим, мы всё же получили слово из всех нулей раньше, чем перебрали все слова. Тогда разобьём слова, которые не попали в код на две группы: кончающиеся на единицу и кончающиеся на ноль. Докажем, что второй группы группы нет. Рассмотрим слово {abc..yz}0, не попавшее в код, где {abc..yz} — некоторая последовательность единиц и нулей. Заметим, что слово {bc..yz}00 также не в коде. Оно могло быть получено из слов 1{bc..yz}0 и 0{bc..yz}0, одно из которых есть рассматриваемое {abc..yz}0. Но если другое слово и встретилось в коде, то мы бы получили из него {bc..yz}01, следуя алгоритму (причем это слово точно встретится в первый раз). Таким образом, слово {bc..yz}00 точно не в коде. Такую же цепочку рассуждений можно провести и для слова {c..yz}000, и так далее. На n-ом шаге мы бы получили утверждение, что слова из n нулей тоже нет в коде, и пришли бы к противоречию. Заметим, что исходя из третьего и четвертого шагов, все слова вида {abc..yz}1 встречаются строго раньше {abc..yz}0, которые точно записаны в код. Таким образом, слов, не попавших в код, нет.
