Чему равен усердный бобр?

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

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

Это называется Halting Problem - по заданной программе машины Тьюринга и входным данным определить, остановится она или попадёт в бесконечный цикл. Было доказано, что отвечающего на это алгоритма в общем случае не может существовать. Пруф остаётся в качестве упражнения для читателя.

Рассмотрим все машины Тьюринга с N состояний, которые остановятся, если их запустить на ленте из нулей. Какая из них работает дольше всех? Максимальное количество шагов и называется функцией усердного бобра - Busy Beaver - BB(N)

Несмотря на кажущуюся пустяковость и смешное название, эта функция - практически final boss среди последовательностей. Она растёт очень, очень, ОЧЕНЬ быстро. Начинается она вменяемо - BB(2) = 6, BB(3) = 21, BB(4) = 107.

Ещё в 1990 году была найдена машина из 5 состояний, которая работает 47,176,870 шагов. Но здесь Тьюринг наносит нам лоу-кик - BB(N) невычислима. Так как невозможно определить, остановится ли произвольная машина Тьюринга, чтобы доказать значение BB(N), необходимо по отдельности доказать зацикливаемость всех машин, которые работают дольше BB(N). Одним из следствий этого является то, что BB(N) растёт быстрее всех функций, которые можно описать конечным алгоритмом.

Звучит, как абсолютно бесполезная на практике проблема, которую должны решать почётные доктора наук за государственные деньги, да? Как бы не так!

Многие исследователи-"любители" посчитали, что задача достаточно весёлая, чтобы самоорганизоваться ради её решения. В 2022 году был создан так называемый The Busy Beaver Challenge - центр притяжения фанатов данной проблемы. Они создали сайт, вики, дискорд и взялись за работу.

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

Конечно, для большинства из них это не является большой проблемой, но в семье не без уродов. Ещё в 2003 году Skelet опубликовал свой результат - доказательство на Паскале длиной в 6000 строк, которое работает для всех, кроме 43 особо непонятных машин. Их так и назвали - 43 машины Скелета.

Исследователи в дискорде разделились и начали расправляться с машинами Скелета. 13 из них они назвали спорадическими - их не удалось доказать общими методами. Для них в индивидуальном порядке конструировали доказательство их бесконечной работы. Чтобы вы понимали уровень сложности происходящего, приведу описание первой из них:

Skelet #1 - после по крайней мере 10^51 шагов, начинает бесконечно выдавать одинаковый паттерн каждые 8,468,569,863 шагов

Итак, спустя 2 года работы задача была полностью решена - подтверждено, что BB(5) = 47,176,870. В инструменте для формальных доказательств Coq был скомпилирован и выложен общий пруф этого утверждения, который для всех машин, работающих дольше BB(5) шагов, доказывает их зацикленность.

Что там дальше по списку, BB(6)? Да, вот вам машина, работающая 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 шагов. Впердё!

UPD. Оказалось, что неделю назад была найдена машина из 6 состояний, которая работает 10↑↑11010000 шагов - то есть 10 в 10 степени не 15 раз, а 10 миллионов. 6 состояний, Карл!

Чем же так заняты эти усердные бобры? Что можно делать так долго, оперируя всего в рамках 5 или 6 состояний? Разберём это в следующий раз, а также то, как это внезапно оказалось связано с одной из известных открытых проблем теории чисел.

@knowledge_accumulator

- О нет, наш малыш упал головой вниз на асфальт! Надеюсь, это никак не повлияет на его интеллект.

25 лет спустя:

- Я против кондиционеров, потому что они наносят вред окружающей среде 👎

Чем так занят усердный бобёр?

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

BB(4) равно 107 - на 4 состояниях особо не развернёшься, а вот BB(5) равна уже 47,176,870. Чтобы осознать её прикол, нам нужно сделать небольшое отступление и посмотреть на одну из простейших (на вид) открытых проблем в математике. Рассмотрим функцию такого вида:

f(x) = x/2, если x чётное
f(x) = 3n+1, если x нечётное

Что, если взять какое-нибудь N и начать применять к нему такую функцию много раз? 5->16->8->4->2->1. Так называемая гипотеза Коллатца заключается в том, что из любого числа мы в итоге придём к 1. Это было подтверждено для чисел <10^21, но так и не было доказано для любого N. У Veritasium есть очень любопытное видео на эту тему.

Итак, функции, которые применяют определённую арифметическую операцию к числу в зависимости от остатка на деления, так и называют - Collatz-like. Их траектории выглядят практически случайными и могут долго колебаться, прежде чем придут в какое-то "финальное" состояние.

Да, вы всё правильно поняли - оказалось, что усердный бобёр из 5 состояний генерирует последовательность для Collatz-like функции от нуля следующего вида:

f(x) = 5(x/3) + 6, если x mod 3 = 0
f(x) = 5(x-1)/3 + 9, если x mod 3 = 1
f(x) = finish state, если x mod 3 = 2

То есть, вместо единицы, как в оригинале, "конечных точек" у неё бесконечно много. Так выглядит генерируемая бобром последовательность:

0->6->16->34->64->114->196->334->564->946->1584->2646->4416->7366->12284->finish

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

Итак, определим такое состояние ленты C(m, n) - сначала m единиц, потом n раз по 001 и ещё 1 единичка в конце. Указатель при этом смотрит на ноль по соседству слева перед всей этой конструкцией. Машина проделывает следующее упражнение, начиная из состояния C(m, 0).

1) m единиц она превращает в ~m/3 троек 001, т.е. общая длина почти не меняется. C(m, n) -> C(0, (m+4)/3) или C(3, (m+3)/3), в зависимости от остатка от деления. В третьем случае машина как раз проваливается в своё конечное состояние.

2) Далее машина наступает на каждую 001, закрашивает нули и отправляется в самое начало ленты, добавляя ещё 2 единицы слева, а затем переходит к следующей 001. То есть, C(m, n) -> C(m+5, n-1).

3) Когда 001 заканчиваются и n снова равно 0, мы получили C(m_next, 0) и далее повторяем процедуру, начиная со пункта 1. Последовательность значений m_1, m_2. m_3, ... как раз и ведёт себя как Collatz-like ряд, описанный выше.

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

Честно говоря, меня всё это повергает в восторг. Самая долгая машина Тьюринга из 5 состояний совершенно не обязана была делать что-то, имеющее короткую арифметическую интерпретацию. Более того, оказывается, теоретические границы вычислимого имеют связи с реальными математическими проблемами.

Busy Beaver для 6 состояний неизвестен. Такой "простор" позволяет создавать монстров, например, так называемого Экспоненциального Коллатца: вместо умножения становится возможным применять экспоненту на каждом шаге. Но это далеко не предел - только за этот июнь было получено 2 принципиально новых результата - числа, которые возможно записать только в стрелочной нотации. А вы жалуетесь, что GPT-5 долго релизят.

@knowledge_accumulator

Почему люди не хотят жить в безопасности?

Среди всех причин преждевременной смерти людей выделяют так называемые Accidental deaths, то есть смерти из-за несчастного случая. В этом классе всё держится на 3 столпах:

- Падения
По многим причинам, это лидирующая причина смерти от несчастного случая у людей старшего поколения.

- Передоз
Часто замаскированный политкорректным словом "отравление", на самом деле именно передоз является главным источником таких смертей - это аж под 100 тысяч человек в год в США.

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

В США на 100к человек приходится чуть больше 10 смертей в год от ДТП, по масштабу сопоставимо с падением и передозами.

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

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

Если бы машины изобрели сегодня, в эпоху благополучия и безопасности, их точно бы сразу запретили во многих странах. Современная "продвинутая" аудитория обсерается в штаны даже от чат-ботов, кто-то вон даже занимается "научными исследованиями" их опасности.

Мимо тогдашних медиа проблема смертности машин проскользнула, наверное, благодаря медленному adoption. В течение аж 20 лет (с 1900) смертность на 100т. плавно росла от 0.05 до 11 - сегодняшнего уровня.

Так вот, к чему я это. Лучший способ сделать вождение безопасным - убрать из него человеческий фактор. Совершенно очевидно, что автопилот, даже не являясь суперинтеллектом, будет допускать драматически меньше ошибок на дороге.

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

Недавно с коллегой на работе мы обсуждали покупку машины. Он мне сказал - я его первый знакомый, который готов купить теслу из-за автопилота. Его друзья купили теслу, потому что она лучше ускоряется/тормозит, кому-то нравится экономия, кто-то топит за электрокары. Сам он её не купит, потому что тесла хуже конкурентов в плане удобства и качества сборки.

Ау, почему вам вообще на это не насрать? Вы что, реально всерьёз учитываете то, сколько в машине подстаканников и трясётся ли дверная ручка? Вас правда волнует выброс парниковых газов? Машина может ехать САМА, и вы ПОМРЁТЕ с меньшей вероятностью.

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

@knowledge_accumulator

Как создать новую вселенную за 20 строк кода?

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

В моём окружении главной наживкой для обучения программированию была разработка игр. Однако, никто нам не объяснил - как на том же самом C++, на котором я решаю динамическое программирование, создаются 3D-игры? Интуитивно казалось, что эту пропасть нереально преодолеть, и мотивации разобраться не было.

Недавно я решил закрыть эту дыру и обнаружил вот это замечательное видео. Оказывается, на современном железе сделать подобие First Person View это элементарная задача.

Итак, заведём бинарный 2D-массив, содержащий "карту мира" - в каждой позиции либо стена, либо пустота. Смотря на значения этих переменных, у вас не возникнет мысли о том, что перед вами полноценная параллельная вселенная. Но пары секунд игрового опыта может быть достаточно, чтобы свести ваш мозг с ума и заставить в это поверить.

Представьте, что вы умеете рендерить 2D-массив пикселей в каком-нибудь окне. Заведём 4 переменные - x, y, angle и fov - координаты камеры, угол по горизонтали, в котором она смотрит, и угол её обзора.

Чтобы нарисовать картинку от первого лица из этого положения, проходимся по каждому столбцу экрана. Каждый из них соответствует конкретному углу - между angle - fov/2 и angle + fov/2.

Далее "запускаем луч" из положения камеры в этом направлении - "летим" переменными x_ray и y_ray, двигая точку по чуть-чуть в упомянутом направлении. На каждом шаге просто проверяем, есть ли блок стены в этом месте. Когда мы нашли блок стены или улетели за дальность прорисовки, возвращаем одно число - wall_distance.

Итак, у нас есть список wall_distance для каждой x-координаты. Теперь рисуем вертикальную линию в каждом столбце. Линия всегда будет в центре, а её длина будет обратно пропорциональна wall_distance. Осталось добавить тривиальное управление персонажем - изменение x, y, angle по кнопкам. Параллельная реальность готова!

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

Посмотрите на гифку. Если вы не ощущаете себя в этой комнате, скорее всего, с вами не всё в порядке.

Этот базовый алгоритм называется Ray Casting и был впервые реализован ещё в 1960-х. На рубеже 80-х и 90-х благодаря изобретательству таких людей, как Джон Кармак, и развитию железа, стало возможно создавать адекватный игровой опыт на основе такой технологии.

На подобном принципе был основан движок игры Wolfenstein 3D (1992) - знакового шутера того времени. Со временем он эволюционировал до полноценного 3D и лёг в основу Quake Engine (1996), от которого берут своё начало Source (Half-Life, CS, Dota 2), IW (Call of Duty) и, конечно, движок всех Doom.

Как оказалось, заложить первый кирпич в здание полноценной игры и создать параллельную вселенную с нуля не очень сложно! Даже написать обучение линейной регрессии на чистом C++, скорее всего, сложнее.

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

@knowledge_accumulator

Абсолютно будничное рассуждение

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

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

Представим себе, что мы организовали людей согласно такой схеме. Каждому человеку каждый час поступает 2 входа - либо константа, либо выход другого человека, и они обязаны за этот "такт" вычислить 1 бинарную операцию и отдать результат следующему.

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

Что, если подать такому интеллекту на вход задачу "применить алгоритм в неизменном виде как можно больше раз, не заканчивая работу" и запустить схему?

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

Раньше, рассуждая о "сознании" компьютера, мы представляли, что оно "живёт" в его памяти. Теперь же видно, что компьютер сам по себе - это тоже иллюзия. Компьютер не задаётся реальным объектом, компьютером является то, что выполняет функцию компьютера.

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

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

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

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

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

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

Хорошего дня!

@knowledge_accumulator

То, во что я верил 15 лет, оказалось подлым враньём.

Я начал программировать в 7 классе (да, поздно), и тогда это заключалось в решении задачек олимпиадного типа.

Там мне, как полагается, встретилась задача про числа Фибоначчи (вдруг кто забыл, F_{i+2} = F_{i+1} + F_i ). Условие простое - найдите N-ное число Фибоначчи за константную память и линейное время.

К счастью, больших проблем это у меня не вызвало - простой цикл из 3 переменных. У задачи был пункт со звёздочкой - сделайте алгоритм, который работает быстрее, чем за линию. Упёршись в непроходимый для меня тупик, я подсмотрел в решение и увидел то, что в мой мозг поместится не смогло. Но всё же поверил - N-ное число Фибоначчи можно найти за логарифм от N.

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

Итак, выражение "F_{i+2} = F_{i+1} + F_i" можно сформулировать в виде операции умножения матрицы на вектор. Введём матрицу 2x2: [[1, 1], [1, 0]] и вектор 2x1: [F_{i+1}, F_i]. Их умножение даст [F_{i+2}, F_{i+1}], то есть проделает 1 итерацию по ряду Фибоначчи.

Получается, что получить F_n можно, возведя эту матрицу в степень n. Вот тут-то мы и приходим к крутой оптимизации - возведение в n-ную степень можно делать не через n умножений, а через log n!

Идея в том, что мы раскладываем результат на множители, у которых показатели степени это степени двойки. То есть n^29 = n * n^4 * n^8 * n^16. Всего таких множителей будет log n, и получить их все тоже можно за log n. По сути, это эквивалентно переводу n в двоичную систему счисления.

Звучит нереально круто. Так я и жил все эти годы, будучи уверенным в том, что знаю ответ на основной вопрос жизни, Вселенной и всего остального - о том, как быстро можно посчитать N-ное число Фибоначчи.

А потом я наткнулся на это видео - "1 секунда на вычисление самого большого числа Фибоначчи". Уже будучи готовым ублажить свой мозг изучением той информации, которую знаю и так, в результате я упал лицом не просто в грязь, а в натуральное говно.

Длина!

Ряд Фибоначчи растёт примерно со скоростью 1.6^n, а значит, количество цифр в записи n- ного числа Фибоначчи растёт линейно относительно n. Как минимум, для записи результата нам нужно линейное время и линейная память. Но это полбеды.

Для возведения матрицы степени n в квадрат нам нужно умножить 2 числа, длина которых около n. А помните сложность возведения чисел в столбик? Аж целый n^2. Таким образом, для очень больших n итоговое количество сделанных операций выглядит как:

k * n^2 + k * (n/2)^2 + k * (n/4)^2 + ... = O(n^2)

Да, оказалось, что всю жизнь я думал, что алгоритм, работающий за квадрат, работает за логарифм. Это самая большая ошибка в данной области, которую я совершал в жизни.

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

А они там такое безумие наоткрывали, что это достойно отдельного поста.

Upd. Тем, кто говорит, что N-ное число Фибоначчи можно посчитать за O(1) аналитической формулой, советую подписаться на канал Stupidity Accumulator

@knowledge_accumulator

Природа власти над иерархией

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

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

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

Однако, в человеческих стаях, размером с миллионы людей и раскинутые по всей планете, такое не совсем присутствует. В части сообществ, в особенности в западных, присутствует ноу-хау - источником власти является процедура. Вся стая поверила, что данный алгоритм назначения и снятия вожака является валидным. Например, когда президент США уходит с поста, то в тот же день он теряет все свои полномочия до последней копейки.

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

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

Власть Путина это любопытный феномен - сам по себе он, как альфа-примат своей стаи, в одиночку обладает нулевой физической силой по сравнению с любым его охранником. Единственное, что можно назвать осязаемым атрибутом власти в России - это ядерный чемоданчик. Это действительно священный "силовой" артефакт в нашей стране. Однако, даже он не запускает ракеты напрямую, а лишь отдаёт сигнал на запуск. Даже неясно, не проигнорируют ли его исполнители при получении.

Я для себя вижу только одно логичное объяснение природы власти в таких ситуации - вожак является вожаком, потому что все остальные верят, что он вожак, и что он им останется. Как только кто-то проявит нелояльность, его тут же устранят другие. Но не потому, что они этого хотят, а потому, что если не сделать этого, то это само по себе проявление нелояльности, и тогда тебя накажут другие.

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

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

@knowledge_accumulator

Этот метод умножения использует каждый китайский второклассник

Ещё тысячелетия назад люди научились умножать числа "в столбик", тратя O(n^2) операций. Однако, потом произошёл сюжетный поворот. Далее пересказываю его, опираясь на достоверный источник - Википедию.

Итак, некий старпёр из МГУ по имени Андрей Колмогоров в 1960 году проводил математический семинар. На нём он сказал: "Мы уже тысячелетиями знаем про столбик, но так и не нашли ничего быстрее. Наверное, это и есть теоретически оптимальный алгоритм для такой операции".

На семинаре присутствовал 23-летний Толян. В отличие от Колмогорова, Толян в математике разбирался и на авторитетные мнения срал с крыши небоскрёба. Уже через неделю он предложил новый быстрый метод умножения.

Для начала числа нужно разложить "пополам" в виде выражения ax+b, где x это "круглое число", примерно равное корню из числа. Например, 11113333 = 1111 * 10^4 + 3333. То есть a и b это числа в 2 раза короче оригинального.

Мы хотим умножить ax + b и cx + d. (ax + b)(cx + d) = ac x^2 + (ad + bc) x + bd. Так, умножение 2 чисел длиной N мы превратили в 4 умножения длиной N/2 и парочку линейных операций.

И тут Толян заметил fun fact: ad + bc = ad + bc + ac + bd - ac - bd = (a+b)(c+d) - ac - bd. ac и bd мы уже умножаем и так для других коэффициентов, а (a+b)(c+d) это только одно дополнительное умножение вместо двух. Получается, что одно из 4 умножений можно сэкономить!

Итоговая сложность: k*N + 3*k*(N/2) + 9*k*(N/4) + .... ~ O(N^1.6). Метод так и назвали в честь Толяна - алгоритм Карацубы.

В 1971 году к серверу подключились Шёнхаге и Штрассен - тот самый, кто придумал быстрое умножение матриц. В своём телеграм-канале они запостили алгоритм, умножающий числа за O(N * log n * log (log n)).

Число длины N можно представить в виде полинома степени K от заданного основания B: x_0 + x_1 * B + x_2 * B^2 + ... У нас есть 2 таких полинома, и результатом их умножения является ещё один полином степени до 2K. Очевидно, подставляя любое значение вместо B, мы будем получать корректное равенство между произведением изначальных значений полинома и значением результирующего полинома.

Алгоритм заключается в следующем: сначала вычисляем изначальные полиномы в 2K точках, потом умножаем между собой эти результаты (в выбираемых точках они маленькие), а дальше можно восстановить коэффициенты результирующего полинома по этим 2K точкам.

Наивная имплементация этой логики даёт квадратичную сложность. Однако, быстрое дискретное преобразование Фурье, выбор правильной степени разложения и ряд других умных оптимизаций позволяют получить ту самую сложность O(N * log n * log (log n)). Детали этого процесса за гранью моего понимания.

В 2019 году был предложен метод, который в теории способен умножать числа за O(N log N). К сожалению, спрятанная константа здесь настолько большая, что его не имеет смысла применять в каких-то реальных ситуациях.

На текущий момент не доказано, что O(N log N) - это нижняя грань сложности умножения 2 чисел. Лишь несуществование линейного алгоритма следует из одной из нерешённых проблем в Computer Science. Вот и живите теперь с этим.

@knowledge_accumulator

Как моя цель на год оказалась худшим хобби, которое я пробовал

Несколько месяцев назад я начал пытаться стать неплохим игроком в iRacing - это самый популярный онлайн-симулятор гонок, в который играют в том числе и настоящие спортсмены.

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

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

И вот, началась настоящая гонка. Теперь вы и ещё 10 чуваков должны ехать по этой трассе. И здесь есть 2 сценария:

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

Ваш рейтинг выше медианного
Весь ваш состав проезжает трассу почти идеально. Если Макс Ферстаппен проезжает трассу за 1:20, то почти все покажут результат в районе 1:22 - 1:24. По паре десятых секунд вы теряете на каждом повороте, потому что нажали тормоз на 5% сильнее или на 0.1 секунду раньше.
Это испытание вашей выносливости - в течение 10+ минут надо почти безошибочно пройти сотню поворотов. Но тут соперники вновь усугубляют ситуацию:

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

А ведь машины ещё и пытаются друг друга обогнать! Если вы не очень продвинутый игрок, вы не умеете правильно обгонять и реагировать на обгон. В итоге, больше половины обгонов заканчивается тем, что как минимум один улетает с трассы.

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

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

Удобно? Вот этим и занимаются гонщики.

В начале я был заряжен на успех и даже слил пару сотен баксов на курс. Он был неплохой сам по себе, но стало понятно, что учиться нажимать педаль ровно на 80%, а не на 70% и на 90% это выше моего предела скуки. Надо сказать, я всё же дошёл до медианного рейтинга, так что, изначальную задачу в итоге выполнил.

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

@knowledge_accumulator

ARC-AGI-3

Напомню общую концепцию бенчмарков ARC-AGI. Вместо того, чтобы проверять модель на публично доступных данных и том же типе вопросов, на котором учили, мы пытаемся ставить перед моделью по-настоящему новую задачу и проверяем её способность обобщать.

Всего несколько месяцев назад была выпущена ARC-AGI-2, которая в целом не сильно отличается от первой версии, и обе были про решение простых визуальных задачек. А вот третья версия сменила формат и превратилась в игровой бенчмарк. Я прошёл все три доступные задачи и почувствовал суть происходящего.

Без каких-либо объяснений вас кидают в простенькую 2D-игру. Наша человеческая интуиция позволяет всего лишь за десятки действий построить модель этого мира и двигаться вперёд. При этом, авторы явно постарались сделать их совершенно непохожими на уже существующие игры.

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

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

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

При обучении RL с нуля это большая проблема. Когда-то я рассказывал про прорывную работу на бенчмарке Atari-100K, где пытаются достичь хорошего уровня "всего" за 100 тысяч кадров. Это тот минимальный масштаб, на котором оперируют текущие методы, причём, в Atari почти нет меняющихся уровней.

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

Для меня остаётся тривиальным вопрос о том, как такое решать - обучаемые алгоритмы, когда отскейлятся, такой бенчмарк съедят не жуя. Интересно то, как и когда к этому подступятся модели из текущей AI-волны. Очень скоро выходит GPT-5. У неё обязательно получится, ведь так?

@knowledge_accumulator

Что хуже - гонки в компьютере или реальные гонки?

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

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

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

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

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

Получается, что реальными гонками заниматься едва ли лучше, чем виртуальными, если нет цели подвергать себя риску и получать от этого удовольствие.

Но помимо занятий гонками в обществе гораздо более популярен другой феномен - а именно, на гонки любят смотреть. Для примера рассмотрим Формулу 1.

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

Итак, несколько профессионалов, едущих с разницей в скорости примерно в 1%, мучают трассу до посинения. Казалось бы - гораздо интереснее наблюдать за муравейником. Однажды я наткнулся на видео - "ЗАЧЕМ СМОТРЕТЬ ФОРМУЛУ 1?", и понял - мне нужно знать ответ на этот вопрос. Краткое содержание от лица автора:

F1 - вершина автоспорта. Во-первых, из-за скорости. Хотя вообще-то мотоциклы едут быстрее, но зато машины F1 проезжают трассу не за 2 минуты, а за полторы.

Ну быстрые, и что с того? Такие скорости не только увлекательные, но ещё и несут опасность. Вообще многие смотрят F1 ради того, чтобы увидеть аварию. Но просто сидеть и ждать, когда она произойдёт, это так себе. Нужна борьба!

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

Но вообще F1 не заканчивается на трассе, это полноценное шоу за её пределами. Можно следить за новостями и будет очень весело! Так что всё, бегом смотреть.

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

Не ведитесь на эту пропаганду.

@knowledge_accumulator

Revisiting Neural Retrieval on Accelerators [2023]

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

Авторы данной статьи непрозрачно намекают, что использование dot product для генерации кандидатов - отстой. Матрица скалярных произведений всех на всех получается с помощью умножения 2 матриц вдоль размерности длины d - размера эмбеддинга, а значит ранг итоговой матрицы ограничен этим самым d, тогда как реальность сложнее.

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

Начнём с самой первой стадии. Авторы почему-то ненавидят HNSW, и поэтому используют эмбеддинг небольшого размера (64), чтобы можно было проскорить ваще всю базу и получить 100к кандидатов. Но им не нужно ровно 100к, поэтому используется approximate top-k.

Допустим, мы хотим достать 100к из миллиарда. Их будет разделять порог по похожести x. Этот порог можно оценить, засэмплив миллион документов и посчитав похожесть 100-го. Затем можно, используя этот порог, пробежаться по всей базе и отсеять документы. Итоговая сложность алгоритма падает с O(N log k) до O(N + rN * log rk), где r - доля сабсэмплинга. В реальности получается в 2.5 раза быстрее.

Дальше к этим 100к кандидатам применяется так называемая Mixture of Logits (MoL) - модель, которая берёт на вход эмбеддинг пользователя и айтема и выдаёт их похожесть, которая по выразительности находится между MLP и Dot Product.

Оба входных вектора нарезаются на куски размером по d - будем называть их подвекторами. Далее мы берём ku подвекторов пользователя и kx подвекторов документа и считаем ku*kx скалярных произведений друг на друга. Далее этот вектор скалярно умножается на вектор весов pi(x, u), который считается как линейный слой + софтмакс от на основе конката тех самых скалярных произведений и ещё двух векторов юзерных и айтемных фичей.

Авторы уделяют много времени оптимизациям, в том числе дизайна своего GPU kernel, правда, к сожалению, я так и не увидел понятного описания того, во сколько раз в точно таких же условиях оно применяется медленнее, чем dot product. Но суммарно эти 2 стадии могут прожевать в 1.8 раз меньше, чем просто top-k dot product. По качеству оно его при этом сильно превосходит.

@knowledge_accumulator

Чем является язык?

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

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

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

Это же касается и языка. Есть «правильный» язык, которым сторонник таких взглядов объективно посчитал тот, на котором говорит сам, и все остальные должны следовать этой парадигме.

Сотни тысяч лет язык эволюционировал, чтобы то, что получилось именно в 2025 году, стало нужно законсервировать. Необходимо создать министерство языка, которое определяет единственно верные правила, и полностью остановить процесс заимствования новых слов.

А какая у такого взгляда альтернатива? Какие выводы о языке будут вытекать из предположения о том, что человек стоит выше всего?

Во-первых, использовать нужно те слова, которые передадут твою мысль. Большое количество заимствований и англицизмов это не баг и «порча» языка. Zoom out, и вы поймёте, что это не что иное, как объединение многих языков в один в масштабе тысячелетий.

Но самый главный вывод в том, что в языке нет настоящих «правил» и «ошибок». Люди просто придерживаются паттернов, которые упрощают понимание текста. Я, бы мог, ставить, запятые где, угодно, или песать с ашыбками, но всё, к чему это приведёт - повышенное напряжение у читающего и меньшая скорость письма.

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

Официально разрешаю вам использовать «ихний» и даже «егоный», а также одевать одежду. Только Надежду на надевайте.

@knowledge_accumulator

Energy-Based Transformers are Scalable Learners and Thinkers [2025]

Начнём с базы. Обычно в ML преобладают модели типа p(y | x) - то есть, на вход подаются фичи, а на выходе распределение на ответ. У этого есть альтернатива - мы можем иметь модель вида E(x, y) - так называемую энергетическую функцию.

E(x, y) показывает "правильность" пары этих двух объектов - если энергия низкая, то пара подходит друг к другу, а если энергия высокая, то не подходит. Теоретически, эти две схемы эквивалентны - можно считать, что обычный классификатор p(y | x) выдаёт энергию для всевозможных y.

Но на практике E(x, y) обладает большей мощностью при том же количестве параметров. Всё дело в том, что один подсчёт p(y | x) эквивалентен множеству применений E(x, y) для каждого ответа. E(x, y) должна лишь оценить качество ответа, тогда как p(y|x) должна решать задачу, последнее фундаментально сложнее.

Рекомендательные системы, кстати, прекрасно впитали эту идею. На последних стадиях ранжирования мы применяем именно модели вида F(user, item), а не p(item | user). Тут же становится очевидной их главная проблема - для выбора ответа функцию надо применять на каждом y,

В доменах с маленьким количеством классов, включая язык, функция энергии может принимать на вход p(y), т.е, вектор вероятностей каждого ответа. Тогда выбор ответа сводится к решению задачи оптимизации E(x, p(y)) по параметрам p(y). Функцию энергии можно сделать полностью дифференцируемой, и тогда можно применить градиентный спуск. В этом случае оно будет сходится к детерминированному выбору правильного ответа, при условии правильно обученной функции энергии.

Введение можно считать оконченным...

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

Танцы с бубном начинаются именно при обучении энергетической функции - у неё ведь на входе теперь ещё и распределение на все классы. Как и в рекомендациях, в таких моделях можно применять тот самый Constrastive loss, про который я говорил в посте про LogQ correction. Но учить на всём декартовом произведении X и Y это кошмарно дорого, а вообще-то нам нужно выдавать энергию для распределения на Y.

В статье к обучению E(x, p(y)) подходят в лоб. Процедура инференса - оптимизация вектора p(y) градиентным спуском по E(x, p(y)) - это, на секундочку, полностью дифференцируемая операция. Делаем так. Берём случайное p(y). Вычитаем из него N раз градиент E(x, p(y)) по p(y), и потом считаем итоговый лосс как близость финального p(y) и правильного p(y).

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

Перейдём к результатам.

Самое главное - точность на валидации скейлится значительно быстрее с увеличением объёма тренировочных данных и уже обгоняет её на 3 миллиардах токенов. С другой стороны, нужно почти на порядок больше флопсов, чтобы получить то же качество. Учитывая то, что компьют можно удешевлять бесконечно, тогда в как разумных данных мы ограничены, то скейлинг с точки зрения данных является более важным показателем.

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

@knowledge_accumulator

Как Великобритания отупляет своих граждан

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

В статье с очень длинным названием над бедными студентами из Саудовской Аравии провели эксперимент - заставляли решать простые задачки на компе, пока они находились в 9 разных условиях:

- 3 разные температуры - 20, 23, 25 градусов
- 3 разных уровня CO2 - 600, 1000, 1800 ppm

Дизайн исследования весьма своеобразный - всех 499 подопытных помещали последовательно в 9 условий, никакого разделения на группы. Но результат у них явно показывает, что 25 градусов значительно хуже 20 и 23, и уровень углекислого газа тоже сильно влияет. Есть и другие статьи с близким результатом.

Что же происходит в нашем родном Лондонграде?

Примерно 2 месяца в году температура на улице переваливает за 25 градусов, и помещение внутри нагревается соответствующим образом на всё это время, включая ночное.

Согласно вот этому отчёту, лишь около 5% домов в UK имеют кондиционер. Даже двушка в Лондоне за 3 тысячи долларов с большой вероятностью будет без него. Таким образом, всё это время жители UK варятся заживо в своём доме.

Fun fact: В США от шутингов за 2024 год умерло 711 человек. В UK от причин, связанных с перегревом, в 2024-м умерло 1311 человек, а тут живёт в разы меньше людей.

В интернете найдётся много 15-летних эко-активистов, которые скажут "Это всё глобальное потепление, в UK, сколько помню, вообще никогда не было жары, это только щас началось". В реальности, конечно, всё не так, и с 1950-х среднее в июле и августе поднялось меньше чем на 2 градуса.

Но как же так? Неужели жители страны с 50к долларов ВВП на человека не могут позволить себе жить как люди? Важный урок - когда вы видите дебильную ситуацию и вам хочется задать вопрос "Как так?", ответ будет почти всегда один - государство.

Согласно Лондонскому Госплану, застройщик не может просто снабдить дом кондиционером. Он должен доказать кабинетным крысам, что перепробовал все остальные варианты, среди которых, например, "minimise internal heat generation through energy efficient design". В результате, видимо, проще забить и построить дома без кондеев.

Частенько в документах говорят о том, что всё дело в ценах на электричестве - несмотря на распиленные миллиарды фунтов на возобновляемых источниках, цена энергии всё ещё на 98% зависит от цены на газ и поэтому прыгает очень высоко.

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

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

@knowledge_accumulator

С днём AGI-осени?

Люди думали о создании "искусственного интеллекта" с незапамятных времён - не то, что на заре компьютеров, а когда их ещё не было. Думаю, все мы знаем про тест Тьюринга - он был предложен аж в 1950 году! Та самая статья Тьюринга довольно интересно читается сегодня, поскольку мы знаем про AI гораздо больше.

Попытки двигаться в сторону "AGI" не заставили себя ждать. Я уже когда-то писал про программу со скромным названием General Problem Solver из 1957-го. Да в ту эру был даже свой ChatGPT - ELIZA (1966). Рано смеётесь - она обгоняла GPT-3.5 в тесте Тьюринга.

Уже тогда говорили - "Через 3-6 месяцев ELIZA будет писать 90% кода". К сожалению, людишки переоценили свои силы, и в 70-х этот обсёр стал очевиден. Амбиции поубавились и про AGI уже как-то стало стыдно говорить.

В 2012-м свёрточные нейросети ворвались в игру и началась эпоха Deep Learning. Довольно быстро его применили в зрении и других областях, в том числе и в обучении с подкреплением. Статья Playing Atari with Deep Reinforcement Learning [2013] знатно хайпанула - надо же, алгоритм самостоятельно учится играть в игру. Потом Deepmind выпустили AlphaGo [2015].

В тот момент я только начинал изучать ML. Отчётливо помню, что в больших ML-сообществах тема AGI считалась кринжом - серьёзные люди тогда жаловали только серьёзные ML-приложения. Я был среди меньшинства, которое ожидало дальнейших побед RL.

Пик пришёлся на 2018-2019-й - Deepmind AlphaStar и OpenAI Five жёстко хайпанули, продемонстрировав топовый уровень игры в Starcraft 2 и Dota 2. Но это была Пиррова победа. Читая внимательно статьи, становится понятно - всё это работает с горем пополам. Не получается так, как в Go - поставил модельку играть саму с собой и пошёл пить чай - всё это уже не скейлится на такие задачи, и нужно городить кучу костылей и ограничений.

И вот в начале 2020-х AGI снова вошёл в мейнстрим, причём не благодаря решению крутой задачи, а благодаря новой форме подачи - из андэграунда вырвались NLP-ресёрчеры, которые релизнули старую как мир идею - чат-бота, но на основе Deep Learning. Увидев такое, уязвимый человеческий рассудок не устоял перед харизмой статистического попугая. На пару лет те, кто не верили в достижение AGI на основе чат-бота, стали считаться тупыми скептиками.

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

И я очень этому рад! Нас ждёт расцвет реально полезных AI-приложений. xAI релизнули общение с раздевающейся аниме-тёлочкой. Superintelligence Lab Цукерберга даёт возможность пообщаться с Russian Girl или Step Mom, ждём релиза AlphaSex от Google Deepmind. Не сомневаюсь, что в скором времени у нас в домах будут Тесла Оптимусы, выглядящие как Ani, и помимо всего прочего ещё и собирающие грязные носки по дому. Женщина, которую мы все хотели.

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

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

@knowledge_accumulator

Успешная альтернатива квантовым компьютерам, о которой почти никто не говорит

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

Но в так называемом Unconventional Computing есть много разных областей. И сегодня я расскажу об одном из них - ДНК-компьютерах. Сразу предупреждаю - я совсем не биолог, и очень был бы рад получить критику изложения в комментариях от того, кто шарит.

Всё началось в 1994, когда Leonard Adleman опубликовал proof of concept - с помощью ДНК возможно решать вычислительные задачи. Решал он задачу поиска гамильтонова пути в графе (т.е. обходящего все вершины). Она, как я вижу, натурально ложится на этот hardware:

1) Берут молекулы, соответствующие вершинам, и молекулы, соответствующие рёбрам. Их выбирают специально так, чтобы рёбра могли подсоединяться к вершинам графа, которым они соответствуют.
2) Всё это взбалтывают и смешивают. Создаётся куча цепочек молекул, каждая из которых - это валидный путь в графе.
3) Получившиеся молекулы фильтруют с помощью дополнительных реакций, чтобы они соответствовали критериям валидности.

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

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

В чём вообще смысл этой области? Зачем пытаться строить компьютеры в майнкрафте и прочих странных доменах? На самом деле, ДНК-вычисления - это не игрушка, и у них есть жирное преимущество по сравнению с классическими вычислениями - энергоэффективность.

Эволюция потратила миллиарды лет на дизайн энергоэффективных биологических механизмов, и классические компьютеры, кажется, далеко позади. Современные компьютеры выдают десятки миллиардов флопов на 1 джоуль. DNA проводят в 10000000000 больше реакций на 1 джоуль.

Энергоэффективность компьютеров быстро растёт, и на эту тему есть даже аналог закона Мура - Koomey's law. С сохранением текущего тренда, нам нужны ещё несколько десятков лет, чтобы классические компьютеры догнали ДНК. Оговорюсь, что прямое сравнение всё же бессмысленно, пока мы не столкнём два подхода в лоб на одной и той же вычислительное задаче.

Но DNA-вычисления я уважаю даже не за это. Они неоспоримо побеждают классические компьютеры в одном очень важном аспекте, и в нём у классических компьютеров нет и не будет вообще никаких шансов. Это обсудим в следующий раз.

@knowledge_accumulator

Как победить старение при помощи искусственного суперинтеллекта?

Встречается у людей такое представление: СуперИИ - это такой ChatGPT, только очень умный. Если не чат-бот, то человекообразная сущность с бесконечным IQ. Чё-нибудь не то ему скажешь - он тут же уничтожит мир. С другой стороны, есть и оптимистичный взгляд. Скажешь ему - "а сделай так, чтобы люди жили долго, счастливо, и ничем не болели", а он возьмёт и сделает.

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

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

Реальность такова, что даже имея бесконечно умный алгоритм и доступ ко всем знаниям, не сразу понятно, что с этим делать, чтобы победить старение. И тут есть 2 новости - хорошая и плохая. Хорошая - решение всё же есть, а плохая в том, что между созданием интеллекта и победой над старением может пройти ещё не один десяток лет.

Чего я хочу добиться? Человек - это просто набор атомов. Иллюзия, как и все остальные "объекты". Я не верю, что возможно составить формальное техническое описание задачи победы над старением - человек слишком сложная и запутанная машина. Нужен другой подход.

Старение - это изменение организма с течением времени и изменение его свойств. Это обозначает, что если свойства организма не меняются, то и старения тоже нет. Но вместо того, чтобы выписать все эти свойства, воспользуемся Adversarial постановкой.

Победа над старением - это результат битвы между двумя суперинтеллектами, решающие 2 противоположные задачи:

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

Воу-воу-воу. Что ещё за "функция от человека", "воздействие на человека", а как это всё проверять-то? Спокойно, щас всё объясню. Сделаю два смелых предположения.

1) Произвольную "функцию" от человека можно закодировать как генетический код вируса, которые мы даём ему вдохнуть / съесть. Вирусы - это те самые наноботы, о которых мы все мечтаем, только не из железа, а из подходящего для нас hardware. Уверен, что существует очень хитровыебанный вирус, который, попав в наш организм, может развернуть произвольно долгий механизм поддержания его молодости, и даже по часам из него исчезнуть. Именно поэтому я писал про ДНК-вычисления и про их теоретическую мощность. СуперИИ такой вирус сможет найти, как и такой, который "вернёт" возраст человека.

2) Всё это нам придётся симулировать в компьютере. Ко мне уже набегали физики с комментариями, что симулировать физику невозможно. Но я уверен - есть способ симулировать человека на каком-то уровне абстракций так, чтобы он был функционально неотличим от реального. Здесь нам поможет технологическая сингулярность - ИИ вызовет взрывной рост вычислительных мощностей и поможет изобрести новые парадигмы, подходящие для проведения подобных вычислений.

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

@knowledge_accumulator