Счёт вслепую [2] // Михаил Раскин

Пользуясь цифрами 0 и 1, несложно записать натуральное число. Сложение в столбик позволяет прибавить к этому числу единицу. Такой способ записи и изменения числа требует в некоторых ситуациях прочитать и изменить все цифры. А если число большое и мы хотим читать и писать поменьше цифр, но можем быстро запросить любые цифры числа «вразбивку»? Разумеется, придётся изменить представление числа. С середины 20-го века известны коды Грея; нам всё равно потребуется иногда читать число целиком, зато менять надо будет лишь по одной цифре за раз. А можно ли прибавить к числу единицу, не читая всего числа? Оказывается, можно. Предварительных знаний не потребуется. Я надеюсь, что всем слушателям удастся понять из рассказанного не меньше, чем они пожелают. Материалы к лекции: Раскин Михаил Александрович. Летняя школа «Современная математика», г. Дубна, дом отдыха «Ратмино» 21-27 июля 2017.