В математике вещественное число называется просто нормальным в целом с основанием b, если его бесконечная последовательность цифр распределена равномерно в том смысле, что каждая из bцифровые значения имеют одинаковую естественную плотность 1/b. Число называется нормальным в базе b, если для каждого положительного целого числа nвсе возможные строки nцифр имеют плотность b.
Интуитивно понятно, что число, являющееся просто нормальным, означает, что никакая цифра не встречается чаще, чем любая другая. Если число является нормальным, никакая конечная комбинация цифр заданной длины не встречается чаще, чем любая другая комбинация такой же длины. Нормальное число можно представить как бесконечную последовательность подбрасываний монеты (двоичный ) или бросков кубика (основание 6 ). Даже если будут такие последовательности, как 10, 100 или более последовательных решек (двоичные) или пятерок (основание 6) или даже 10, 100 или более повторений последовательности, такой как хвост-голова (два последовательных подбрасывания монеты) или 6 -1 (два последовательных броска кубика), также будет столько же любой другой последовательности равной длины. Никакая цифра или последовательность не приветствуются.
Число называется абсолютно нормальным, если оно нормально во всех основаниях целых чисел, больших или равных 2.
Хотя общее доказательство может быть дано, что почти все действительные числа являются нормальными (это означает, что набор ненормальных чисел имеет меру Лебега ноль), это доказательство не является конструктивным, и только несколько конкретных чисел оказались нормальными. Например, константа Чейтина является нормальной (и невычислимой ). Широко распространено мнение, что (вычислимые) числа √2, π и e нормальны, но доказательства остаются неуловимыми.
Пусть Σ будет конечным алфавитом из b- цифр, а Σ набор всех последовательностей, которые могут быть взяты из этого алфавита. Пусть S ∈ Σ - такая последовательность. Для каждого a в Σ пусть N S (a, n) обозначает, сколько раз цифра a встречается в первых n цифрах последовательности S. Мы говорим, что S просто нормальный если предел
для каждого a. Теперь пусть w - любая конечная строка в Σ, и пусть N S (w, n) - количество раз, когда строка w появляется как подстрока в первые n цифр последовательности S. (Например, если S = 01010101..., то N S (010, 8) = 3.) S является нормальным, если для все конечные строки w ∈ Σ,
где | w | обозначает длину строки w. Другими словами, S является нормальным, если все строки одинаковой длины встречаются с одинаковой асимптотической частотой. Например, в нормальной двоичной последовательности (последовательность в алфавите {0,1}) 0 и 1 встречаются с частотой ⁄ 2 ; 00, 01, 10 и 11 встречаются с частотой ⁄ 4 ; 000, 001, 010, 011, 100, 101, 110 и 111 встречаются с частотой ⁄ 8 и т. Д. Грубо говоря, вероятность нахождения строки w в любом заданном позиция в S в точности такая, как ожидалось, если бы последовательность была создана в random.
. Предположим теперь, что b - это целое число больше 1, а x - действительное число. Рассмотрим расширение бесконечной последовательности цифр S x, b числа x в позиционной системе счисления с основанием b (мы игнорируем десятичную точку). Мы говорим, что x просто нормален по основанию b, если последовательность S x, b просто нормален, и что x нормален по основанию b, если последовательность S x, b нормально. Число x называется нормальным числом (или иногда абсолютно нормальным числом ), если оно является нормальным по основанию b для каждого целого числа b больше 1.
A заданная бесконечная последовательность является либо нормальной, либо ненормальной, тогда как действительное число, имеющее различное расширение base-b для каждого целого числа b ≥ 2, может быть нормальным в одной базе, но не в другой (в этом случае это не нормальное число). Для оснований r и s с log r / log s рациональным (так что r = b и s = b) каждое число, нормальное по основанию r, является нормальным по основанию s. Для оснований r и s с иррациональными log r / log s существует несчетное количество нормальных чисел в каждой базе, но не в другом.
A дизъюнктивная последовательность - это последовательность, в которой появляется каждая конечная строка. Нормальная последовательность дизъюнктивна, но дизъюнктивная последовательность не обязательно должна быть нормальной. Богатое число с основанием b - это число, расширение которого по основанию b дизъюнктивно: число, которое дизъюнктивно по отношению к любому основанию, называется абсолютно дизъюнктивным или называется лексиконом . Число, нормальное по основанию b, богато основанием b, но не обязательно наоборот. Действительное число x богато основанием b тогда и только тогда, когда множество {xb mod 1: n ∈ N} плотно в единичном интервале.
Мы определили число как просто нормальное в основании b, если каждая отдельная цифра появляется с частотой 1 / b. Для данного основания b число может быть просто нормальным (но не нормальным или b-плотным), b-плотным (но не просто нормальным или нормальным), нормальным (и, таким образом, просто нормальным и b-плотным), или ни одним из этих. Число является абсолютно ненормальным или абсолютно ненормальным, если оно не просто нормальное для любой базы.
Для любой базы, в то время как рациональные числа могут быть просто нормальными в определенной основе, каждое нормальное число иррационально.
Концепция нормального числа была введена Эмилем Борелем (1909). Используя лемму Бореля – Кантелли, он доказал, что почти все действительные числа являются нормальными, установив существование нормальных чисел. Вацлав Серпинский (1917) показал, что можно указать конкретное такое число. Бехер и Фигейра (2002) доказали, что существует вычислимое абсолютно нормальное число. Хотя эта конструкция не дает напрямую цифр построенных чисел, она показывает, что в принципе возможно перечислить все цифры конкретного нормального числа.
Набор ненормальных чисел, несмотря на то, что он «большой» в смысле несчетности, также является нулевым набором (как его мера Лебега как подмножество действительных чисел равно нулю, поэтому оно практически не занимает места внутри действительных чисел). Кроме того, ненормальные числа (как и нормальные числа) плотны в действительных числах: набор ненормальных чисел между двумя различными действительными числами не пуст, поскольку он содержит каждое рациональное число ( на самом деле, это несчетное число бесконечных и даже сходится ). Например, существует несчетное количество чисел, десятичные разложения которых (с основанием 3 или выше) не содержат цифры 1, и ни одно из этих чисел не является нормальным.
, полученная путем объединения десятичных представлений натуральных чисел по порядку, является нормальной по основанию 10. Аналогичным образом, различные варианты постоянной Шамперноу ( выполняются путем выполнения такой же конкатенации в других базах) являются нормальными в своих соответствующих базах (например, постоянная Чамперноуна по основанию 2 нормальна в базе 2), но не было доказано, что они нормальны в других базах.
, полученная путем конкатенации простых чисел по основанию 10, нормальна по основанию 10, как доказано А. Х. Коупленд и Пол Эрдеш (1946). В более общем плане последние авторы доказали, что действительное число, представленное в основании b конкатенацией
, где f (n) - это n простое число, выраженное в основании b, нормально в основании b. Безикович (1935) доказал, что число, представленное тем же выражением, с f (n) = n,
полученное путем конкатенации квадратные числа в базе 10, нормально в базе 10. Гарольд Дэвенпорт и Эрдеш (1952) доказали, что число, представленное тем же выражением, где f - любое непостоянный многочлен, значения положительных целых чисел которого являются положительными целыми числами, выраженными по основанию 10, нормален по основанию 10.
Накай и Шиокава (1992) доказали, что если f (x) - любой непостоянный многочлен с действительными коэффициентами, такой что f (x)>0 для всех x>0, тогда действительное число, представленное конкатенацией
где [f (n)] - целая часть числа f (n), выраженная по основанию b, является нормальным по основанию b. (Этот результат включает в качестве частных случаев все вышеупомянутые результаты Чамперноуна, Безиковича, Дэвенпорта и Эрдеша.) Авторы также показывают, что тот же результат имеет место даже в более общем случае, когда f является любой функцией вида
где αs и βs - действительные числа с β>β 1>β2>...>β d ≥ 0 и f (x)>0 для всех x>0.
Бейли и Крэндалл (2002) показывают явный бесчисленно бесконечный класс b-нормальных чисел, возмущая числа Стоунхема.
Это было неуловимо цель доказать нормальность чисел, которые не построены искусственно. Хотя √2, π, ln (2) и e строго предполагаются как нормальные, до сих пор не известно, являются ли они нормальными или нет. Не было даже доказано, что все цифры на самом деле встречаются бесконечно много раз в десятичных разложениях этих констант (например, в случае π популярное утверждение «каждая строка чисел в конечном итоге встречается в π» не является истинным.). Также было высказано предположение, что каждое иррациональное алгебраическое число абсолютно нормально (что означало бы, что √2 нормально), и контрпримеры не известны ни в какой базе. Однако ни одно иррациональное алгебраическое число не оказалось нормальным ни в какой базе.
Никакое рациональное число не является нормальным в любом основании, поскольку последовательности цифр рациональных чисел в конечном итоге периодичны. Однако рациональное число может быть просто нормальным в определенной базе. Например, просто нормально в базе 10.
Мартин (2001) привел простой пример иррационального числа, которое абсолютно ненормально. Пусть f (2) = 4 и
Тогда α - это Число Лиувилля и абсолютно ненормально.
Дополнительные свойства нормальных чисел включают:
Агафонов показал ранний связь между конечными автоматами и нормальными последовательностями: каждая бесконечная подпоследовательность, выбранная из нормальной последовательности с помощью обычного языка, также является нормальной. Другими словами, если кто-то запускает конечный автомат в нормальной последовательности, где каждое из состояний конечного автомата помечено либо «выход», либо «нет выхода», и машина выводит цифру, которую он читает следующей после ввода "output" состояние, но не выводит следующую цифру после входа в "no output state", тогда последовательность, которую он выводит, будет нормальной.
Существует более глубокая связь с игроками с конечным числом состояний (FSG) и информацией Конечные компрессоры без потерь (ILFSC).
Шнорр и Стимм показали, что ни один FSG не может преуспеть в любой нормальной последовательности, а Bourke, Hitchcock и Винодчандран показал обратное. Следовательно:
Зив и Лемпель показали:
(они фактически показали, что оптимальная степень сжатия последовательности по всем ILFSCs является в точности ее скоростью энтропии, количественной мерой ее отклонения от нормальности, которая равна 1 именно тогда, когда последовательность обычный). Поскольку алгоритм сжатия LZ сжимает асимптотически так же, как и любой ILFSC, это означает, что алгоритм сжатия LZ может сжимать любую ненормальную последовательность.
Эти характеристики нормальных последовательностей можно интерпретировать как означающие что "нормальный" = "случайный с конечным числом состояний"; т.е. нормальные последовательности - это в точности те, которые кажутся случайными для любого конечного автомата. Сравните это с алгоритмически случайными последовательностями, которые представляют собой те бесконечные последовательности, которые кажутся случайными для любого алгоритма (и на самом деле имеют аналогичные характеристики азартных игр и сжатия с машинами Тьюринга, заменяющими конечные автоматы).
Число x нормально в основании b тогда и только тогда, когда последовательность
Эта связь приводит к терминологии, согласно которой x является нормальным по основанию β для любого действительного числа β, если последовательность