dxdt.blog: занимательный интернет-журнал

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

Итак, представьте, что лексический парсер, обрабатывающий предложения, столкнулся со следующей конструкцией на английском языке:

The chap the cat the girl owned scratched screamed.

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

Это пример так называемого “центрального встраивания”, “центрального эмбеддинга” (а ещё точнее: center embedding – на английском). Лингвистическое явление, важность которого для парсинга языковых грамматик, – в том числе, и прежде всего, людьми, – определил Хомский.

Вернёмся к фразе ещё раз:

The chap the cat the girl owned scratched screamed.

Можно использовать фигурные скобки и переписать предложение так, что получится “код” на некотором условном языке “программирования”. Условном, но зато очень высокого уровня.

The chap {
	the cat {
		the girl {} owned 
	} scratched 
} screamed.

И это уже можно разобрать. Пошагово выписываем то, что за внутренними скобками:

The chap – screamed,
the cat – scratched,
the girl – owned (тут специально поставлены пустые скобки, чтобы наметить рекурсивный принцип, лежащий в основе встраивания).

Если, как говорится, своими словами, то пересказать можно так: “Парень вскричал, потому что его поцарапала кошка, принадлежавшая девушке” (или кот? nyet, “кот” – был бы tom). Owned (“была владеема”, если дословно) – относится к кошке, со стороны девушки. Если переставить слова, то получим: the girl owned the cat – “девушка владела котом/кошкой”. Казалось бы – эквивалентная конструкция. Но нет, не совсем, потому что парсинг разных записей будет разным. То есть, смысл, стоящий за {the cat the girl owned} и {the girl owned the cat}, может быть и одинаковый, но к этому смыслу ещё нужно привести текст, записанный разным способом. Это напоминает понимание логических формул, как “записей”, которое понимание даётся с трудом. Кроме того, наблюдаемый эффект очередной раз подчёркивает то, что в самом тексте смысла нет.

Итак, возвращаемся к разбору исходного упражнения: the girl owned the cat – “девушка владела кошкой”. И эта кошка поцарапала парня. Поцарапанный принадлежащей девушке кошкой парень – вскричал: screamed.

Эмбеддинг позволяет вложить отношения одно в другое, “подвесив” каждую половину пары в ожидании глагола, а все три смысловых пары – в ожидании возникновения структуры вложенности. Посудите сами: the chap – подвешивает “объект парень” (что “the chap” сделал, что – не сделал; что с ним произошло?), для разрешения нужен ответный элемент лексической конструкции, в данном случае – глагол screamed, но он стоит в самом конце, а вместо него парсер читает the cat. Тут парсер должен запомнить, что не хватает соединения для предыдущего “объекта” и продолжить разбирать фразу. Но третим пунктом опять идёт “подвешивание”: the girl. И только потом – начинаются “замыкающие” глаголы, которые нужно правильно подключить.

Реально ли такой же эффект получить на русском? Можно попробовать, но результат всегда будет лишь приблизительный, да и то, только если без запятых. Причина в том, что русский – не столь аналитический, как английский. Например:

“Парень кошкой девушке принадлежащей поцарапанный вскричал”.

Но тут уже видны разные падежи, и сразу становится “понятно”, что “парень кошкой” (какой?) и т.д. Здесь уже подключения выполнены морфологией, парсер не должен ничего подвешивать. Это совсем другая схема, не такая, как в английском: синтез, доступный русскому языку, нивелирует перегружающий парсер эффект.

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

Потому что если парень кошкой вскричал, то “поцарапанный” повисает полностью, уже ни на что не опираясь. А если всё же приклеить “поцарапанный” к парню, – ну, кошкой вскричал он, поцарапанный, – то что делать с “принадлежащей”?

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

Другой вариант на русском:

“Парень, кошка, – девушка владела, – поцарапала, вскричал”.

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

“Парень кошка девушка владела поцарапала вскричал”.

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

Более того, если использовать множественное число, то можно отказаться от артиклей the (для единственного – отказаться никак нельзя: получится сильно “неграмматический” вариант). Например, в подборке головоломок Quanta Magazine предлагалось раскодировать следующую, чисто рекурсивную, фразу:

Bulldogs bulldogs bulldogs fight fight fight.

Опять же, это грамматически корректное предложение на английском. Но понять, кто тут кого “борет” – непросто. (Весьма вольный перевод, в котором все “бульдоги” – это бульдоги из разных стай: «бульдоги, которые дерутся с дерущимися бульдогами, тоже нарвались на бульдогов, которые дерутся». Ну или что-то в этом роде: бульдоги – они такие.)

В разговорном языке подобные конструкции, – третьего уровня, – практически не встречаются. Тем не менее, вот более чем реальный пример «канцелярита» из документа под названием British road traffic act, 1972 (это что-то вроде дополнений к правилам дорожного движения, не важно) – вчитайтесь:

A person who, when riding a cycle, not being a motor vehicle, on a road or other public place, is unfit to ride through drink or drugs shall be guilty of an offence.

Всё понятно? Конечно. “Лицо, которое, когда едет на велосипеде, который не является транспортным средством, по дороге или по другому общедоступному пространству, не способно ехать из-за алкогольного или наркотического опьянения, должно быть признано совершившим правонарушение”. Всё верно, но – уф!

Другой пример, уже на “американском” языке, но тоже хороший – между прочим, это фраза из интервью футболиста (американского), но в 1985 году:

It’s ironic that I’m here, where the man the trophy I won is named after coached.
(Источник: Fred Karlsson, Multiple Center-embedding in Spoken English.)

Отличный стиль встраивания: тут дважды повторяется двухуровневый эмбеддинг! Подобную игру слов, пусть и без “местных идиоматических выражений”, не перевести точно на русский. Впрочем, вот вариант: “Есть некоторая ирония в том, что и я – здесь, где человек, в честь которого назван Приз, который я выиграл, был тренером”.

Получается, что в ходе непростого декодирования подобных конструкций парсер вынужден “подвешивать” существительные до момента их “разрешения”, например, глаголами. При этом двойное подвешивание вообще не составляет проблемы в английском: the ball the cat dropped bounced. Совсем сложные случаи почему-то начинаются с трёх подвешиваний.

Возможно, причина в том, что каждое подвешенное существительное потребляет некоторый важный ресурс парсера. Скорее всего, рассматривая примеры предложений выше, вы сами можете почувствовать это исчерпание ресурса, приводящее к “зависанию” “сознательного парсера”. То есть речь тут вовсе не про программу или LLM. Что это за ресурс? Возможно, специальная структурная лексическая память, а возможно, некий “модуль” “разрешения противоречий”. Предположим, данный модуль должен заранее занять некий объём доступных связей, чтобы потом собрать из них уже осмысленный, непротиворечивый вариант, присоединив понятия лексическими коннекторами одно к другому – так, как нужно. Однако, при разборе подобного эмбеддинга, вместо подключений смыслов происходит “тик, тик, тик” по уровням, и каждый “тик” – это подвешенный коннектор, который требует предварительного захвата кучи возможных связей для обеспечения своего “висения” против всего корпуса возможных смыслов.

Описанное переполнение в английском наступает раньше, и это переполнение – однонаправленное (слева направо). Вернёмся к исходному предложению: The chap the cat the girl owned scratched screamed – может, пацан-парень (the chap) тут – это тот, который принадлежит кошке и девушке (the cat the girl owned)? Мало ли – они могли его захватить. Но тогда не хватает союза (and?) и повисает царапанье (scratched).

Вспомогательные элементы, типа “который”, “где” и др. – они как бы есть в английском варианте, но там они “нулевые”, обозначены пустыми словами, и только если рассматривать текст во всей полноте, тут же возникают в построенной структуре. Это важный момент. И он, опять же, подтверждает, что в любом тексте, – как в тексте, – никакого смысла нет: смысл образуется в представлении читающего. Конечно же, можно добавить структурных элементов, типа who, what, that и пр., в английский текст. И получится знаменитый This Is the House That Jack Built:

This is the cat
That killed the rat that ate the malt
That lay in the house that Jack built.

Схема в чём-то похожая, но парсер уже не переполняющая.

(Это дополненная версия статьи, которую я ранее опубликовал на “Хабре”.)

Кстати, в заметке про возрождение дирижаблей на dxdt.ru, которая вышла в 2008 году, 17 лет назад, упоминаются дирижабли-авианосцы, как носители беспилотников. Но там же сказано, что самолёты (понятно, что самолёт – не беспилотный), “уже базировались на дирижаблях, в краткую эпоху цеппелинов”. Так и было. Это сейчас, почему-то, схему преподносят как новинку. За прошедшие годы в интернеты выложили немало архивных фото. Вот ниже пара подтверждений про самолёты на цеппелинах.

(Credit: Richard K. Smith/U.S. Naval History and Heritage Command.)

Это самолёт Vought UO-1 и стыковочная ферма, которая должна была использоваться на цеппелине, во время испытаний, 1928 год.

(Credit: National Archives and Records Administration.)

Тот же самолёт, но уже прицепленный к дирижаблю USS Los Angeles. 1930 год.

Кстати, в продолжение недавней заметки про то, что тип float – это не про числа, тем более, не про действительные числа. С точки зрения рекомендаций разработчику ПО.

Вообще, если получается, то никаких float и тому подобных инструментов лучше не использовать. Совсем. Тем более, в воплощении различных sin, cos и прочих. Заменять нужно таблицами целых (в смыcле int) значений и целочисленными, со строго фиксированной справа точкой, арифметическими операциями. Особенно, если речь о программировании систем управления и микроконтроллеров.

Если же не получается совсем отказаться, то есть эффективный способ правильно думать про float. Нужно переменные с типом данных float понимать как алгоритмы, и сравнение таких переменных интерпретировать как сравнение алгоритмов. Это помогает избежать многих ошибок (см. ниже).

Например, во float нет дистрибутивности. В алгоритмической интерпретации это означает, что выражения L := b*(c + d) и L := b*c + b*d – присваивают переменной L разные алгоритмы. И действительно, запись, в которой сперва вычисляется сумма (c + d), а потом результат умножается на b, это другой алгоритм, нежели вариант, когда сперва b умножается на d и b умножается на с, а потом вычисляется сумма результатов (обратите, кстати, внимание, что тут ещё и порядок играет важную роль: сначала b*c или сначала b*d? если с точки зерния параллельных вычислений эти операции могут быть выполнены “независимо” разными потоками, то с точки зрения компилятора, имеющего дело с вполне себе последовательной записью, всё может выглядеть сильно иначе – но это явно тема для другой записки).

Если не упускать этот алгоритмический момент из виду, то оступиться становится сложнее. Так, алгоритмическое восприятие float позволяет отбросить сомнения, что в двух описанных выше случаях из L можно достать разное битовое значение при одних и тех же входных переменных – алгоритмы-то там разные. Естественно, сравнивать алгоритмы сложно, но тут понятие об алгоритме – это лишь средство обобщения, мыслительный гаджет, но такой гаджет, который верно работает.

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

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

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

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

Разберём один такой конкретный пример математической задачи с глиняной таблички YBC 6967/P255041. Табличка датируется 1900-1600 до н.э., этот период называют “старовавилонским”. Фотографии четырёх её сторон приведены ниже. Небольшая часть клинописных знаков находится на боковушках таблички, но для наших целей это не важно: в этот раз мы не будем расшифровывать сами надписи по отдельным клинописным знакам – главное, что на табличке нет чертежа, а только текст (но осталось место, на котором мог быть быть чертёж).

(Источник: Yale Peabody Museum, YPM BC 021031; картинка есть в большем разрешении.)

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

Во-первых, древние шумерские задачи часто ставятся для пар специальных чисел, которые называют “обратными”. Такие числа используются и в типовых задачах с “квадратными уравнениями”, и на табличках с таблицами умножения. Соответствующие клинописные термины обозначают igi-bi и igi. А именно, это такие парные числа, произведение которых равно степени числа 60. 60 является основанием системы счисления, поэтому обратными будут: 4 и 15, 3 и 20, 6 и 600 и т.д. Это система с плавающей точкой, поэтом 60 тоже может обозначаться единицей (откуда и термин “обратные”: это ведь и есть обратные числа, в том смысле, что их произведение обозначается цифрой 1). Данный подход используется и в задаче на рассматриваемой табличке.

Почему, всё же, 60 – это единица? Потому что система счисления позиционная и шестидесятеричная. Например, в десятичной системе обратным к 2 можно назвать 5, потому что 2*5 это 10. Но десять, вроде бы, не единица? Да, если говорить о числе, но не совсем так, если говорить о системе счисления. Если десятичная точка плавающая, то отличить единицу от 10 или от 100 будет сложно. Если мы перемещаем точку вправо, то из 5 получается 0.5, а это уже точно 1/2 – то есть, обратное к числу 2 в привычном смысле алгебры умножения.

Шестидесятеричная система более удобна для точных расчётов, чем десятичная – подробнее про шестидесятеричную систему можно прочитать в отдельной заметке, а здесь все числа, для удобства, будут даны в десятичной записи.

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

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

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

Вернёмся к табличке. Набранный на ней текст содержит формулировку задачи с пошаговым объяснением того, как эту задачу решать.

Упрощённый перевод, где в скобках даны мои комментарии (адаптировано из Jens Høyrup, Algebra in Cuneiform, 2013):

Из пары обратных чисел (то есть, те самые igi-bi и igi), одно превышает другое на 7.
Чему равны эти обратные числа?
Возьми 7, на которое одно число другое превышает, и разбей на две части: 3½. (Здесь “разбей” – нужно интерпретировать как деление отрезка пополам.)
Восстанови два 3½, результат: 12¼. (А это и есть геометрическая операция получения квадрата на двух равных отрезках, задающих стороны.)
Присоедини 12¼ к исходной площади, равной единице: 72¼. (Обратите внимание: единица здесь – есть первая степень 60 в терминах шумеро-вавилонской системы счисления, то есть, 60 + 12¼ == 72¼.)
Чему равно 72¼? Это 8½. (“Равно” здесь – это обратное геометрическое преобразование, от квадрата, как фигуры, к стороне: то есть, сторона квадрата с площадью 72¼).
Теперь отметь 8½ и соответствующее 8½. (В смысле сторон квадрата.)
3½, элемент площади, отсоедини и присоедини на место. (8½ – 3½ == 5; 8 + 3½ == 12; заметьте ещё раз: (8½)^2 – (3½)^2 == 60.)
Первое число – 12, второе – 5.
12 есть одна часть пары, 5 – вторая. (Те самые igi-bi и igi.)

Попробуем не рисовать чертёж, а сразу понять, какая тут задача, в числах. Первая строка условия говорит, что произведение некоего числа на сумму этого же числа и 7 равно 60. Собственно, если обозначить искомое число x и записать всё в формулах современной алгебры, то и получаем квадратное уравнение.

x(x+7) == 60
x^2 + 7*x == 60
x^2 + 7*x - 60 == 0

Как такую задачу решает школьник сейчас? Очень просто – что называется, не задумываясь:

x^2 + 7*x - 60 == 0,
D == 7^2 - 4(-60) == 289,
(x_1, x_2) == (-7 +/- √289)/2 = (5, -12).

Ответ -12 - не подходит (кстати, почему?); выбираем ответ 5. 
У нас прямоугольник, одна сторона равна 5, вторая, по условию, 5 + 7 == 12. Ответ: 12 и 5.

Но на исходной табличке нет дискриминанта, там, в современных обозначениях, записано несколько другое преобразование:

Исходная площадь 60, то есть, "единица", которую обозначим q.

Пусть p - разность сторон (второе число на 7 больше, то есть, p == 7).
 
x(x + p) == q

Тогда p/2 это половина разности (7/2).

(x + p/2)^2 == q + (p/2)^2 - то есть, строим больший квадрат, его площадь равна 72¼ (см. правую часть).

Дальше, по табличке, – “геометрически” извлекаем квадратный корень из левой части: то есть, определяем, что отрезок x + p/2 равен стороне квадрата с площадью 72¼. А именно: 8½.

Если переписать в современных обозначениях, то получим то, что принято называть выделением полного квадрата. Именно так и выводится формула для решения квадратного уравнения:

(x + p/2) == sqrt(q + (p/2)^2),
x == -p/2 + sqrt(q + (p/2)^2).

Здесь p, q это коэффициенты из x^2 + p*x + q == 0.

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

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

Теперь посмотрим на чертёж к задаче.

Условие соответствует верхней диаграмме. Остальные – объяснение метода решения.

Дистрибутивность умножения относительно сложения означает, что a*(b + c) = a*b + a*c. В действительных числах, по определению, умножение дистрибутивно относительно сложения. Запишем это на Pyhton и посмотрим, что напечатает простая программа.

import math

q = 11*(math.sqrt(5) + math.sqrt(17))    # q = a*(b + c)
p = 11*math.sqrt(5) + 11*math.sqrt(17)   # p = a*b + a*c
print(p == q)                            # q == p => (q - p) == 0

q = 34*(math.sqrt(5) + math.sqrt(17))
p = 34*math.sqrt(5) + 34*math.sqrt(17)
print(p == q)                            # ???

Запускаем (Python 3.11.2) и смотрим:

True
False

В коде, в первом случае, написано:

p = 11*(√5 + √17),
q = 11*√5 + 11*√17.

Значения p, q сравниваются. Программа выводит True – значения равны. Что и следовало ожидать, если бы это были действительные числа: по определению, q и p – это одно и то же число.

Во втором случае написано всё то же самое, алгебраически, но другой множитель:

p = 34*(√5 + √17),
q = 34*√5 + 34*√17.

Удивительно, но результат сравнения p и q теперь False – числа не равны.

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

Компьютеры не работают с действительными числами. Потому что это невозможно. Да, натуральные, целые, рациональные – это подмножества действительных (с которыми подмножествами компьютеры тоже не работают, кстати). Но если вы случайным образом бросите точку на числовую прямую, то попадёте в иррациональное число. Запись этого числа в виде десятичной дроби – бесконечный процесс, который, впрочем, может быть формально определён – получится алгоритм вычисления конкретной записи числа (вспомним формулы для π, например).

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

Да, символьные вычисления, с успехом выполняемые компьютерами, позволяют работать с “иррациональностями”. Но символьные вычисления происходят в других математических структурах (в других кольцах, если хотите строго) и не работают с десятичной записью действительных чисел. То есть, если записывать √2 как символ “√2”, – в том смысле, что это обозначение числа, квадрат которого равен двум, – то тут проблем нет. Но совсем другое дело – преобразование десятичной записи.

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

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

Один из очень мощных методов обработки радиосигналов, повышающей возможности радаров, это синтезирование апертуры антенны. Общие приципы этого метода я описывал на dxdt.ru. Вот, например, записка 2008 года. Если совсем кратко, то идея синтезирования апертуры такая: станем записывать сигналы в разных точках некоторой траектории, а потом синхронно обработаем результаты записи, учитывая координаты точек, для которых отдельные элементы были записаны. При выполнении некоторых условий – полученный результат будет близок к результату физической антенны, размер которой соответствует дистанции, пройденной при записи. То есть, пролетел отдельный приёмник с малой антенной двадцать метров – результаты синтезирования позволяют получить виртуальную двадцатиметровую антенну.

С синтезированием апертуры связан ещё один интересный аспект: для синтезирования необходимо движение, но двигаться может не только радар. Напротив, двигаться, относительно радара, – и, обычно, некоторого “фона”, подстилающей поверхности, – может наблюдаемая цель, а её движение как раз создаст “базу” для синтезирования сигнала. Это метод обратного синтезирования апертуры. Алгоритмы используются существенно более сложные, но метод неплохо подходит для распознавания и классификации типов движущихся целей. Особенно, на море, в отношении больших кораблей. Поэтому использованием обратного синтезирования особенно известен штатовский P-8 Poseidon – морской самолёт радиолокационного наблюдения, на котором применяется специальная, подвешиваемая под фюзеляж, наружная система РЛС AN/APS-154 (AAS).

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

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

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

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

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

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

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

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

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

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

Но, всё же, нетрудно найти и конкретные примеры, когда возможности физического эксперимента по быстрому завершению процесса превосходят возможности классических компьютеров по моделированию исхода этого же эксперимента. У Ричарда Борчердса есть прекрасная иллюстрация (YouTube, англ.): квантовые вычисления на фарфоровом чайнике. Фарфоровый чайник, упавший на бетонный пол, разбивается существенно быстрее, чем суперкомпьютер успевает предсказать конфигурацию осколков чайника. Но только лишь из этого наблюдения – не следует обратное: что, мол, можно подключиться к сверхмощному вычислителю внутри чайника, чтобы использовать его для решения других задач.

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

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

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

Такие вычисления могли бы выполняться быстрее, чем на суперкомпьютере в той же симуляции, поскольку суперкомпьютер обсчитывается более медленными фрагментами кода на стороне гипервизора. Почему это так? Потому что суперкомпьютер построен из отдельно моделируемых кусочков – транзисторов внутри симуляции и тому подобных элементов. Реализация каждого элемента требует ресурсов. Это как модель компьютера на “редстоун-релюшках” в Minecraft: работает, но очень медленно. А вот вычисление конфигурации осколков чайника – вселенский гипервизор реализует непосредственно, на своей аппаратуре. Могли бы это и быть “квантовые вычисления”? Да, вполне.

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

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

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

(Это версия статьи, которую я вчера разместил на “Хабре”.)

Опубликовал на “Хабре” статью по теме занимательной арифметики и вычисления периода записи дробной части чисел в позиционных системах счисления. Это, фактически, развёрнутое объяснение того, почему можно на калькуляторе проверить период записи рационального числа 1/(7^11) – тут важно, что это объяснение “почему”, и на примере двоичной системы счисления (думаю, что это по теме подходит на “Хабр” хорошо), а иначе-то всю вторую часть можно сильно сократить, определив период для 1/7. Сам исходный период, для 1/(7^11), я привожу в пример в статье про шумеро-вавилонские цифры.

В современном английском предложения “the bumblebee chased the ball” и “the ball chased the bumblebee” диаметрально переставляют преследующего и преследуемого только потому, что переставлены слова. Есть занятная гипотеза, почему так получилось. Если люди разговаривают на двух относительно близких языках, которые, тем не менее, имеют разные схемы словоизменения, разную морфологию, то получается, что при общении на языковой границе удобно просто отрезать от слов изменяемые элементы, оставляя только какой-то базовый вариант, фактически – корень. Ведь корни в этих языках часто одинаковые, поэтому и основное значение фразы из урезанных слов “без падежей” слушатель может понять.

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

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

И в английском сходный механизм сработал для древне-, среднеанглийского против древнескандинавских и старофранцузских диалектов. В последнем случае, со старофранцузским, потому, что схема работает и тогда, когда одна из сторон просто плохо владеет языком другой стороны. Такая вот “факторизация” языков по сумме схем словоизменения.

Опубликовал на “Хабре” небольшой текст про рекурсивное “центральное встраивание” (center embedding), которое доступно в английском языке, и его связь с восприятием языков и их грамматик. Речь про фразы вроде “The chap the cat the girl owned scratched screamed” – это как раз основной пример из статьи на “Хабре”. В разговорном языке, понятно, такое не встречается, но так-то у меня есть и вариант с вложенностью уровня пять (нетрудно строить по шаблону, конечно):

The ship the crocodile the chap the cat the girl owned scratched gnawed submerged resurfaced.

Годится для тестирования LLM/GPT.

The ship {
 the crocodile {
  the chap {
   the cat {
    the girl owned 
   } scratched
  } gnawed 
 } submerged 
} resurfaced.

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

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

Всё то же самое применимо и к симметричным алгоритмам: можно построить некоторое ожидание стойкости – например, 64-битный симметричный ключ для какого-то алгоритма можно считать стойким в течение недели. Опять же, условная оценка – многое как раз зависит от алгоритма, от доступных оптимизаций. 2^64 это не так мало, как может показаться: представьте, что специализированный вычислитель проверяет 1000 значений за один такт и работает на тактовой частоте 5 ГГц (зедесь и 1000, и гигагерцы – это всё время), тогда для перебора 2^64 значений потребуется полтора месяца. (А если проверка одного значения занимает много тактов, то и полный перебор сильно затянется для 2^64.)

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

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

Но всё это – время, и в случае утечек оно играет даже две роли одновременно: утечка “по каналу времени” позволяет сократить время перебора.