Привет, читатели моего блога! В этот раз я решил поделиться переводом статьи Brian'а Hayes'а из шестого номера журнала American Scientist за 2001 год.
Перевод этой статьи мной был пару лет назад опубликован на другом ресурсе, но там меня давно уже нет , да и статья там превратилась в нечто непонятное из-за того, что чудесным образом половина прикреплённых изображений пропала оттуда, а некоторые сменились совершенно другими. Очевидно, тот ресурс со своими приколами - багами. Ресурс однодневка, газета "СПИДИНФО". Какую-то интересную и полезную информацию в "газетах" хранить не рекомендуется. В них её просто нет! Поэтому я решил заново опубликовать перевод этой статьи тут, у себя в блоге. Итак, поехали, но вначале небольшой эпиграф от меня.
Эпиграф.
"Tertium non datur" или "третьего не дано" - утверждение выдвинутое стоиками и утвердившееся во всём и везде в этом мире. Но верно ли оно?
Парадоксальность материальной импликации, обретённая в условиях двузначности отношением необходимого следования, и тщетность всех попыток исправить положение изобретением строгих, сильных, релевантных, паранепротиворечивых и прочих импликаций неопровержимо свидетельствуют о неадекватности двузначной логики. Трёхзначность присуща следованию, определённому в силлогистике Аристотеля, против которого предназначался вымешленный стоиками "закон" исключённого третьего.
Категорически извратил аристотелево следование С.К.Клини, истолковав отношение "все X суть Y" как удовлетворяющееся при несуществовании X, ибо "смысл этот проще и потому полезнее". В результате его следование обрело парадоксы материальной импликации. Кэррол сказал бы: "Трёхзначная реальность стала двузначной химерой". Где же полезность?
ОСНОВАНИЕ ТРИ
Люди считают десятками, а машины считают двойками — это в значительной степени подводит итог тому, как мы работаем с арифметикой на этой планете. Но есть бесчисленное множество других способов подсчета. Здесь я хочу предложить троекратное приветствие троичной системе - основанию 3. Цифровой ряд представления числа в этой системе: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, и т.д.
Они не так широко известны или не так широко используются, как их десятичные и двоичные собратья, но у них есть свои прелести. Это лучший выбор среди систем нумерации, когда база 2 слишком мала, а база 10 слишком велика, база 3 подходит в самый раз.
Втроём эффективнее.
Подноготная всех систем нумерации одинакова. Цифры в разных базах могут выглядеть по-разному, но числа, которые они представляют, одни и те же. В десятичной системе счисления цифра 19 является сокращением для выражения:
1x10^1 + 9х10^0
Аналогично двоичная цифра 10011 представляет собой:
1x2^4 + 0x2^3 + 0x2^2 + 1x2^1 + 1x2^0
Представления числа разные, а значение - одно! То же самое относится и к троичной версии 201:
2x3^2 + 0х3^1 + 1x3^0
Общая формула для числительного в любой позиционной записи выглядит примерно так:
...d3r^3 + d2r^2 + d1r^1 + d0r^0....
Здесь r - основание, или база. А d3..d2..d1..d0 - это цифры в представлении числа по порядку следования. Обычно r является положительным целым числом, а цифры представляют собой целые числа в диапазоне от 0 до r–1, но ни одно из этих ограничений не является строго необходимым. Вы можете составить совершенно правильные числа на отрицательной или иррациональной основе, и ниже мы встретим числа с отрицательными цифрами.
Однако сказать, что все базы представляют одни и те же числа, не означает сказать, что все числовые представления
одинаково хороши для всех целей. База 10, как известно, хорошо подходит для тех из нас, кто считает по пальцам.
База 2 доминирует в вычислительной технике, потому что двоичные устройства просты и надежны, с двумя стабильными состояниями — включен или выключен, полный или пустой. Компьютерная схема также использует совпадение двоичной арифметики и двоичной логики: один и тот же сигнал может представлять либо числовое значение (1 или 0), либо логическое значение (истина или ложь). Традиционные предпочтения базы 10 и технические преимущества базы 2 не имеют ничего общего с какими-либо внутренними свойствами десятичной и двоичной систем счисления. База 3, с другой стороны, имеет подлинное математическое различие в свою пользу. По одной правдоподобной гипотезе, это самая эффективная из всех целочисленных баз; она предлагает наиболее экономичный способ представления чисел.
Как вы измеряете экономность числового представления? Если вы просто считаете цифры, то всегда выигрывает самая большая база; например, основание 1 000 000 может представлять любое число от 0 до десятичных 999 999 в одной цифре. Проблема в том, что одна цифра может быть представлена одним из миллиона различных символов, все из которых вы должны каким-то образом распознать. На противоположном полюсе находятся унарные числа, или числа с основанием 1. Для унарного представления десятичного числа 1 000 000 требуется только один символ, но этот символ повторяется миллион раз. (Унарная нотация относится к категории отличной от других баз — на самом деле это не позиционная система счисления, но в настоящем контексте она служит полезным предельным случаем.) Среди всех возможных способов записи чисел до миллиона ни 1 000 000, ни 1 не кажутся идеальными; на самом деле, вы вряд ли могли бы смогли представить число хуже, чем любой из этих вариантов. Минимизация количества символов в представлении числа вызывает расширение алфавита символов, и наоборот; когда вы увеличиваете количественный фактор представления, другой уменьшается. Очевидно, нам нужно оптимизировать некоторую совместную меру ширины числа (сколько в нем цифр) и его глубины (сколько разных символов требуется для выражения одной цифры). Очевидной стратегией является минимизация произведения этих двух величин. Другими словами, если r - это основание, а w - количество символов выражающих цифру, мы хотим минимизировать rw при этом сохраняя r^w постоянным. Любопытно, что эту проблему легче решить, если r и w рассматриваются как непрерывные, а не целочисленные переменные, то есть, если мы допускаем дробное основание и дробное число цифр. Тогда получается (см.Рисунок 1), что оптимальным основанием является число e, основание натуральных логарифмов, с числовым значением около 2,718.
Поскольку 3 - это целое число, ближайшее к e, оно почти всегда является наиболее экономичным целочисленным
основанием (см. Рисунок 2).
Рассмотрим еще раз задачу представления всех чисел от 0 до десятичных 999 999. База 10 для представления требует ширины в 6 цифр, так что rw = 60. Базе 2 достаточно 20 двоичных цифр, чтобы охватить тот же диапазон чисел, rw = 40. Но троичное представление еще лучше: троичное представление имеет ширину 13 цифр, так что rw = 39. (Если бы база e была практическим выбором, ширина составляла бы 14 цифр, что дает rw = 38,056.)
Трит за Трит за Трит.
Это особое свойство базы 3 привлекло внимание первых компьютерных разработчиков. Исходя из гипотезы о том, что количество компонентов компьютера будет примерно пропорционально как ширине, так и глубине обрабатываемых чисел, они предположили, что rw может быть хорошим показателем стоимости оборудования, и поэтому троичная нотация обеспечит наиболее эффективное использование аппаратных ресурсов. Самое раннее опубликованное обсуждение этой идеи, которое мне удалось найти, содержится в книге 1950 года "Высокоскоростные вычислительные устройства", обзоре компьютерных технологий, составленной по поручению ВМФ США сотрудниками Engineering Research Associates.
Примерно в то же время, что и исследование ERA, Герберт Р. Дж. Грош предложил троичную архитектуру для компьютерного проекта Whirlwind в Массачусетском Технологическом Институте. "Вихрь" превратился в систему управления военной радиолокационной сетью, которая дежурила над воздушным пространством Северной Америки в течение 30 лет холодной войны. Whirlwind также был испытательным полигоном для нескольких новых компьютерных технологий, включая память на магнитном сердечнике, но троичная арифметика не была среди протестированных инноваций; Whirlwind и его преемники были двоичными машинами!
Так получилось, что первый работающий троичный компьютер был построен по другую сторону Железного Занавеса.
Машина была разработана Николаем Петровичем Брусенцовым и его коллегами из Московского Государственного Университета и получила название Сетунь в честь реки, протекающей недалеко от университетского городка.
Между 1958 и 1965 годами было построено около 50 машин. Сетунь оперировал числами состоящими из 18 троичных цифр, или тритов, давая машине числовой диапазон 387 420 489. Двоичному компьютеру потребовалось бы 29 бит, чтобы достичь этой емкости; с точки зрения rw, троичный дизайн выигрывает от 54 до 58. К сожалению, Сетунь не реализовал потенциал базы 3 для уменьшения количества компонентов. Каждый трит хранился в паре магнитных сердечников, соединенных тандемом, так что бы они имели три стабильных состояния. Пара ядер могла содержать два двоичных бита, что составляет больше информации, чем один трит, и поэтому в данном аспекте троичное преимущество было достигнуто не в полной мере.
Наряду с троичной арифметикой компьютер, построенный на базе 3, может также использовать троичную логику. Рассмотрим задачу сравнения двух чисел. В машине, основанной на двоичной логике, сравнение часто представляет собой двухэтапный процесс. Сначала вы спрашиваете: "X меньше, чем Y?"; в зависимости от ответа, вам, возможно, придется задать второй вопрос, например: "Равен ли X Y?" Троичная логика упрощает процесс: одно сравнение может дать любой из трех возможных результатов: "меньше", "равно" и "больше". Троичные компьютеры были причудой, которая исчезла, хотя и не быстро. В 1960-х годах было еще несколько проектов по созданию троичных логических элементов и ячеек памяти, а также по сборке этих блоков в более крупные компоненты, такие как сумматоры. В 1973 году Гидеон Фридер и его коллеги из Государственного Университета Нью-Йорка в Буффало спроектировали полноценную машину на базе 3, которую они назвали ternac, и создали ее программный эмулятор. С тех пор идея троичных вычислений время от времени возрождалась, но вы не найдете ни одну реальную троичную машину на складе в CompUSA.
Почему база 3 не прижилась? Легко догадаться, что надежных устройств с тремя состояниями просто не существовало или их было слишком сложно разработать. И как только бинарная технология утвердилась, огромные инвестиции в методы изготовления бинарных чипов превзошли бы любое небольшое теоретическое преимущество других баз. Более того, это только гипотеза о том, что такое преимущество существует. Все зависит от предположения, что rw является надлежащей мерой аппаратной сложности, или, другими словами, что дополнительные затраты на увеличение основания то же самое, что и дополнительные затраты на увеличение количества цифр. Но даже если троичные схемы не найдут пристанища в компьютерном оборудовании, аргумент Златовласки в пользу базы 3 может применяться в других контекстах. Предположим, вы создаете одну из этих ужасных систем телефонных меню — нажмите 1, чтобы получить неудобства, нажмите 2, чтобы быть снисходительным, и так далее. Если есть много вариантов, каков наилучший способ их организации?
Рисунок 3. Троичная структура может предложить самый быстрый путь через систему телефонного меню. Размещение восьми вариантов (предположительно одинаково вероятных) в одном восьмиугольном меню (слева) заставляет вызывающего абонента прослушивать в среднем 4,5 пункта меню. Двоичная структура (посередине) имеет ту же производительность, но троичное дерево (справа) снижает среднее значение до 3,75.
Должны ли вы создать глубокую иерархию с множеством маленьких меню, каждое из которых предлагает всего несколько вариантов? Или лучше свести структуру к нескольким длинным меню? В этой ситуации разумной целью является сведение к минимуму количества вариантов, которые несчастный абонент должен прослушать, прежде чем, наконец, добраться до места назначения. Проблема аналогична проблеме представления целого числа в позиционной системе счисления: количество элементов в меню соответствует основанию r, а количество меню аналогично ширине w. Среднее количество вариантов, которые нужно выдержать, сводится к минимуму, когда в меню три блюда.
Превращение в Троичную Пыль.
Хотя числа одинаковы во всех базах, некоторые свойства чисел наиболее четко проявляются в определенных представлениях. Например, вы можете сразу увидеть, является ли двоичное число четным или нечетным: просто посмотрите на последнюю цифру. Троичная основа также различает четное и нечетное, но более тонко: троичная основа представляет четное число, если представление имеет четное число единиц. (Причину легко увидеть, когда вы считаете степени 3, которые неизменно нечетны.) Более 20 лет назад Пол Эрдо и Рональд Л. Грэм опубликовали гипотезу о троичном представлении степеней 2. Они заметили, что 2^2 и 2^8 могут быть представлены в троичной системе без каких-либо 2-ек (троичные цифры равны 11 и 100111 соответственно). Но каждая другая положительная степень 2, по-видимому, имеет по крайней мере одну 2 в своем троичном разложении; другими словами, никакая другая степень 2 не является простой суммой степеней 3. Илан Варди из Института высших научных исследований искал до 2^6973568802 не найдя контраргумента, но гипотеза остается открытой. Троичное представление числа также может помочь осветить своеобразный математический объект, называемый множеством
Кантора, или пылью Кантора. Чтобы визуально это лучше представить себе, нарисуйте отрезок и сотрите среднюю треть; затем перейдите к каждому из получившихся более коротких отрезков и удалите также среднюю треть из них, и продолжайте таким же образом. После того, как было стерто бесконечно много средних третей, остается ли что-нибудь? Один из способов ответить на этот вопрос - обозначить точки исходной линии как троичные числа от 0 до 0.222.... (Повторяющаяся троичная дробь 0,222 ... в точности равна 1,0.) Учитывая эту маркировку, первая средняя треть, подлежащая удалению, состоит из точек с координатами от 0,1 до 0,122 ..., или, другими словами, все координаты с 1 в первой позиции после точки основания. Аналогично, второй раунд стираний устраняет все точки с 1 во второй позиции после точки основания. Шаблон продолжается, и ограничивающий набор состоит из точек которые нигде не имеют единиц в их троичном представлении. В конце концов, почти все точки были уничтожены, и все же осталось бесконечное количество точек. Никакие две точки не соединены непрерывной линией, но у каждой точки есть соседи, сколь угодно близкие. Сложно сформировать мысленный образ такого бесконечно перфорированного объекта, но троичное описание это упрощает.
Драгоценный камень в Троичной Короне.
Возможно, самая красивая система счисления из всех, - пишет Дональд Э. Кнут в книге "Искусство компьютерного программирования", - это сбалансированная троичная система счисления. Как и в обычных троичных числах, цифры
сбалансированного троичного числительного являются коэффициентами степеней 3, но вместо того, чтобы исходить из множества {0, 1, 2}, цифры равны -1, 0 и 1. Они "сбалансированы", потому что расположены симметрично относительно нуля. Для удобства обозначения отрицательные цифры обычно записываются с помощью винкулума или перекладины вместо знака минус с префиксом.
В качестве примера, десятичное число 19 записывается 1(-1)01 в сбалансированной троичной системе, и это число интерпретируется следующим образом:
1x3^3 - 1x3^2 + 0х3^1 + 1x3^0
Что равно:
27 – 9 + 0 + 1
Каждое число, как положительное, так и отрицательное, может быть представлено и каждое число имеет только одно такое представление. Начинается сбалансированная последовательность троичного счета:
0, 1, 1(-1), 10, 11, 1(-1)(-1), 1(-1)0, 1(-1)1
Двигаясь в противоположном направлении, первые несколько отрицательных чисел будут:
(-1), (-1)1, (-1)0, (-1)(-1), (-1)11, (-1)10, (-1)1(-1)
Обратите внимание, что отрицательные значения легко распознать, поскольку ведущий трит всегда отрицательный. Идея систем сбалансированных чисел имеет довольно запутанную историю. И машина Сетунь, и эмулятор Фридера были основаны на сбалансированной системе, как и предложение Гроша для проекта Whirlwind. В 1950 году Клод Э. Шеннон опубликовал отчет о симметричных системах со знаком и цифрами, включая троичные и другие базы. Но ни один из этих изобретателей 20-го века не был первым. В 1840 году Огюстен Коши обсуждал числа со знаком в различных базисах, а Леон Лаланн немедленно продолжил беседу об особых достоинствах сбалансированной троичной системы счисления. Двадцатью годами ранее Джон Лесли изложил в "Философия Арифметики" методы вычисления в любой базе со знаковыми или беззнаковыми цифрами. Лесли, в свою очередь, был предвосхищен столетием ранее кратким эссе Джона Колсона "отрицательно-утвердительная арифметика". Еще раньше Иоганн Кеплер использовал сбалансированную троичную схему, смоделированную на основе римских цифр. Есть даже предположение, что арифметика со знаком подразумевалась ещё в индуистских ведах, что делает идею действительно очень старой!
Что делает сбалансированную тройку такой красивой? Это обозначение, в котором все кажется простым. Положительные и отрицательные числа объединены в одну систему, без необходимости использования отдельных знаковых битов. Арифметика почти так же проста, как и с двоичными числами; в частности, таблица умножения тривиальна. Сложение и вычитание - это, по сути, одна и та же операция: просто отрицайте одно число, а затем добавляйте. Отрицание само по себе также не требует усилий: измените каждое на 1, и наоборот. Округление - это простое усечение: установка наименее значимых значений трит равными 0 автоматически округляет до ближайшей степени 3. Наиболее известное применение сбалансированной троичной нотации - в математических головоломках, связанных с взвешиванием. Учитывая весы с двумя чашами, вас попросят взвесить монету, которая, как известно, имеет некоторый интегральный вес от 1 грамма до 40 граммов. Сколько мерных гирь вам нужно? Поспешным ответом было бы шесть весов по 1, 2, 4, 8, 16 и 32 грамма. Если монета должна попасть в одну чашу, а все измерительные веса - в другую, вы не можете сделать лучше, чем такое решение с коэффициентом 2. Однако, если гири можно положить в любую чашу, то получается "тройной трюк", который работает только с четырьмя гирями: 1, 3, 9 и 27 граммами. Например, монета весом 35 граммов будет балансировать на весах, когда гири весом 27 граммов и 9 граммов помещены в лоток напротив монеты, а гиря весом 1 грамм находится в том же лотке, что и монета. Таким образом можно взвесить каждую монету весом до 40 граммов. Джеймс Оллрайт, который поддерживает веб-сайт, пропагандирующий сбалансированную троичную систему счисления, предлагает денежную систему, основанную на том же принципе. Если и у продавца, и у покупателя есть только одна банкнота или монета каждого номинала в степени 3, они могут внести точную сдачу для любой транзакции.
Картотека Марты Стюарт.
Несколько недель назад, копаясь в файлах со старыми вырезками и корреспонденцией, я сделал открытие поразительной очевидности и тривиальности. То, что я нашел, не имело никакого отношения к содержанию файлов; речь шла об их расположении в ящике. Представьте себе привередливую офисную работницу, Марту Стюарт из секретарш, которая настаивает на том, чтобы ни одна папка с файлами не скрывалась в тени другой. Выступающие вкладки на папках должны быть расположены так, чтобы в соседних папках вкладки всегда находились в разных положениях. Добиться такого поэтапного расположения легко, если вы настраиваете новый файл, но это становится беспорядочным, когда папки добавляются или удаляются случайным образом. Ящик, заполненный "наполовину вырезанными" папками, которые имеют только две позиции вкладок, может изначально чередоваться слева-направо-слева-направо. Однако шаблон портится, как только вы вставляете папку в середину ящика. Независимо от того, какой тип папки вы выберете и куда вы ее поместите (за исключением самых концов последовательности), каждая такая вставка порождает конфликт. Удаление папки имеет тот же эффект. Перевод в двоичную цифру можно представить как слева = 0 и справа = 1, нетронутый файл представляет собой чередующуюся последовательность ...0101010101.... Вставка или удаление создает либо 00, либо 11 — дефект, очень похожий на дислокацию в кристалле. Хотя в принципе дефект можно исправить — либо путем введения второго дефекта противоположной полярности, либо путем переключения всех битов между местом дефекта и концом последовательности, — даже самый маниакально аккуратный хранитель записей вряд ли будет применять такие методы в реальном ящике для файлов.
В своих собственных картотеках я использую папки с третью, а не с половинным делением; вкладки отображаются в трех позициях: слева, посередине и справа. Тем не менее, я долго думал или, скорее, я предполагал, не утруждая себя размышлениями, что будет применяться аналогичный анализ, и что я не мог быть уверен в том, что смогу избежать конфликтов между соседними папками, если я не буду готов перемещать файлы в новые папки после каждой вставки. Затем несколько недель назад на меня снизошло прозрение в отношении картотеки: внезапно я понял, что переход от папок в двоичном представлении к папкам в троичном представлении имеет решающее значение. В любой позиции в любой такой последовательности вы всегда можете вставить новую цифру, которая отличается от своих соседей. Основание 3 - это наименьшее основание, обладающее этим свойством. Более того, если вы создаете троичную последовательность, последовательно вставляя цифры, которые избегают конфликтов, то выбор того, какой символ вставить всегда является принудительным; вам никогда не придется делать произвольный выбор из двух или более законных возможностей. Таким образом, по мере заполнения ящика с файлами не только возможно поддерживать идеальный порядок Марты Стюарт но это ещё и довольно просто реализовать. Удаления, к сожалению, доставляют больше хлопот, чем вставки. Невозможно удалить произвольные элементы ни из двоичной, ни из троичной последовательности с гарантией, что две одинаковые цифры не будут сведены вместе. (С другой стороны, если вы достаточно суетливы, чтобы беспокоиться о расположении вкладок в папках с файлами, вы, вероятно, никогда ничего не выбрасываете.)
Протокол, позволяющий избежать конфликтов, настолько очевиден, что я предполагаю, что он должен быть известен клеркам файлов повсюду. Но в полудюжине учебников по подшивке, небольшая выборка из удивительно обширной литературы, я не нашел четкого изложения принципа. Как ни странно, мое незначительное наблюдение об упорядочивании папок в ящиках для файлов приводит к некоторой математике, представляющей более широкий интерес. Предположим, вы ищете такое расположение папок, при котором вы не только избегаете размещения любых двух одинаковых вкладок рядом друг с другом, но и избегаете повторения каких-либо более длинных шаблонов. Это исключило бы не только 00 и 11, но также 0101 и 021021. Последовательности, которые не имеют смежных повторяющихся шаблонов любой длины, называются "свободными от квадратов" по аналогии с числами, у которых нет дублированных простых множителей. В двоичной системе счисления однозначные последовательности 0 и 1, очевидно, не содержат "квадратов", как и 01 и 10(но не 00 или 11); тогда среди последовательностей длиной в три бита есть 010 и 101, но ни одна из других шести возможностей не содержит "квадратов". Если вы сейчас попытаетесь создать четырехзначную двоичную последовательность без "квадратов", вы обнаружите, что застряли. Таких последовательностей не существует! Как насчет "бесквадратных" троичных последовательностей? Попробуйте увеличивать цифру за цифрой, и вы, вероятно, обнаружите, что ваш путь заблокирован в какой-то момент. Например, вы можете наткнуться на последовательность 0102010, которая не содержит "квадратов", но не может быть расширена без создания "квадрата". Многие другие троичные последовательности также приводят к таким тупикам. Тем не менее, норвежский математик Аксель Туе почти столетие назад доказал, что существуют неограниченные троичные последовательности без "квадратов", и он дал метод для их построения. Сердцем алгоритма является набор правил замены цифр:
0 > 12, 1 > 102, 2 > 0.
На каждом этапе построения последовательности к каждой цифре применяется соответствующее правило, и результат становится отправной точкой для следующего этапа. На рисунке 4 показано несколько итераций этого процесса.
Туэ показал, что если вы начинаете с последовательности без "квадратов" и продолжаете применять правила, последовательность будет расти без ограничений и никогда не будет содержать "квадрат". Совсем недавно внимание обратилось к вопросу о том, сколько троичных последовательностей не содержат "квадратов". Дорон Зейлбергер из Ратгерского Университета в статье, написанной в соавторстве с Шалошем Б. Эхадом, установил, что среди 3^n, n-значные троичные последовательности не менее 2^n/17 свободны от "квадратов". Уве Гримм из Амстердамского Университета несколько ужесточил эту нижнюю границу; он также нашел верхнюю границу и подсчитал все n-значные последовательности до n = 110. Оказывается, существует 50 499 301 907 904 способа упорядочения 110 троичных цифр, которые избегают всех повторяющихся шаблонов. Мне нужно будет выбрать один из них, когда я настрою свою картотеку без "квадратов".