В теоретической математике существует немало открытых проблем, которые пусть и не известны широкой публике, но всё же “широко известны среди специалистов”, то есть, достаточно знамениты, поскольку есть канонические списки (“Коуровская тетрадь” и др., не важно). Для заметной части из этих проблем и связанных задач можно было бы отыскать контрпримеры (и даже просто – примеры), используя современные возможности по оптимизированному перебору текстов компьютерных доказательств. В этом не только нет ничего особенно удивительного, но даже нет и проявления какого-то “нового интеллекта”: схема известная – перебирай себе тексты программ, проверяя автоматом корректность записи (см. историю проблемы о четырёх красках и так далее). Если бы, конечно, универсальным образом работал и перебор, и методы перевода на язык систем компьютерного доказательства нужных наборов теорем. Теоремы, впрочем, интенсивно переводят.

То есть, это самое реальное применение для знаменитых “LLM с нейросетками” на ближайшее время, при котором они могли бы оказаться очень эффективными для математических исследований. Попытки такие, вроде как, предпринимались, потому что подход достаточно очевидный, однако массового результата пока что не видно.



Комментировать »

Продолжаем тему “про алгоритмы“, на примере циклов и компиляторов. Запись алгоритма на языке высокого уровня (ЯВУ) – это некоторый пересказ того, что должно выполняться вычислителем. На то он и язык высокого уровня. При этом, обычно, вычислителем исполняется не запись на ЯВУ, а некоторый результат преобразования компилятором. То есть, алгоритм, казалось бы, один. Но, во-первых, может быть много разных записей этого алгоритма на многих разных языках. Даже если удалось удачно определить, что означает фраза “две программы реализуют один алгоритм” (отдельная проблема), то, при минимально содержательном определении, машинное доказательство того, что разные записи соответствуют одному алгоритму – составит большую трудность (в общем виде соответствующее сравнение вообще неразрешимо, но это другая история, а несложные конечные автоматы, обычно, как-то эффективно сравнить всё же можно). Трудности на этом направлении гарантируют, что даже если реализован некий автоматический перевод с одного ЯВУ на другой, это вовсе и не означает, что результат не менее автоматического анализа переведённой программы применим к программе исходной.

Другими словами, если у вас есть добротный анализатор для языка Fortran (для языка, не для алгоритмов), то он вовсе не обязательно эффективен для программ на Haskell, которые транслированы (ну, предположим) в код на Fortran: проверяться всё равно будет Fortran-программа. Это сильно сужает возможности по созданию полезных универсальных “анализаторов кода на ЯВУ”.

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

Предположим, что на процессоре “Имярек-7” команда MOV (“копирующая/перемещающая какие-то данные”) не просто сама по себе Тьюринг-полная (как в x86), но ещё и содержит “особенность” реализации, приводящую к тому, что число 0xFFFFFFFF превращается в 0x0, если сделать два MOV подряд из ОЗУ в регистр REG1. Поэтому, чтобы какие-то детали гарантировать относительно программы и реализации алгоритма, нужно в рассмотрение включить и аппаратные особенности. Сделать это автоматическим способом непросто. Отчасти поэтому-то и появляются всякие разные трансляции в “байт-код”, пригодный для исполнения “песочницей” (например, “Java-машиной”, если хотите): в такой конфигурации можно построить какие-то формальные описания и для языка, и для “машины”, которая его интерпретирует. Можно показать, что тут, при следовании некоторым принципам, всё разрабатывается безопасно (и это, действительно, так, но далеко не в общем случае).

Если же что-то всё же пошло не так, то оно пошло из-за дефекта реализации “машины”, а эта реализация находится за пределами модели. Это удобное сужение темы: если у вас код вылезает из песочницы, то проблема существует над песочницей, а не в ней; песочница хороша по определению: существовала бы проблема в ней – вылезать и не требовалось бы, да.

Представьте, что сложную схему отношений между записями алгоритмов, разными языками высокого уровня, компиляторами и аппаратурой зарисовали в виде графа, где направленные рёбра – это стрелки, обозначающие преобразование кода. Например, перевод с одного ЯВУ на другой. Или перевод в машинный код. Или перевод в подмножество состояний конечного автомата, соответствующего процессору. Тут за каждой стрелкой скрываются целые наборы “схлопывающих” и забывающих отображений, при которых различные способы представлений на стороне начального узла все переводятся в единственный способ на стороне узла конечного (такое вот “ядро” отображения). Например, циклы for, while, do – все схлопываются в сочетание операторов if, потому что только так позволяет записывать целевой язык. Тогда базовые логические преобразования, записываемые формально, могут и совпадать, но вот большое количество возможностей по внесению особенностей и ошибок в исходный код – останется вне пределов доступности для того или иного анализатора, схлопнувшись, что называется, до неразличимости.



Комментировать »

Как понять, что факторизация числа 15 не может ничего говорить о реализации квантового алгоритма Шора? Понять это несложно: один из делителей числа 15 должен быть меньше 4 (потому что 4^2 == 16), единица не рассматривается по условиям задачи, и это не 2 (потому что только нечётные подходят). Так что любой процесс поиска, каким бы аналоговым он ни был, если вообще сходится, то неизбежно попадёт в 3, что и будет верным ответом.

Заметьте, что ещё и 5 = 3 + 2, а простых чисел, меньших 15, только шесть: поэтому, учитывая, что умножение здесь коммутативно (это очень важно для квантовых алгоритмов), число 2 отбрасывается, а схема поиска расщепляется на пары, то, в самом худшем случае, вероятность, что аналоговый аппарат, состояния которого переключаются по возможным узлам дерева, промахнётся – меньше трети. (На практике, ещё раз, для промахов там просто нет места.)



Комментировать »

Недавняя записка про оптимизацию циклов и микроконтроллеры иллюстрирует весьма важный момент, связанный с пониманием алгоритмов, записи алгоритмов и реализаций этих алгоритмов. Не менее рельефный пример в этом же направлении касается базовых логических операций и понимания записи формул. Речь про вопрос из области логики, логических выражений: является ли P и ¬¬P – одним и тем же? Даже разработчики-программисты нередко говорят, что “да, является”.

Знак “¬” – это логическое отрицание, проще говоря – “не”, или “!”, как будет во многих привычных языках. То есть, казалось бы, тут, во второй части, написано, что “не-не-P”, а тогда, если P имеет значение TRUE, то “не-не-P” тоже TRUE; то же верно и для P == FALSE. Понятное двойное отрицание, поэтому, что P, что ¬¬P – разницы нет: одно и то же. Это, впрочем, не совсем так.

Использование дополнительной “закорючки” (“¬”) позволило реализовать два способа записи, которые точно отличаются. Как способ записи, как “формула”, “P” и “¬¬P” – сильно разные вещи. Посудите сами: во втором случае на два “знака-закорючки” больше; кроме того – для выполнения “сокращения” нужно ввести дополнительное правило, по которому двойное отрицание вообще схлопывается, а чтобы это правило сработало, потребуется его внести “в набор допустимых операций” и применить, то есть, продумать и оптимизировать, даже если не сравнивать именно две записи. Так что “¬¬P” приносит с собой много разного, отсутствующего в “P”.

Понятно, что тут очень многие соглашения вынесены за скобки, но, тем не менее, это хороший пример базовых свойств процесса оптимизации. Да, компилятор мог бы заменить ¬¬P на P. Почти что то же самое компилятор и проделывает, когда заменяет запись цикла, тело которого не вносит изменений в результаты работы фрагмента кода, на простое присваивание:

b = 14; 
for(a = 0; a < 8; a++){ 
 b = b + a;
} 

заменяется на эквивалентное

b = 42;

(или это не эквивалентная замена?)

Вообще, запись алгоритма, содержащая определение цикла, описывает повтор неких операторов/команд, но не определяет, как этот повтор должен реализовываться на оборудовании. В принципе, тело цикла можно прямо выписать в качестве повторений команд, это известный приём оптимизации, он так и называется - "развернуть циклы". Очень часто, будучи применённым к программе на языке высокого уровня (ЯВУ), приём даёт заметный прирост производительности. Почему? Потому что исчезли накладные вычислительные расходы. При обычной обработке представления цикла на ЯВУ - появляются необходимые машинные команды, соответствующие "записи" цикла, а процессор вынужден их исполнять. Команд может оказаться неожиданно много: например, потребуется сложная обвязка для реализации обработки переменной цикла.

Занятно, что автоматическая "обратная оптимизация", по размеру кода, когда повторяющиеся логические блоки сворачиваются в циклы, - представляет трудность. Тут, впрочем, уже недалеко и до алгоритмической неразрешимости.



Комментировать »

Где именно в криптосистеме электронной подписи ECDSA “работает” эллиптическая кривая?

Посмотрим, для начала, на значение подписи, которое состоит из двух параметров – (R, S). Здесь R – это координата X точки на используемой эллиптической кривой, а именно, X-координата точки k∘G, где G – точка кривой, называемая генератором (зафиксированный параметр криптосистемы), а k – секретное уникальное значение (ECDSA nonce). Запись k∘G, – “умножение на скаляр”, – означает повторное сложение точек: G⊕G⊕G⊕…⊕G, где G встречается k раз, а “⊕” – обозначает операцию в группе точек кривой, то есть, сложение точек. (Умножение тут лучше было бы записать [k]G, например, но это детали.)

На значение k накладываются различные ограничения, но это всего лишь натуральное число (конечно, так можно сказать про всё, что встречается “в компьютерах”). Структура кривой такова, что есть пары точек с совпадающими X-координатами, но различными Y-координатами. Этот момент нередко используется в атаках на реализации ECDSA. В данном случае – R это именно X-координата.

Эллиптическая кривая непосредственно использована для вычисления одного параметра подписи – R, который, впрочем, сразу “превращается” из точки, как кортежа значений, задаваемых дополнительной структурой уравнения кривой, в единственное число.

Нетрудно заметить, что здесь, в процессе вычисления R, не использовано никаких значений, связанных с подписываемым сообщением или с секретным ключом – эти элементы пока что даже не упоминались. Параметр R служит в качестве опорного значения, необходимого для проверки подписи – к R должно сойтись значение после “невидимых сокращений”, заложенных в уравнение проверки подписи.

Это основная математическая идея ECDSA: базовое уравнение так устроено, что части структуры преобразования, вынесенные наружу в составе публичных значений, сокращаются, если ключ проверки соответствует подписи (и параметрам), но не сокращаются в прочих случаях.

Сокращающиеся структуры не видны, а вычислить их, – то есть, обратить, – по открытым значениям и параметрам, сложно. Концептуально это напоминает, например, RSA, где внутри открытого ключа всегда содержится структура, связанная с разложением на простые множители, благодаря которой криптосистема работает. Тут необходимо обратить внимание на то, что, во многих практических реализациях, значение k может вычисляться с использованием и подписываемого сообщения, и секретного ключа – например, так делается в схеме детерминированной ECDSA. Но “классическая” ECDSA такого, вообще говоря, не требует. Это, впрочем, один из самых проблемных моментов реализаций данной криптосистемы – так, если третья сторона знает параметры генератора псевдослучайных чисел, который использовался для получения k, то эта третья сторона без особых трудностей может вычислить секретный ключ по значению подписи и подписанного сообщения (см. ниже).

Итак, эллиптическая кривая, заданная для ECDSA, использовалась для вычисления R. Где ещё встречаются операции с точками? Прежде всего – вычисление открытого ключа. Открытый ключ в ECDSA это точка на кривой, а получается он из секретного значения d путём умножения генератора: Q == d∘G. То есть, d – целое число. Принцип эквивалентен вычислению r. Однако, в отличие от r, открытый ключ Q повсеместно записывают как пару координат (X,Y), но это только способ записи, потому что достаточно сохранять X и один “бит знака” для Y.

Вторая часть подписи ECDSA – параметр s. И значение этого параметра вычисляется уже без использования операций с точками кривой. Уравнение для s следующее:

S == k^(-1)*(H + Rd)

– здесь, кроме уже определённых k, R и d (d – секретный ключ), используется значение H – это и есть подписываемое сообщение (технически, это значение хеш-функции от сообщения).

Все значения в данной формуле – это натуральные числа (даже k^(-1)), а не точки. Поэтому тут использованы другие значки для обозначения операций: “+”, “*”, “^(-1)” – это “обычные” операции сложения, умножения и взятия обратного по умножению. “Обычные” в кавычках по той причине, что вычисления проводятся по модулю некоторого числа. То есть, это привычная арифметика остатков. Положительное число, по модулю которого проводятся операции, это так называемый порядок группы точек кривой. Можно считать, что порядок – это количество доступных для вычислений точек кривой. Порядок обозначают, например, P, а тот факт, что это арифметика остатков “по P” записывают как (mod P). Так что свойства кривой тут участвуют только косвенно. Взятие обратного по умножению – k^(-1) – это нахождение такого числа, которое даст 1 (mod P) при умножении на k. Так как вычисления выполняются (mod q), то k^(-1) тоже будет целым числом. Пример: 4*2 == 1 (mod 7) – так как 8/7 – даст остаток 1. Обратите внимание, что все вычисления дальше – тоже (mod P), но отдельно этот момент упоминаться не будет, так как, для практических целей ECDSA и для простого P, свойства вычислений совпадают с привычными операциями в рациональных числах (кроме сложения точек кривой).

Раз это обычная арифметика, то и по формуле для S нетрудно увидеть, что если известны k, H, R, S, то легко вычислить секретный ключ d – просто перепишем уравнение относительно неизвестной переменной d. Значения H, R, S – публично доступны: первое из них это подписанное сообщение, а два других – сама подпись. Никаких “хитростей” эллиптической кривой тут уже не задействовано, поэтому и никакие особенности арифметики эллиптических кривых конкретно на этом направлении криптосистему не защищают. (Более того, если известно не точное значение, но какие-то дополнительные свойства k, то уравнение S можно превратить в неравенство, составить набор “приближений”, который позволит найти приближённое значение для секретного ключа, чтобы потом быстро подобрать его точно по значению открытого. Но это тема для другой записки.) Итак, при вычислении S операции на эллиптической кривой не используются.

Проверка подписи в ECDSA использует следующее уравнение:

C == (H*S^(-1))∘G ⊕ (R*S^(-1))∘Q

– обратите внимание, что тут разные обозначения операций, чтобы можно было различить операции с точками и операции с числами; а значение Q, – открытый ключ, – это d∘G. Работает вся эта схема потому, что, из-за свойств сложения в группе точек кривой, можно операцию сложения точек ⊕ спустить в натуральные числа, вот как: 3∘G ⊕ 5∘G == (G⊕G⊕G)⊕(G⊕G⊕G⊕G⊕G) == 8∘G. При этом, если подставить вместо S формулу вычисления S (см. выше), то в правой части сократится всё, кроме k∘G. Получим, что C == k∘G, а X-координата C должна совпасть с R, если, конечно, подпись верна и вычисления верны. И здесь эллиптическая кривая используется непосредственно для вычисления итогового значения, а именно – умножение на скаляры точек G (генератор) и Q (открытый ключ), сложение получившихся точек.



Комментировать »

Несколько дней назад появилась работа (Yilei Chen), предлагающая квантовый алгоритм для быстрого (“за полиномиальное время”) решения задач теории решёток, на сложности которых основаны оценки стойкости многих современных постквантовых криптосистем. Квантовый алгоритм – это алгоритм для гипотетического квантового компьютера, то есть, дважды теоретический. Однако, в данном случае, как раз этот факт и выглядит особенно занятно.

Почему эта тема популярна? Если хотя бы теоретическое описание алгоритма верное и если его удастся развить до параметров практических версий задач (этого пока что нет, о чём прямо написано в исходной работе), то многие суперсовременные криптосистемы из класса “постквантовых” – не просто сразу потеряют постквантовую стойкость, но, возможно, даже станут менее стойкими к квантовой атаке чем, скажем, классическая RSA. Конечно, тут заведомо присутствует очень много “если”, и это всё гипотетические рассуждения. Однако и стойкость соответствующих постквантовых криптосистем к атакам на классическом компьютере – отдельный, всё ещё не очень хорошо исследованный, вопрос.

Понятно, что в статье обнаружатся ошибки и она потребует, как минимум, уточнений. Так, сегодня опубликована записка (Omri Shmueli), указывающая на недостижимые значения параметров, которые использованы в доказательстве корректности алгоритма. Это, впрочем, только добавляет арифметической занимательности, поскольку доказательство недостижимости основано на оценке количества простых чисел, меньших заданного. Дело в том, что описанная версия алгоритма, для корректной работы, требует построения набора из некоторого количества попарно простых натуральных чисел, меньших заданного порогового значения – но для определённых значений параметров таких чисел может не найтись в нужном количестве, поскольку не хватит простых. Если алгоритм нельзя исправить (это ещё тоже не факт) и это удастся доказать, то может даже так оказаться, что постквантовая стойкость криптологических задач теории решёток зависит от количества простых чисел, меньших заданного порога. А это весьма сильное и интересное ограничение. (Но, конечно, вряд ли это так.)

(Update, 13/10/2024: в исходной работе довольно быстро обнаружилась критическая ошибка и автор пока не нашёл способа эту ошибку исправить. Из этого не следует вывод, что “задачи на решётках” обладают строго доказанной стойкостью к “квантовым атакам”.)



Комментировать »

В марте довольно много писали про новую атаку на SHA-256, “с обнаружением коллизий”. Вообще, тут нужно отделять академические атаки от практики, условно говоря, всяких биткойнов: в исходной работе (“New Records in Collision Attacks on SHA-2”, Li, Liu, Wang) речь идёт про академические атаки на урезанную “функцию сжатия” (см. ниже) из состава SHA-2 (SHA-256 – это разновидность SHA-2), да ещё и со специально подобранным предыдущим состоянием. Это общепринятый подход к исследованию стойкости хеш-функций, результат существенно лучше предыдущих достижений, но нужно учитывать, что он не обязательно приводит к практической атаке на полную хеш-функцию. В статье сказано именно про “практическую атаку”, это верно, однако это разная “практика”.

Возьмём в качестве примера SHA-256 и одну из практических (в академическом смысле) атак, представленных в упомянутой выше работе. Ядром схемы хеш-функции SHA-256 являются преобразования, соответствующие симметричному шифру. Повторно выполняемые раунды преобразований шифра, внутри хеш-функции, и образуют так называемую “функцию сжатия” – это важнейший элемент. Входной текст для преобразования в SHA-256 разбивается на блоки. Блок – это последовательность байтов, соответствующая разрядности функции, здесь – 256 бит или 32 байта. Блоки обрабатываются функцией сжатия, внутри которой выполняется заданное количество раундов – то есть, повторное применение одних и тех же преобразований, в цикле, к обрабатываемому блоку. Далее речь будет идти только про один блок, а не про полный входной текст.

После каждого раунда, блок, в результате применения преобразований, изменяется и потом снова подвергается тем же преобразованиям, которые опять изменяют блок. Эта комбинаторная часть позволяет добиться нужного разрежения для отображения входных блоков в выходные значения. Штатная схема SHA-256 использует 64 раунда в функции сжатия. Атака, о которой идёт речь, работает для 39 раундов (обратите внимание: с подобранным начальным состоянием – это очень важный момент).

Что это означает? Это означает, что исследователи нашли и предъявили кортеж из трёх конкретных значений (чисел или массивов байтов – как хотите), которые, будучи подставленными в урезанную до 39 раундов сжатия версию хеш-функции SHA-256, дают одинаковый результат. Одно из этих значений – это начальное состояние, устанавливаемое перед вызовом функции сжатия внутри урезанной SHA-256. То есть, при штатной реализации SHA-256 – этим состоянием либо был бы предыдущий обработанный блок, либо начальные константы из спецификации SHA-256. Два других упомянутых значения – это различающиеся в некоторых байтах входные блоки. Обработка этих блоков при указанных, весьма строгих, условиях – даёт коллизию. То есть, академическая “практическая” демонстрация, с конкретными числами. Это вполне себе строгий и разумный способ анализа стойкости преобразований. В данной науке это называется SFS-коллизия (от Semi-Free-Start). Но, опять же, очень далеко от демонстрации реальной, практической, “уничтожающей” коллизии SHA-256, то есть, демонстрации двух различных входных текстов, дающих одинаковый результат хеш-функции. (Что, конечно, не отменяет заметного продвижения.)

Сколько раундов для функции сжатия вообще важны? Важны все раунды, указанные в спецификации. Каждый раунд очень важен и блокирует атаки, успешные для урезанных вариантов. Раунды именно для этого и служат. Потому что, если значение хеш-функции изменяется даже только в результате последнего раунда, то на выходе всё равно получаются разные значения и, строго говоря, коллизии нет (но может быть “почти коллизия” и т.д.).

Естественно, обнаружение точек совпадения для уменьшенного количества раундов нередко даёт инструменты для взлома всей хеш-функции целиком. Именно поэтому академические атаки на примитивы с урезанным количеством раундов – важнейший инструмент. Однако, является ли тот факт, что коллизия найдена для более чем половины количества раундов, автоматической гарантией успешного применения того же метода к, предположим, половине оставшейся половины? Нет, совсем не является. Методы тут развиваются, так сказать, полностью “нелинейно”, так что непреодолимое вычислительное препятствие может возникнуть хоть бы и на каждом следующем раунде – потребуется полностью переделать метод атаки. Собственно, это очередное улучшение атак на SHA-2 как раз построено на новых методах, если сравнивать с теми методами, которые использовали для атак на MD5 и пр.

Конкретный пример, взятый из исходной работы: для 39 раундов SHA-256, при заданном начальном состоянии, получаются совпадающие значения для разных входных блоков (выдача программы, прилагаемой к работе):

431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d
431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d

Можно было бы предположить, что раз точка совпадения найдена, то и дальнейшие раунды дадут одинаковые результаты. Но это далеко не так – состояние хеш-функции шире, чем конкретный результат преобразования блока. Так, если в той же программе указать 42 раунда (всего на три раунда больше), то значения уже заметно разойдутся:

d33c0cff 17c9de13 21f528f0 3362e217 563f1779 521a1b9c df062e86 19fb5973 
105d6c34 43ceb0ad 120ba1a0 3362e217 d6dd86e0 7da567b5 cf1ca736 19fb5973

Это, ещё раз, никак не уменьшает ценности результата для 39 раундов, но показывает, что для полной SHA-256 всё, – пока что, – хорошо.

Криптографические хеш-функции отображают сообщения произвольной длины в блоки фиксированной длины, так что, математически, коллизии там есть по определению. Другое дело, что если хеш-функция хорошо отображает множество входных текстов в, скажем, 2^256 выходных значений, то о коллизиях “на полном переборе” можно не особенно задумываться: мало кто может создать и записать даже 2^128 текстов. Атаки с обнаружением точек совпадения в функции сжатия как раз, потенциально, выявляют дефекты отображения, которые могут позволить найти коллизии без необходимости полного перебора. А возможно, что и позволят найти способы решения гораздо более сложной задачи вычисления прообраза, – то есть, подбора входного текста по значению хеш-функции.



Комментировать »

Картинка из прошлогодней записки про таблицу подстановок:

S-boxes

С чем связана такая геометрия верхней части? Прежде всего, с тем, что каждая строка там – это уменьшение “неопределённости” в два раза. И действительно: картинка состоит из значений байтов, повёрнутых вертикально, то есть, это таблица, в которой верхняя строка соответствует старшему биту байта. Последовательное увеличение значений байтов, справа налево, с использованием типового кодирования (это важная оговорка), означает, что половина клеток-пикселей старшего бита заполнена нулями, половина – единицами.

Нули и единицы разбивают всё пространство возможных значений на две равных части. Вот это и есть ключевой момент теоретико-информационного определения бита, про который нередко забывают даже при постоянной, – ручной, так сказать, – работе с битами/байтами: один бит информации соответствует уменьшению “неопределённости” в два раза, что бы там под “неопределённостью” ни подразумевалось. Если взять произвольный байт, то значений у него может быть 256 различных, это будет степень неопределённости. Если известен один бит, то возможных значений уже 128, если два бита, то 64, и так далее, перемещаясь по картинке вниз. А если эту концепцию наложить на идею непрерывности, то нетрудно увидеть целый набор фундаментальных математических объектов.



Комментировать »

Единичной окружностью, при некоторых допущениях, можно назвать достаточно мощное множество пар чисел (x, y), которые удовлетворяют формуле X^2 + Y^2 == 1. Это, например, привычный случай школьной координатной плоскости. Но можно сказать, что “окружность”, без всяких формул, это большой набор конкретных пар чисел, которые буквально переписаны в массиве исходных данных. Отсутствие формулы в методе определения делает второй вариант существенно отличающимся от первого. И этот второй вариант как раз соответствует популярному сейчас подходу с использованием ИИ (“искусственного интеллекта”) в качестве инструмента анализа: вместо построения вычислительно эффективного общего метода – предлагается таскать с собой наборы исходных данных, проводя там поиск. Чтобы описать больше разных окружностей – возьмём больше разных массивов.

В случае с формулой – (координатная) пара принадлежит окружности, если подстановка в формулу сохраняет равенство. В случае с массивом исходных данных – пара принадлежит окружности тогда, когда удалось найти именно эту пару методом перебора массива. Зато нет дополнительных моделей и концепций. Это сильно различающиеся подходы.

Важный онтологический аспект: новое знание – это возможность заменить большой массив “исходных данных”, где из дополнительных структур присутствует только способ индексирования (“итератор”, если хотите), на структурный метод, который в вычислительном смысле не только короче, но и много проще, чем “итератор” с исходными данными. Понятно, что таблица координат точек, задающих окружность, тоже может использоваться во многих практических случаях, например, если нужно быстро рисовать некоторые “закрашенные круги” на некотором “матричном” дисплее (условном). Есть и другие варианты эффективного использования подобных таблиц. Но они не отменяют того факта, что можно написать короткую программу, – короче, чем массив с точками “окуржности”, – которая успешно сгенерирует сотни мегабайт видеопотока, имитирующего, предположим, полёт над некоторой фантастической местностью. И тут можно вспомнить популярные когда-то давно “демо-программы” (“демосцены”), работавшие на ограниченных вычислительных ресурсах.

Понятно, что не всякие наборы пар чисел укладываются в заданную выше формулу, если, конечно, не изменять базовую логику, определения операций и прочие свойства. У схемы X^2 + Y^2 == 1 – есть много оговорок, её запись и реализация требует некоторых дополнительных соглашений, в отличие от простого “итератора”, построенного в стиле попарного сопоставления некоторых элементов множества. Однако именно поэтому данная схема несравнимо богаче по познавательным возможностям. Например, использование формулы позволяет построить объяснение того, как так выходит, что некоторая пара чисел не лежит на заданной окружности, то есть, построить весьма мощные новые теории. А вот массив исходных данных, сам по себе, – такой возможности не предоставляет: тут только и можно сказать, что “соответствующей пары нет в списке”.



Комментировать »

Кстати, есть весьма полезный пример, показывающий различие между формулами, компьютерами и интерпретацией формул. Его удобно приводить в качестве иллюстрации к объяснениям про “компиляторы, регистры, транзисторы и ячейки с битами”. Отчасти относится к предыдущей заметке. Сравним запись (a == b) с записью ((a – b) == 0). Например, в контексте записи и компиляции исходного кода на том или ином языке программирования: if (a == b) {…} и if ((a – b) == 0) {…} – известно, что результаты вычисления условий в таких if-ах на практике могут различаться; причём то, как именно они различаются, зависит и от языка, и даже от используемого системного окружения.

Наивная арифметическая логика тут такая: “a равно b, когда a-b == 0”. Но тут многое спрятано внутри. Во-первых, никто же не сказал, какого типа объекты a, b; во-вторых, не определено, что это за операция “-“; в-третьих, с равенством, как понятием, вообще говоря, тоже есть масса тонкостей. Так, в записи использован двойной знак равенства “==” – он означает какую-нибудь “эквивалентность”?

Знак “=” – один из самых сложных, с точки зрения машинной интерпретации. Собственно, поэтому и возникли “==”, “===”, “:=” и прочие сочетания. Вот если написано “f = m+n”, то что тут имеется в виду? Что “f” – это “формула” (или даже “функция”), имеющая вид _ + _? Или запись обозначает, что имя “f” нужно использовать как синоним для строки “mn”? Или это условие, которое обозначает проверку того, что число под именем “f” равно сумме чисел под именами “m” и “n”? Или какой-то другой вариант?

Можно предположить, что “==” это именно “равенство”. Но равенство объектов ещё нужно определить. Это не всегда просто. Особенно, для компьютеров. Особенно, если вы вынуждены использовать какие-нибудь представления с плавающей точкой – тут не только нули прекрасно расщепляются на разные представления, но и другие неожиданные эффекты постоянно проявляются (см. пример ниже). Конечно, наивный школьный подход предполагает, что “==” это, всё же, “простое и очевидное” равенство натуральных чисел, автоматически оснащённых сложением, умножением, и даже какими-то некоммутативными и разрывными вычитанием с делением. Что касается натуральных чисел, то, согласно распространённому мнению, тут-то вообще всё становится “очевидным” ещё после того, как в начальных классах про них много рассказали на примерах с палочками. Поэтому случается, что натуральные числа смело относят в разряд “самоочевидных феноменов”, с которыми работать умеют, якобы, даже вороны и, особенно, вороны (переключите ударение, если вы не LLM).

Однако, если не заходить далеко в орнитологическую область, а остаться с компьютерами, то и тут не нужно даже вспоминать теоретическую математику, чтобы символ “==” начал расплываться: достаточно того, что компьютеры, через языки высокого уровня, работают и со строками символов (что бы это ни значило). Сравнение строк требует дополнительных соглашений, с которыми сталкивались даже многие пользователи персональных компьютеров. Причём процесс тут двунаправленный, приводящий к занимательным эффектам: вспомним, что во многих случаях заглавные и строчные буквы ASCII считаются одинаковыми. Тогда строка “AbC”, выходит, равна строке “ABc”, пусть тут и некоторое видимое свойство перешло на соседнюю букву; но это означает, что “ABC” является повторением “Abc”, и хоть битов для записи нужно больше, ничто не мешает на каком-то этапе обработки переписать “ABC” как “abc” – что сплошь и рядом делается в программировании, а побочный эффект используется для защиты DNS-запросов, сколь бы странным это ни показалось.

А ведь “==” может предусматривать неявное приведение типов при сравнении, что прямо относится к не менее школьным, хоть и некоммутативным, задачам про апельсины в ящиках (например). Потому и появляются “===”, а также и используемые в теоретической математике “:=”, означающие не столько “равенство”, сколько определение. Что же про вариант (a-b) == 0, то тут, как минимум, ясно, что требуется ввести много дополнительных соглашений, чтобы определить вычитание. Особенно, для строк. Но и без строк в компьютерном представлении возникнут новые, занимательные эффекты, иногда полезные, иногда – неожиданные.

Вот и вернёмся к языкам программирования и представлению чисел в компьютерах. Известно, что уже в языке Python попытка признать (a-b) == 0 и a == b эквивалентными наталкивается на тот самый, занимательный, эффект:

import math
a = math.pow(5, 55)
b = 5 ** 55

print(a == b)
print((a - b) == 0)

Эта нехитрая программа печатает следующий результат (Python 3.9, Debian 11):

False
True

Так что здесь a хоть и не равно b, но зато (a – b) равно нулю. Что происходит? Происходит вычислительное сравнение, на которое влияет представление чисел внутри Python, переполнение и автоматическое (неявное) преобразование типов:

a == 2.7755575615628914e+38
b == 277555756156289135105907917022705078125

– это, вообще-то, весь фокус, записанный “в формулах”. Соответственно, если возводить в степень 15, то программа напечатает True и True, что соответствует арифметическим ожиданиям. Аналогичный эффект (True, True) даст, по другой причине, следующий вариант:

import math
a = math.pow(5, 55)
b = 5 ** 55

print(a == float(b))
print((a - b) == 0)

За простыми на вид компьютерными формулами часто скрываются хитрые трактовки и скрытые структуры, которые хоть и подразумеваются, но это подразумевание бывает с двойным (“==”), а то и с тройным дном (“===”).



Комментировать »

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

Иными словами, мощность 2^2000 состояний интерпретируется как количественная оценка незнания о состоянии некоторой системы (частиц) в мысленном представлении конкретного наблюдателя-исследователя: вот система из 2000 частиц, но наблюдатель-исследователь не знает ничего о конкретном её состоянии, кроме того, что вариантов есть всего 2^2000, а две тысячи битов можно даже вручную зарисовать карандашом на листе ватмана. Получается, что весь огромный массив “спрятался” за мысленным представлением о неизвестном (кстати, это концептуально совпадает со схемами физических экспериментов, когда наступление “квантового” события определяется по отсутствию события “классического” – “детектор ничего не детектировал”).

В случае, когда огромное количество состояний нужно было бы вкладывать в “окружающую Вселенную”, мощностей могло бы и не хватить. А вот огромный “топос”, стоящий за интеллектом наблюдателя-исследователя, проблем с размещением 2^2000 испытывать не будет: во-первых, это конечное количество; во-вторых, значение локализуется в легко обозримую структуру. Перекликается с идеями о том, что и окружающий кусочек Вселенной – это лишь локализация аспектов из того самого “топоса” (то есть, “галлюцинации”), а невычислимый процесс этой локализации – соответствует интеллекту (может, даже разуму).



Комментировать »