Возьмём для примера (как тогда взял Конвей) d=3.

Тогда первыми словами, которые мы добавим, будут
000000
000111
000222
000333
и так далее.

Казалось бы, мы будем добавлять только их. Но — давайте "мыслить трансфинитно": добавим все эти слова (пусть их и бесконечное число), и посмотрим, какое слово мы добавим после них.

Ответ — это слово
001012.
Потому что из (лексикографически самых младших из ещё не покрытых) слов 0010** мы не можем себе позволить заменить первую звёздочку нулём — будем на расстоянии не больше 2 до слова 000000, а из слов 00101* нам не подходят ни *=0 (из-за того же слова из нулей), ни *=1 (из-за слова 000111), а вот 001012 подходит, вот мы его и берём.

Можно продолжить заполнять этот код — и это хорошее упражнение (которое выглядит занудным, если его делает кто-нибудь ещё, но которое захватывает, когда его делаешь с листочком бумаги). Давайте я напишу ближайшие несколько кодов, которые появятся:
001012 — мы его уже видели, затем
001103
001230
001321

Затем пойдут
001456
001547
001674
001765

И когда мы, проявив упорство, добавим всё бесконечное число слов вида 001*** — первым словом вида 002*** будет
002023.
Потому что
00200* слишком близко к 000000,
00201* слишком близко к 001012,
002020 — опять к 000000,
002021 — к 001321 (и это легко пропустить),
002022 — к 000222, ну и
002023 — то, что нужно.

Так вот, мы всё это делали не просто так!

Уже на этих словах можно было увидеть какую-то регулярность — и начинать "копать" и разбираться, что же тут интересное.

Но интересного больше. Теорема, которую рассказывал Конвей на лекции —
Теорема. Можно так ввести на неотрицательных целых числах сложение и умножение (превратив их в поле), что построенный код будет линейным.

Конечно же, сложение и умножение получаются нестандартными — а поле будет характеристики 2.

На самом деле, это поле будет объединением "возрастающей башни" полей из 2^{2^k} элементов (поле из p^m элементов это подполе p^r элементов, если r это степень m).
Более того, сложение тут — это то самое ним-сложение (побитовое сложение двоичных записей), которым решается задача о выигрышных позициях в игре в ним.

И вот эта теорема совершенно удивительна: вроде бы, мы начинали с лексикографического порядка — а в результате на натуральных числах возникла структура поля, а найденные коды оказались образующими линейное пространство.

Собственно, если взять вместо бесконечного алфавита — алфавит из B=2^{2^k} символов, — а слова ограничить конечной длиной n — то мы получим часть этого кода: слова, у которых лишь последние n символов ненулевые, и которые не выходят за алфавит A={0,1,...,B-1}. И это уже совсем ситуация кодов, с которой этот рассказ начинался.

Например, при B=4 (то есть k=2) и n=6 наш код начнётся со слов
000000
000111
000222
000333
001012
001103
001230
001321
002023
002132
...

И если верить в теорему выше — то слово 002023 должно быть равно 2*001012, где множитель два — элемент поля из 4 элементов.

И вот мы получаем "2*2=3" в поле из 4 элементов {0,1,2,3} — только обычно, конечно, никто не обозначает его элементы 2 и 3, потому что 2 это вовсе не 1+1 (которое там равно нулю).

Но соотношения мы получаем как раз какие надо: в поле из 4 элементов, кроме 0 и 1, для которых 1+1=0, есть ещё два элемента, a и b (те самые наши "2" и "3"), причём a^2=b, b^2=a, ab=1, a+1=b, b+1=a.

То, что ab=1, видно, например, из
2* 001321 = 002132 —
в левой части мы знаем всё, кроме "2*3".

Вот кусочек из работы Конвея и Слоана, "Lexicographic Codes: Error-Correcting Codes from Game Theory" — посвящённый как раз этим утверждениям: