Главы | Экскурс в двоичную систему счисления

Совместно с издательством «Питер» публикуем главу из книги математика Юджинии Ченг «Математический беспредел. От элементарной математики к возвышенным абстракциям» о том, почему некоторые числа невозможно сосчитать, а бесконечность + 1 не то же самое, что 1 + бесконечность. Перевод с английского А. Шмид.

Двоичная система счисления — это такое представление чисел, в котором вместо цифр 0, 1, 2, 3 и так далее до 9, которыми мы обычно пользуемся в десятичной системе счисления, используются только цифры 0 и 1. Удивительно, сколько информации можно хранить с помощью всего лишь двух цифр, 0 и 1. Компьютеры работают исключительно в этой системе, как будто все вокруг представляет собой лишь переключение с on на off, и таких переключений существуют миллионы и миллиарды. Вы можете получить очень много разных конфигураций, имея в своем распоряжении очень маленькое количество вариантов on/off переключений.

При наличии двух переключений вы можете получить четыре возможные конфигурации:

При наличии трех переключений вы получаете уже восемь конфигураций:

Это похоже на меню из двух или трех блюд. Дерево переключений будет выглядеть таким образом:

При наличии трех переключений каждая из восьми конечных точек дает нам одну из восьми конфигураций. Мы просто должны проследить сверху вниз по веткам до конечной точки, считывая по пути off и on.

Мы будем называть эти рисунки деревьями, потому что именно так они называются в математике. Это кажется глупым, ведь обычно деревья растут снизу вверх, но математические деревья часто растут так, потому что нам привычно читать сверху вниз. Хотя некоторые направляют математические деревья в сторону:

Думаю, вы понимаете, что не имеет никакого значения, в какую сторону мы направляем наше математическое дерево, потому что независимо от расположения схемы в ней зашифрована одна и та же информация. Мы можем также назвать такое дерево блок-схемой, так как оно демонстрирует абстрактные, а не физические отношения объектов друг к другу. По мере того как математика становится более абстрактной, в ней используются все более наглядные схемы, а абстрактные отношения объектов друг к другу становятся все более тонкими и все более значительными. Кроме того, схемы часто способны представить информацию гораздо более кратко, чем словесные объяснения. Вспомните, например, нашу схему эвакуации бесконечного отеля-небоскреба Гильберта.

В большинстве случаев базовая математика идет прямым путем. Например, вот такое сложение:

3 + 2 = 5.

Или вот такое уравнение:

2х + 3 = 7.

Символы радостно выстроились в ряд. Решение этого уравнения мы тоже будем записывать рядами:

2х = 7 — 3

2х = 4

х = 2.

Далее мы увидим, что по мере усложнения математика приобретет больше измерений. Если изучаемые нами объекты имеют форму, то у нас уже появляется больше способов скомпоновать их друг с другом. Мы сможем сделать нечто большее, чем просто выстроить их в ряд. Это как собирать пазл или строить что-то из Лего. Представьте, что вы пытаетесь объяснить кому-то на словах, как построить машину из Лего, не показывая инструкции в картинках. Рисунок может заменить тысячи слов, точно так же и математическая схема может многое объяснить гораздо быстрее и нагляднее.

Возможно, вы заметили, что, добавив к дереву новое переключение, на следующем уровне мы должны разделить каждую конечную точку на две ветви. Кстати, конечные точки часто называют «листьями», потому что они находятся на концах «ветвей», даже если дерево растет сверху вниз.

Каждый раз, когда мы добавляем одно переключение, мы удваиваем количество возможных конфигураций. Это значит, что для четырех переключений у нас будет 2 × 2 × 2 × 2 возможных конфигураций, то есть 2^4, а для n переключений у нас будет 2^n возможных конфигураций. Это похоже на то, как мы считали числа с n-м количеством десятичных знаков, только теперь у нас не десять, а два варианта выбора для каждого уровня, как в примере с меню.

Двоичная система счисления представляет собой различные наборы on/off переключений. Она похожа на десятичную систему счисления, но вместо единиц, десятков, сотен, тысяч и так далее у нас будут единицы, пары, четверки, восьмерки и так далее. Целые числа в двоичной системе счисления более популярны, чем дроби. Мы можем сравнить четырехзначное число в десятичной и в двоичной системе счисления, например, вот таким образом:

В десятичной системе счисления число 1101 можно разложить следующим образом:

(1 × 1 000) + (1 × 100) + (0 × 10) +1.

А двоичное число 1101 можно разложить на десятичные разряды следующим образом:

(1 × 8) + (1 × 4) + (0 × 2) + 1.

В то время как в десятичной системе это будет 13.

В десятичной системе четырехзначное число может выразить любое число до 9999, то есть 10^4 — 1. А в двоичной системе четырехзначное число может выразить только числа до 2^4 — 1 = 15.

Может показаться, что двоичная система счисления слабовата, особенно при том, что в главе 5 я пообещала, что в двоичном мире мы сможем считать на пальцах до 1023. Но мы будем использовать принцип чередования. В двоичной системе вы можете зашифровать все, что угодно, с помощью простых on/off переключений, а в десятичной системе каждая «позиция» предполагает десять вариантов фрагмента информации, выраженные цифрами 0, 1 и далее до 9. Иногда у нас есть большое количество цифр, которые мы можем использовать, но мало позиций для них (скажем, в компьютере). Или, например, [tooltip word="ISBN-код» text="Международный стандартный номер книги. — Примечание переводчика"] на книгах размещается на ограниченном пространстве, но каждая позиция может выражать множество разных вещей. Цветовой код HTML еще более компактный, он записывается в шестнадцатеричной системе счисления, то есть на базе 16. Это значит, каждая позиция имеет 16 возможных вариантов. Используются такие знаки, как 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, B, C, D, E, F.

Один из моих любимых вариантов использования двоичной системы счисления — это свечи на именинном пироге. Если у вас есть всего семь свечей, то кажется, что вы можете украсить только пирог для ребенка, которому исполняется не более семи лет. Но если вы будете использовать двоичную систему счисления, то есть зажженная свечка будет представлять собой on, или 1, а незажженная свечка — off, или 0, то вы сможете поздравить любого человека, кому исполняется меньше 128 лет. То есть, конечно же, любого из ныне живущих на земле.

И да, мы действительно можем использовать двоичную систему счисления для того, чтобы посчитать на пальцах до 1023, то есть до 2^10 — 1. Вот как это делается. У каждого пальца есть два возможных положения. Он может быть выпрямленным, это будет 1, или загнутым, это будет 0. И вот у нас есть десять цифр (десять обычных цифр!), которые мы можем использовать в двоичной системе счисления, что позволит нам выразить числа от 0 до 1023. На рисунке ниже приведены числа от 0 до 31, которые мы можем показать с помощью одной руки.

А вот соответствующие цифры в пятизначной двоичной системе:

Это довольно занимательно, но требует некоторой концентрации внимания, гораздо большей, чем при обычном счете на пальцах до 10. К сожалению, маловероятно, что этот метод поможет нам высвободить ментальное пространство. Я не уверена, что у меня получится долго считать в двоичной системе и одновременно разговаривать с кем-нибудь. (Я только что попробовала сделать это, но дошла только до 10, а потом сбилась.)

Если вы умеете концентрироваться и хорошо владеете своими пальцами, то можете использовать их даже на базе 3. Это означает, что у вас будет 3 возможных варианта для каждой позиции. Для этого вы должны уметь сгибать каждый палец наполовину, независимо от положения остальных пальцев, тогда каждый палец будет иметь 3 возможных положения, которые будут соответствовать 0, 1 и 2. Попробуйте выпрямить безымянный палец и одновременно согнуть средний палец наполовину, затем согните безымянный палец полностью. Есть ли разница между этими положениями? Тут требуется немало ловкости.

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

Когда мы имеем дело с десятичными дробями, после запятой идут десятые, потом сотые, потом тысячные и так далее. Например, число

0,3526

в действительности представляет собой

У двоичных дробей первый знак после запятой будет половина, следующий — четверти, потом восьмые доли и шестнадцатые доли. Так, двоичное число

0,1101

можно также записать как

Что в обычной десятичной системе счисления будет десятичной дробью 0,8125. Мы также можем изобразить все возможные двоичные дроби в виде дерева, точно так же, как мы рисовали все конфигурации переключений on/off.

На этом рисунке вместо ветвей off и on у нас будут ветви 0 и 1. Это похоже на то, как мы использовали зажженные и незажженные свечки на двоичном именинном пироге в качестве 0 и 1. Сейчас у нас есть только четыре цифры, и, значит, будет только четыре уровня разветвления. Мы могли бы использовать этот метод также для обычных десятичных дробей, но тогда нам понадобилось бы десять ветвей, выходящих из каждой конечной точки на каждом уровне. Такое дерево быстро нарисовать не получится.

Теперь каждый лист представляет собой двоичную дробь. Чтобы узнать, какую именно, нужно проследить по дереву сверху вниз, считывая по пути нули и единицы на каждой ветви. Так, первый лист будет 0,0000. Второй — 0,0001 и т. д. Вот они все:

Если у нас четыре цифры, то наше дерево будет иметь пять уровней, если у нас n цифр, то наше дерево будет иметь n-е количество уровней, а если у нас будут двоичные дроби с бесконечным количеством десятичных знаков, то это будет «дерево с бесконечным количеством уровней». Это немного странная концепция, потому что предполагается, что конечные точки дерева — листья — должны представлять собой итоговые числа. Но если дерево растет бесконечно, то не будет никаких конечных точек. По этой причине разумнее рассматривать числа как линии на дереве. Мы уже выяснили, что можем узнать, какое число выражает каждый листок, проследив за его линией по дереву сверху вниз. Даже если у дерева нет никаких конкретных конечных точек (потому что оно бесконечно), мы все равно можем проследить за его линиями, которые тоже будут продолжаться бесконечно.

Двоичные числа могут выражать все числа, которые способна выразить обычная десятичная система (просто для этого требуется больше цифр), точно так же двоичные дроби могут выражать все возможные десятичные дроби (тоже используя при этом больше цифр). Так, линии бесконечного дерева соответствуют всем «десятичным числам, которые продолжаются бесконечно», то есть всем действительным числам. Или, как минимум, действительным числам от 0 до 1. И вот мы снова можем приоткрыть дверь в неизведанное:

* По дереву с n-м количеством уровней проходит 2^n линий.

* По дереву с бесконечным количеством уровней проходит «два в бесконечной степени» линий.

До сих пор мы не рассматривали целую часть дроби. В следующей главе мы узнаем, почему эта часть дроби не имеет большого значения. Мы также выясним, почему целую часть дроби лучше рассматривать в двоичной системе счисления, а не в десятичной и почему сначала мы могли ее игнорировать.

Возможно, сейчас вы думаете, что мы все еще ничего не добились. Ведь мы так и застряли на вопросе: сколько будет два в бесконечной степени? В следующей главе мы соберемся с силами и справимся с этим вопросом. Но сначала увидим такой захватывающий пейзаж, какой мы только способны оценить. Мы уже знаем, как построить действительные числа из натуральных с помощью деревьев. Знаем, что именно так можно создать более большую бесконечность. Все, что нам теперь нужно, — это повторение, и так мы создадим иерархию бесконечностей. Это тема следующей главы.