Вспоминая Конвея: одна из его лекций, которые я услышал (на одной из бременско-лионских летних школ, http://www.issmys.eu/previous-year ) была о лексикографических кодах. Давайте я сначала расскажу эту конструкцию так, как тогда рассказывал он сам.

Для начала — чуть-чуть общих слов о кодах, исправляющих ошибки (если вы с ними уже встречались — это можно спокойно пропустить).

Есть блочные коды — когда есть некоторый алфавит A, размер блока n, и подмножество S кодовых слов среди всех слов A^n длины n. На словах есть расстояние Хэмминга — это число мест, в которых они различаются. И кодовое расстояние d — это наименьшее расстояние между двумя словами кода. Передавая сообщение, мы его кодируем в |S|-ичной системе счисления и передаём, пересылая словами из S. И чем больше кодовое расстояние — тем устойчивее код к помехам.

Простейший пример — алфавит из 0 и 1, сообщения длины n состоят из собственно сообщения в первых (n-1), последний бит это "бит контроля чётности": сумма всех предыдущих mod 2.
Кодовое расстояние d=2, поэтому если при передаче происходит одна ошибка, мы её обнаруживаем — но не можем исправить, потому что не знаем, какой бит поменялся.

Следующий стандартный пример — это код Хэмминга. Это код из 16 слов на блоках длины n=7. Но перечислять 16 слов неудобно — и есть отдельный удобный класс кодов, линейные. Это коды, у которых множества слов являются линейным подпространством; соответственно, достаточно задать его базис (а координаты разложения передаваемой строки по нему будут независимыми битами/символами).
Матрица, строки которой есть элементы этого базиса, называется порождающей матрицей кода; вот порождающая матрица кода Хэмминга —
(1 0 0 0 0 1 1)
(0 1 0 0 1 0 1)
(0 0 1 0 1 1 0)
(0 0 0 1 1 1 1)

Кстати, несложно видеть, что в этой матрице первые 4 столбца образуют тождественную матрицу; поэтому первые четыре бита (они же коэффициенты разложения по этому базису) можно считать самим сообщением, а последние три — аналогом "контрольной суммы", контролирующими передачу первых битов и друг друга.

И несложное упражнение — проверить, что для кода Хэмминга d=3. Поэтому если при передаче происходит одна ошибка, можно не только обнаружить факт ошибки, но и её исправить. Действительно, из-за неравенства треугольника ни от какого слова не будут два слова на расстоянии 1 (иначе расстояние между ними было бы не больше 1+1=2<d=3).

Соответственно, конечно же, хочется d побольше, но чтобы размерность кода не сильно падала. Потому что код S={00000,11111} под названием "повторить пять раз", конечно, имеет d=5 и потому исправляет две ошибки, но пропускную способность канала в те же 5 раз уменьшает.

Ну и тут есть много большой красивой науки — куда я не пойду, хотя оставлю ссылку на лекцию Шеня (https://www.youtube.com/watch?v=DNCpIo1Gjco ) и на соответствующий рассказ на Мат. Этюдах (где кодируется уже не дискретным алфавитом) — https://www.etudes.ru/ru/etudes/contact-number/

Так вот, используя понятия выше как мотивировку, рассмотрим вот такую странную конструкцию. Пусть у нас есть бесконечный алфавит A={0,1,2,3,...} из неотрицательных целых чисел. Рассмотрим слова в таком алфавите, бесконечные влево — как в конструкции p-адических чисел. И зафиксируем "кодовое расстояние" — число d>0.

После чего будем "жадным образом" строить код S — добавляя каждый раз лексикографически первое слово, которое находится на расстоянии хотя бы d от всех уже построенных.

Возьмём для примера (как тогда взял Конвей) 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.