Символично было бы, что моя третья статья на этом ресурсе, как то гармонировала бы с цифрой 3. 
Не скрою свой давний интерес к троичной тематике и даже разработке схем примитивных вычислительных устройств на этой основе.
Это дело любительское, но весьма интересное!
Ковыряясь у себя в папках со всякими интересными, мне лично, публикациями на эту тематику обнаружил статью из американского журнала(см.ниже). Хотел бы поделится идеями в ней озвученными. Возможно кому то это то же будет интересно, а возможно кого то оплодотворит на большое или маленькое научное открытие или схемотехническое решение или программный алгоритм какой, например эффективного сжатия и хранения информации. Как известно без оплодотворения дети не рождаются.
Недавно на одном авторитетном, лично для меня, ресурсе по технической тематике в основном увидел откровение что ключевые фигуры ИТ США 1970-х и 1980-х(а их там очень много и порой противоречивые весьма фигуры) пошли работать в сферу высоких технологий с идеей предотвратить отставание от СССР. Эта идея была весьма популярна после запуска Спутника. Если это правда то мне кажется что не только запуск Спутника мотивировал их в этом. Помимо прочего там ещё ставится интересный вопрос(обзор развития ИТ с подробностями за 30 лет с 70 по 90-й): почему за 30 лет кроме США ни одна страна в мире не смогла реализовать хоть какие то микропроцессорные, схемотехнические, "железные" реализации, идеи за исключением разве что Англии, которая к концу 80-х таки нарисовала свой ARM? Ни Европа, ни СССР, который на копирование тупо перешёл, ни кто либо другой? Вопрос интересный мне показался.
Но это касается периода в 30 лет. В этой статье охвачен больший период в котором США не такие уж пупы земли в этом аспекте. Что печально и по ныне наши ИТшники некоторые убеждены что не надо делать лучше, надо делать "как все". Типа не надо изобретать велосипед, он и так уже существует. Я с этим не согласен!
Эпиграф (от меня).
"Tertium non datur" или "третьего не дано" - утверждение выдвинутое стоиками и утвердившееся во всём и везде в этом мире. Но верно ли оно?
Парадоксальность материальной импликации, обретённая в условиях двузначности отношением необходимого следования, и тщетность всех попыток исправить положение изобретением строгих, сильных, релевантных, паранепротиворечивых и прочих импликаций неопровержимо свидетельствуют о неадекватности двузначной логики. Трёхзначность присуща следованию, определённому в силлогистике Аристотеля, против которого предназначался вымешленный стоиками "закон" исключённого третьего.
Категорически извратил аристотелево следование С.К.Клини, истолковав отношение "все X суть Y" как удовлетворяющееся при несуществовании X, ибо "смысл этот проще и потому полезнее". В результате его следование обрело парадоксы материальной импликации. Кэррол сказал бы: "Трёхзначная реальность стала двузначной химерой". Где же полезность?
Н.П.Бруснецов.
THIRD BASE
Третье Основание.
Люди считают десятками, а машины считают двойками — это в значительной степени подводит итог тому, как мы работаем с арифметикой на этой планете. Но есть бесчисленное множество других способов подсчета. Здесь я хочу предложить троекратное приветствие троичной системе - основанию 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 и его преемники были двоичными машинами!
Так получилось, что первый работающий троичный компьютер был построен по другую сторону Железного Занавеса.
Машина была разработана Николаем Петровичем Брусенцовым и его коллегами из Московского Государственного Университета и получила название Сетунь в честь реки, протекающей недалеко от университетского городка.
Прим. от меня.
Не только первый но и последний! Тем паче серийный! Ещё никто в "железе" не реализовал. Разве что какие эмуляторы на двоичной программируемой логике, опять таки, основе 2.
Между 1958 и 1965 годами было построено около 50 машин. Сетунь оперировал числами состоящими из 18 троичных цифр, или тритов, давая машине числовой диапазон 387 420 489. Двоичному компьютеру потребовалось бы 29 бит, чтобы достичь этой емкости; с точки зрения rw, троичный дизайн выигрывает от 54 до 58. К сожалению, Сетунь не реализовал потенциал базы 3 для уменьшения количества компонентов. Каждый трит хранился в паре магнитных сердечников, соединенных тандемом, так что бы они имели три стабильных состояния. Пара ядер могла содержать два двоичных бита, что составляет больше информации, чем один трит, и поэтому в данном аспекте троичное преимущество было достигнуто не в полной мере.
Прим. моё. По сей день это пока неразрешимая проблема - разработка элемента с тремя стабильными состояниями решает её. У автора чуть ниже об этом. Попадалась на глаза совсем недавно информация, что российские институты в кооперации с китайцами работают как раз над этим. Однако даже если брать современную схемотехнику, в которой с 70-х годов MOSFET'ы, или транзисторы с изолированным затвором, собой вытеснили всё прочее, то там в обычном инверторе 2 элемента идёт. В ячейках SRAM памяти минимум 6 элементов на один бит, в DDR - 1 элемент с конденсатором на бит информации. Но проблема в том что при считывании бита он теряется в ячейке и поэтому схемотехника усложняется его перманентным перезаписыванием. Общее количество элементов в DDR на один бит меньше чем в SRAM но больше чем 1 элемент на бит. Эта "дешевизна" обусловлена тем что в DDR обработка не бита, а целого байта происходит, а в SRAM можно с каждым битом по отдельности работать и перезапись не требуется. Т.ч. если применять схемотехнику двоичную к троичной на сегодняшнем этапе тут то же некоторый выигрыш получается элементарный. Не так давно компания AMD анонсировала разработку памяти на тиристорах. Ячейка на мосфете с конденсатором заменяется одним тиристором который не требует перезаписи. Но эта технология так и не реализовалась в массовом производстве из-за энергопотребления самого тиристора. Троичный тиристор с энергопотреблением не больше чем мосфет, и не более дорогостоящему технологическому процессу его печати на кристалле, было бы решением данной проблемы. Или ещё какие новые, до селе не виданные решения , может даже не на основе полупроводников, всё таки уже мы давно в мире нанотехнологий, а там уже физика процессов иная в самом полупроводнике на такой размерности. Сверхпроводимость и т.д.
Наряду с троичной арифметикой компьютер, построенный на базе 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 троичных цифр, которые избегают всех повторяющихся шаблонов. Мне нужно будет выбрать один из них, когда я настрою свою картотеку без "квадратов".
© Брайан Хейс
P.S. Эта статья была опубликована в ноябрьско–декабрьском номере журнала American Scientist за 2001 год. Автор статьи Brian Hayes. На сайте журнала не смог найти архивную копию. Документ находится у меня на компе в формате pdf т.ч. ссылку дать не могу кроме вышеописанной , косвенной ссылки на источник.
Перевод в большей степени яндекса, т.к. я не шибко силён в английском, но пришлось кое что переводить на русский логическим путём т.к. у автоматизированных переводчиков порой теряется суть или вообще извращается.
Помимо прочего обогатил статью своими примечаниями.
Комментарии
Унарная нотация, вот оно! Полагаю, что мир построен на унарной нотации, но поскольку мы - простительно, ибо по нужде - обобщаем, упрощаем и оптимизируем, вот и вылазят всякие парадоксы, закономерности и иррациональности. А в мире всё конкретно и уникально. Нет никакой "сути". Поэтому и нет проблем, всё работает.
Аж волосы на голове дыбом встали, как это глубоко! гы
"Унарная нотация" до меня то же долго въезжало. Я так понял что автор хотел сказать что это представление числа одними единицами.
Просто, как крайний пример привёл. Которым только одно число выразить можно. Но там оговорка, что это не относится к позиционной системе. Т.ч. степени к единице тут никак не подходят - всё будет единица. Он видимо хотел что то типа римской системы, то же не позиционной, изобразить. Или ещё какой более древней. Где чёрточками числа обозначали.
самое сложное в унарной нотации записать ноль и отрицательные числа :)
ничего сложного, просто уникальное количество единиц
Чисто интересно, сколько уникальных единиц требуется для представления нуля?
Очень мало!
Отрицательное -да, сложно. Но ноль без проблем. Просто 0 - начало. И далее всё количеством нулей выражать
Один унарный символ - 0. 00=1, 000=2, 0000=3 и т.д. Унарная нотация.
А отрицательно число или число со знаком или даже дробное число, с плавающей запятой, тут минимум два выражения нужно. Какое то условное количество 00-й означает - и +. Далее мантисса числа и порядок. Собственно в двоичной , компьютерной, системе так числа и представлены. Там только байт размерность принятую имеет из этой размерности исходят, в чистой математике чего то мудрить надо. Или наоборот , число с плавающей точкой проще математически чем "железно" представить тут. Как и отрицательное число. Знак ведь не цифра, так же как и дробь.
Один байт- 8 бит = 256 значений. Один униайт
= тогда 256 унит
Машинное слово на 248 ячеек увеличивается сразу. На каждую ячейку и её обработку минимум 1 элемент, для хранения, для простейшей логической операцией над словом ещё 512 элементов требуется. Ну и т.д.
Хотя тут даже инверсия логическая требует больше двух элементов на один унит. Если его инвертировать то только в представлении положительно и отрицательного нуля - больше никак. Короче знатный огород получится представлений числа в унарной нотации. Даже с технологиями в 1 нанометр калькулятор с одним арифметическим действием размером с холодильник получится, и это ещё сильно постараться надо будет в эти размеры всё уложить
Проще и размеры намного меньше, унарную нотацию сразу в двоичную нотацию впихнуть. Эмулировать т.с. И лучше всего эмулировать только ввод и вывод. Хранение и операции в двоичной нотации производить.
.
А где пятиричная система исчислений? Основанная на том простом факте что у человеков 5 пальцев..?:)
Если у Вас пять пальцев то могу предложить выражение для Вашей 5-иричной системы математическое. Даже могу калькулятор накидать в обычном браузере с переводом из десятеричной в пятиричную и обратно. Или сразу счёт в 5-иричной. Вы им будете пользоваться? если да - пишите. Предложение бесплатно только для перевода чисел, остальное за деньги
У меня два раза (так то четыре) по 5 пальцев, но активно пользоваться можно 5- это просто raid массив, чтоб не сбиться:))
У нас как припоминаю работали над компьютерами с троичной логикой в статье упомянутой -но все заглохло
А зачем нужна "экономность числового представления"? Если зачем-то нужна, эта нужность точно важнее других критериев?
Если бы я прогрессорствовал у дикарей, ещё не имеющих своей системы счисления, выбирал бы между девятичной и шестнадцатеричной системами. Первая проще, вторая красивее. О, можно поиздеваться и сделать первую для простонародья, вторую для жречества, пущай страдают переводя из одной в другую.
А троичная система - шлак и бред. Не нужна. И компьютеры на троичной логике мусор и не нужны. А уж какой диверсией стали бы системы хранения данных на троичной логике.
Это вопрос чисто технического удобства. Когда проще всего было реализовать бинарность (0-1), реализовали ее.
Допускаю, что на иной элементной базе оптимальный выбор может быть иным.
Никаких принципиальных преимуществ или иной логики этот выбор сам по себе не даст, это просто вопрос представления.
> Это вопрос чисто технического удобства.
Вот именно. Любая система с основанием большим, чем два, экспоненциально усложняет аппаратную часть но выигрыш в вычислениях если и даёт, то настолько небольшой, что ни малейшего смысла в таком железе не оставляет.
Для ручных же вычислений системы с маленьким основанием тоже неудобны. Объёмы текстов растут, сложность вычислений от того тоже растёт. Где-то между восьмеричной и шестнадцатеричной на мой взгляд и лежит золотая середина.
Нет. Третичная логика - основа квантового компьютера, который как общеизвестно не оставляет вычислениям на современных компьютерах никаких шансов. Это другая архитектура, требующая другого математического аппарата. Если бы не решение о том, что свою передовую кибернетику дешевле и проще похоронить и начать импортировать из-за рубежа, то первый квантовый компьютер был бы советским.
Вот для квантовых и используйте. Тезис про экспоненциальное усложнение, кстати, подтверждается ;)
> который как общеизвестно
Учёный изнасиловал журналиста.
Не, ну Сетунь-то не была квантовой, а это 1959 год. Однако уже тогда было показано что АЛУ компьютера на третичной логике как минимум в 1,6 раз производительней АЛУ на двоичной. Троичное слово в 1,6 раза короче двоичного и нафик не нужен разряд для хранения знака, поэтому операции выполняются во столько же и больше раз быстрей. И это без квантовых эффектов.
У меня сие с завидной регулярностью.
> АЛУ компьютера на третичной логике как минимум в 1,6 раз производительней АЛУ на двоичной.
Это пока то АЛУ на технологиях каменного века. Чуть дальше развились, уже начнёт проигрывать, и чем сложнее аппаратура, тем сильнее будет проигрыш.
> Троичное слово в 1,6 раза короче двоичного
Когда у тебя уходят ограничения на размер слова, это преимущество нивелируется, а возросшая сложность ВСЕГО кремния никуда не девается.
> У меня сие с завидной регулярностью
Ну вот. Научиться работать в троичной логикке можно и на бинарных вычсистемах. Делаешь эмулятор и вперёд, на покорение вершин. В любой системе счисления, какую захочешь.
Это не каменный век был, а передовые для 50-х годов прошлого века технологии. Недоказуемо, потому что никто не делал. Массовое производство памяти на двоичной логике было запущено раньше, её себестоимость в производстве падала по экспоненте, до тех пор пока двоичная память не стала по цене грязи.
Архитектурно они никуда не уходят. То что общая производительность позволяет путём чудовищных с точки зрения архитектуры накладных расходов использовать слово любого размера ничего не доказывает. Можно предположить, что при сопоставимой сложности троичное АЛУ давало бы большую производительность. Но возникает множество технологических вопросов, поэтому так это было бы или нет, мы уже не узнаем.
Да, можно. Кто же спорит? Вопрос накладных расходов на эмуляцию.
Нет, квантовый компьютер может быть реализован только в двоичной системе. И вот почему...
Если мы внимательно присмотримся к циферблату часов, то заметим, что стрелки на нём вращаются... по часовой стрелке! А как ещё могут вращаться стрелки?
Против часовой. А ещё? А больше никак! То есть, существует только два направления вращения. Туда и обратно, по часовой стрелке и против. Я даже специально запишу слово "два" с помощью цифры. И эта цифра будет... правильно, 2.
Но, может быть, два направления вращения существуют только на 2-мерной поверхности? Нет. В нашем 3-мерном пространстве их тоже только два. Итак, запоминайте. На 2-мерной поверхности вращение происходит вокруг точки, в 3-мерном пространстве вокруг оси... а в 4-мерном?
В 4-мерном вокруг плоскости, в 5-мерном вокруг некоторого 3-мерного многообразия... Ничего сложного. Просто ведь...
Но во всех пространствах или, как говорим мы, квантовые физики-теоретики, в любых многомерных многообразиях есть только два направления вращения - туда и обратно!
Ну-с, дорогие мои, что отсюда вытекает, так сказать, вытекает с неизбежностью падающего домкрата? Правильно, двоичная система!)
Монти Пайтона пересмотрели?
А теперь кое-что совсем другое. В квантовых вычислениях и третичной логике существует состояние в котором направление вращения не определено.
УИЖ. Квантовые вычисления вообще крайне мало похожи на вычисления на классических компьютерах.
Да. Из-за наличия третьего состояния законы булевой алгебры становятся неверными и им приходится создавать аналоги. Вместо закона противоречия - закон несовместности состояний, вместо исключённого третьего - полноты состояний и т.д.
Не порите чуши о том, чего не понимаете. Пожалуйста.
Всё в квантовых вычислениях определено. Если классический бит можно представить в виде клеточки с нарисованной в ней 1 или 0, то кубит будет выглядеть как множество таких клеточек с проставленными в них 0 и 1.
Можете для удобства представить кубит в виде квадрата 100х100 клеток. И в каждой из них будет либо 0, либо 1. И при сложении двух таких кубитов в квантовом регистре получается 2-мерная матрица...
Её строка будет состоять из 10 000 клеточек, а её столбец... правильно, тоже из 10 000...
Итóго, у нас получится... 100 000 000 клеточек, с проставленными в них 0 и 1. И это далеко не предел. Отнюдь!)
Вы мне сообщаете про представление, а я Вам толкую про математический аппарат. Вы рассказываете что "по физике" третье состояние в существующих реализациях не выражено. Не, ну ok. Это неудивительно, с учётом того что весь инструментал работает на обычных компьютерах.
Ладно. Подождём ещё кого-нибудь... кому эта тема будет интересна.
Ну, а нет, так нет... )
-стрелки вообще не вращаются
-минутная и часовая вращаются в противоходе
-стрелки вращаются то в одну, то в другую сторону, как им вздумается
-стрелки вращаются, но невозможно определить в какую сторону
Аргумент какой то слабенький. Тем паче если мы присмотримся к циферблату часов то заметим что часы вообще в 60-и ричной системе счисления представлены.
Ключевая фраза во всём этом... эмм... непотребстве:
- Произведём измерение вдоль избранной оси...
Вдоль избранной, понимаете?! Какая тут система, 60-тиричная или ещё какая, - по барабану!
Ну-с, а сколько направлений у оси? Всего лишь два, не правда ли?)
Парадокс Ахилла: секундная стрелка никогда не догонит минутную, а минутная - часовую.
Вывод: у древних греков никогда не было часов? Вывод неверный. У Зенона их не было.
Стрелка вектора состояния по такому параметру как спин, действительно, описывает поверхность сферы. И поэтому, чтобы определиться с направлением спина, мы должны выбрать плоскость сечения этой сферы, проходящую через её центр...
Впрочем, и этого тоже будет недостаточно. Ведь, на плоскости можно провести бесконечное число осей вращения. Ну, почти бесконечное...
Поэтому выбираем конкретное направление. Направление оси, разумеется. А уж этому направлению оси будут соответствовать два направления спина, противоположных друг другу. Просто ведь...
Я недаром провёл экстраполяцию от 2-мерной поверхности до 5-мерной. Да, не удивляйтесь. Пространство и поверхность это одно и то же. Ну, почти...
Итак, каким образом частица может вращаться сразу вокруг всех возможных осей вращения, коих бесконечное множество? Оч. просто. Если частица представляет из себя 5-мерное многообразие, то она по определению будет вращаться вокруг 3-мерного многообразия.
То есть, вокруг всех возможных осей вращения одновременно. Просто ведь... )
Если бы часы были сферой, то секундная стрелка не только могла бы догнать минутную, но и зайти ей во фланг. И сбить с пути...
Блин, Ленка куда-то пропала... (
Тоже не знаю...
Я тут вывел её образ в рассказе. Она в составе девичей штрафной... тьфу, ты... то ись, штурмовой роты зашла в тыл к укропам, в районе Бахмута.
Ну, как водится, девчонки быстро перестреляли сидевших в окопе укров. Кого в затылок, а кому и меж глаз пулю вогнали. А укроповского командира захватили живьём и допросили. С пристрастием...
Ну, а потом Ленка перерезала ему горло. Сначала, вообще, хотела голову отрезать... Но Танька завизжала, типа мол, забрызгала мне камуфляж... сучка киевская. Ну, Ленуська и не сдержалась... )
Кровавые у вас рассказы...
Ой, да ну! Скажите тоже... Да разве ж это кровавые?
Вот у Николая Васильевича да, кровавые! Мне до него ещё расти и расти... )
Николай зашёл по колено в болото, поднял правую руку вверх и замер прислушиваясь. Все затихли.
-- Витя, если Вий покажется, в горло ему стреляй, -- Виктор кивнул, перебежал и занял позицию у полунилого пня.
-- Санек, постарайся джавелином ему по яйцам попасть... не промахнись, а то нам тут всем крышка.
-- Будет сделано, Михалыч, -- он вскинув джавелин на плечо и прицелился.
-- Захар! Давай! Петарду кидай! -- скомандовал Николай.
Бахмутское болото внезапно запузирилось и забулькало. В ночное небо вырвались огненные столбы.
-- Что это Михалыч!!
-- Это шаровая! Ложись!
Но было уже поздно...
Исследуя математическую модель кубита мы обнаружили много интересных вещей. Например, наряду с вышесказанным, спиновые состояния кубита не связаны между собой отношениями причины и следствия.
То есть, если мы начнём выводить их на устройство вывода, то они будут появляться там в любой последовательности, выбранной совершенно случайным образом. Что это? Что это за пространство состояний такое?
Это неметрическое пространство. И в нем отсутствуют такие понятия как время и расстояние. И тем не менее, мы с вами только что смогли окинуть его взглядом. Ну и да, можно сказать, что мы заглянули в будущее... и увидели, что между его состояниями отсутствует причинно-следственная связь.
Ну-с, вот вы только что и пощупали руками и увидели глазами то, что нельзя ни потрогать, ни увидеть... )
Подозрительно всё это. Растояние корреляции должно быть. Более того, фотоны спутанными быть не могут. Они носители, индикаторы спутанности двух электронов в экспериментах Аспе. Регистрируются они в момент времени и в точке пространстве.
Как взаимодействуют между собой кубиты в квантовом регистре? Интересный вопрос...
По крайней мере, мы своими глазами увидели, как каждая клеточка с записанными в ней 0 или 1 из первого кубита совершает операцию сложения с каждой клеткой из второго кубита. Да, это число сочетаний из комбинаторики... Или нет?)
Как реализованы состояния кубита не на листе в клеточку, а в нашей реальности? Окей. Возьмём ваш любимый листок в клеточку и вырежем из него наш квадрат 100×100 клеток и... натянем его на сферу. Сферу Блоха. При достаточной сноровке это может получиться. Тем более, если квадрат был нарисован на тонком листе резины...
А что, если попробовать натянуть каждую клеточку в отдельности? Тогда у нас получится 10 000 сфер с натянутыми на них клетками. И все они будут ничем иным, как 3-мерными проекциями одной и той же гиперсферы...
Сколько получится окружностей при пересечении плоскости сферой? Много... Кстати, сам вывод состояния кубита на устройство вывода можно сравнить с прохождением сферы через плоскость. И каждой окружности будет соответствовать своё состояние...
И единственное, что для этого нужно, это наличие... тьфу, ты... то есть, постулирование наличия дополнительных измерений. Примерами которых может являться... эмм... да что угодно! Например, диэлектрическая проницаемость... или энтропия... я уж не говорю про гравитацию.)
По секундной стрелке не могут вращаться? Или по минутной? Какие то ассоциации непродуманные.
А где суперпозиция? Куда она из вашей би-сексуальной схемы делась?
Если Вы заранее определили в какую сторону вращение пойдёт, то тут никакого квантового эффекта уже нет. Состояние неопределённости - 3-е и самое главное состояние. Т.ч кубиты тут отдыхают. Кутриты рулят.
На кубитах или ещё чём двуликом можно, бесспорно, и расчёты вести и представлять непредставимое, но это всё равно что из Медведково в Лианозово через Чертаново ехать. Когда есть путь куда более короткий.
Вы, я вижу, учебник КМ скурили. А его читать нужно было. :)
Собссно, основание квантовой системы - количество чистых состояний. Суперпозиция чистых состояний - это не третье состояние, а именно суперпозиция между ними, суперпозиций - бесконечность (в чём и одна из выгод при вычислениях, и проблема при выводе результата заодно).
А любая неортогональность чистых состояний - сразу избыточность аппаратуры, проблемы с ошибками и их коррекцией и т.п. бессмыслицы без выгод.
Ну так, а как это представить в цифре? Вы тут пишете "суперпозиция" не то , а сё. Стало быть её надо как то и чем то представлять. Я написал, что это состояние неопределённости! Состояние определённости это уже определённое состояние.
Если суперпозиция у Вас ничем не представлена тогда из вашего текста её уберите! А если чем то хотите представлять то трит тут намного логичнее чем бит получается.
Иными словами спин влево -1, спин вправо +1, 0- состояние неопределённости. В один бит это не впихуется
, очевидно, никак, стало быть огород городить в двоичной системе надо будет. Превращать трёхзначную реальность в двузначную химеру!(с)см. Эпиграф.
В дискретных числах суперпозиция непредставима. Даже соотвествующая суперпозициям приведённая плотность вероятности выражается только числом бесконечной точности.
Конкретным числом бесконечной точности, а не просто третьим состоянием. 0.837212546523497354675663454723659659752353929523... находится между 0 и 1, но это вполне конкретное число. Какой смысл представлять это число в виде -1, если из -1 это число обратно всё равно не получится?
Квантовый компьютер может иметь троичную основу, как пример - спин, чистыми состояниями для которого будут единичные проекции на некие ортогональные оси x,y,z. Просто это очень неудобно и в смысле физической организации, и - несмотря на то, что оси ортогональны, такие чистые состояния будут неортогональны друг другу. Что неудобно с вычислительной точки зрения.
Но у этих чистых состояний точно так же будут суперпозиции - состояния между 0 и 1 или между 1 и -1.
В общем, бессмыслица.
Ну вы то как то представляете её, словом "суперпозиция". Почему нельзя цифрой или символом её представить?
..........
Число тут никакое не при чём. Числа либо цифрами либо символами представляются. Представляется даже бесконечность или ноль - вполне себе непредставимое число.
Во-первых, потому что весь смысл квартового компьютера в том, чтобы в суперпозиции во время всех вычислительных эволюций находилась вся когеретная квантовая система. В процессе вычислений КК все кубиты системы описываются одной волновой функцией и представляют из себя одну сущность, принципиально неприводимую ни к какой классической. Собссно, без этого КК - бессмысленно сложный аналоговый компьютер. Нет смысла в 1-кубитном КК, а вот когенентная на время вычислений система из 1000 кубит - это уже сила, на некоторых типах операций превосходящая суммарную вычислительную мощь человечества в квинтиллионы раз. Фишка именно в когерентности, нельзя рассматривать кубиты по отдельности.
Во-вторых, потому, что когда приходит время вывода результата из когерентной квантовой системы в классическую, каждый бит (трит, квартет - неважно) чистого состояния получает своё значение с какой-то вероятностью (согласно оператору и набору чистых состояний). Вероятность - аналоговое значение, нет никакого смысла представлять его какой-то цифрой. Вообще никакого, это бессмыслица, абсурд.
Как вы представите миллионнобитное значение одним битом? или тритом (если на них у вас клин)? Да никак.
Как можно представить себе квантовую суперпозицию? Например, в виде монеты. На одной стороне которой решка, а на другой - орёл...
Теперь ваша задача научиться управлять вероятностью выпадения решки или орла. Окей, научились...
И в результате, например, тысячи испытаний у вас стабильно выпадает 765 раз орёл и 235 раз - решка... Берём вторую монету и проделываем с ней все те же самые процедуры. В смысле, учимся управлять её вероятностью. В результате у нас получилось, например, 673 раза выпал орёл и 327 раз - решка...
А потом выполняем операцию сложения, согласно принятым правилам. Да, складываем каждую решку и орла первой монеты с каждой решкой и орлом второй монеты. В результате у нас получится 1000 × 1000 = 1000 000 результатов.
Сколько вам понадобится времени, чтобы выполнить миллион операций? А квантовый компьютер сделает это за то же самое время, за которое классический выполняет одну операцию!
Как это у него получилось? А у него уже были записаны все эти тысячи состояний первой и второй монеты. А вот вам, чтобы узнать эти состояния, потребуется тысячу раз подбросить первую монету и тысячу раз - вторую монету.
То есть, если хотите, квантовый компьютер конвертирует время в пространство. И если в классическом случае эти состояния разделены временными отрезками, то в квантовом - пространственными.
Где же находится это пространство? А вот это уже тема для отдельного разговора... )
Страницы