Конец 2024 года стал временем неопределенности для всех, и теоретическая информатика не осталась в стороне. В этой области случились как серьезные прорывы и открытия, так и столкновения с границами возможного.
Искусственный интеллект, как и прежде, не сходил с первых полос. Исследователи начали понимать, что творится внутри “черных ящиков” – нейронных сетей, на которых работают чат-боты вроде Bard и ChatGPT. Им удалось показать, что эти системы действительно понимают данные, с которыми работают и которые создают. При этом все больше признаков указывает на то, что прогресс в области ИИ уже начал замедляться.
В других областях дела шли увереннее. Спустя десятилетия поисков наконец удалось поймать за хвост загадочное числовое существо – пятого занятого бобра. Правда, и тут не все гладко: первые попытки найти его преемника, шестого занятого бобра, говорят о том, что он может скрываться за непреодолимым математическим “забором”.
В 2024 году громко заявила о себе и теория помехоустойчивого кодирования – математических конструкций, которые умеют сами исправлять возникшие ошибки. Исследователи впервые доказали, что метод исправления ошибок, без которого немыслимы квантовые компьютеры, действительно работает. Однако, согласно другому открытию, некоторые классические помехоустойчивые коды неэффективны по своей природе.
Танцы с бобрами
Задача пятого занятого бобра, названная в честь особого типа компьютерных программ с длительным временем выполнения, тесно связана с глубочайшими нерешенными вопросами в информатике и математике.
Речь идет о машинах Тьюринга – простейших вычислительных устройствах, которые Алан Тьюринг придумал как модель универсального компьютера. Сегодня их легко опробовать онлайн.
Машина Тьюринга работает по заданным правилам. У него есть бесконечная лента памяти, разделенная на ячейки, и “головка”, которая может читать и записывать символы в эти ячейки, а также двигаться влево или вправо.
Правила – это инструкции вроде “если в текущей ячейке стоит 0, замени его на 1 и сдвинься влево”. Каждое такое действие считается одним шагом. Чем больше правил мы даем машине, тем сложнее будет ее поведение.
Представим, что мы дали машине определенное число правил и запустили ее. Она начнет выполнять алгоритм шаг за шагом. В какой-то момент она может зациклиться и работать вечно. А может остановиться, если попадет в ситуацию, для которой нет подходящего правила. Загадка “занятого бобра” гласит: если машина все-таки остановится, то какое максимальное число шагов она может сделать перед остановкой?
Ученые уже нашли ответы для простых случаев. Если у машины всего одно правило – она остановится максимум через один шаг. Если правил два – через шесть шагов, если три – через 21 шаг, если четыре – через 107 шагов. Но вот пятый случай оказался настолько сложным, что его не могли решить десятки лет.
И вот наконец группа энтузиастов справилась с задачей . Они не только нашли ответ – 47 176 870 шагов, но и доказали, что большего числа быть не может. Хотя эта задача вряд ли найдет практическое применение, ее решение – настоящий триумф человеческого разума над математикой. А вот с поиском шестого числа дела обстоят совсем печально: первые попытки показывают, что оно может оказаться принципиально недостижимым.
В январе произошло еще одно интересное событие: любители математики помогли разгадать загадку знаменитой игры “Жизнь” , которую придумал Джон Конвей. Они искали в ней повторяющиеся комбинации клеток и нашли такие, которые воспроизводятся через 19 и через 41 шаг. Таким образом команда доказала удивительное свойство игры: в ней можно найти узор, который будет повторяться через любое заданное число шагов. Ученые называют это свойство “омнипериодичностью”.
Лучшая жизнь благодаря коду
Квантовые компьютеры давно будоражат умы ученых, но несмотря на годы работы, создать по-настоящему полезную и эффективную машину пока не удается. Отчасти виновата их природа: в таких технологиях используются странности квантовой механики, то есть законов, которые управляют мельчайшими взаимодействиями во вселенной. Из-за этого они очень уязвимы к ошибкам. Почти 30 лет назад исследователи показали: кубиты, квантовые аналоги компьютерных битов, можно объединять так, чтобы они устраняли “баги”. Но для этого частота ошибок каждого кубита должна быть ниже определенного порога.
В декабре команда Google впервые смогла добиться такой точности в работе системы коррекции ошибок , что теперь можно уверенно сказать – эти необычные машины действительно можно будет создать. Правда, очень нескоро.
Исследователи также предложили новый подход к борьбе с ошибками, основанный на апериодических мозаиках – наборах фигур, из которых можно сложить бесконечный узор, но он никогда не будет повторяться полностью. Как в случае с мозаиками, и в случае с защитными кодами действует один принцип: изучив небольшой фрагмент, невозможно понять, как устроена вся система целиком.
И это не все новости – человечество наконец разобралось с помехоустойчивыми кодами для обычных компьютеров. Их самые многообещающие варианты всегда смущали своей неэффективностью. Исследователи два десятилетия искали способ это исправить, но теперь получили окончательный ответ: увы, проблема неразрешима в принципе.
Новости квантового мира
Многие важнейшие открытия года помогли лучше понять загадочный мир квантовой механики с помощью методов информатики. На субатомном уровне взаимодействия частиц невероятно сложны, и ученым до сих пор трудно было полностью разобраться даже в простейших квантовых системах. Но четверо информатиков создали алгоритм , который может эффективно описать любой такой набор частиц – впервые в истории науки. Объединив математическую оптимизацию с особым приемом под названием “релаксация”, исследователи научились быстро выводить гамильтониан – универсальное уравнение, полностью описывающее поведение квантовой системы. Правда, этот метод работает только при неизменной температуре.
Та же группа ученых сделала еще одно важное открытие в физике микромира. Они математически доказали: для каждой системы существует своя критическая точка – температура, при которой связь между частицами, известная как “запутанность” , разрывается полностью.
Другие исследователи обнаружили, что некоторые задачи квантовой физики, например, поиск локального минимума энергии, могут оказаться сравнительно простыми для вычислительных машин нового поколения.
Растущее понимание ИИ
Искусственный интеллект, пожалуй, остается самой яркой и одновременно самой загадочной областью теоретической информатики. В этом году OpenAI, создатели ChatGPT, представили новую серию чат-ботов o1 , невероятно сообразительных. Однако, несмотря на впечатляющие успехи, никто до конца не понимает , как устроены системы, из-за чего они остаются уязвимыми для взломов и других проблем.
Больше всего интересует такой вопрос: действительно ли эти модели осознают смысл того, о чем говорят, или по своей сути они лишь ” стохастические попугаи “, которые умеют только по-разному комбинировать ранее увиденную информацию? Последние исследования говорят в пользу первого варианта. Команда Google DeepMind проанализировала, какие навыки позволяют LLM достигать таких впечатляющих результатов, и пришла к выводу: нет, простого перебора данных тут недостаточно. “Модели создают убедительные тексты, объединяя свои способности и темы такими методами, которых почти наверняка не было в обучающих данных”, – объясняет пионер ИИ Джефф Хинтон , получивший в 2024 году Нобелевскую премию по физике за работы в области машинного обучения.
Ученые обнаружили и другое любопытное явление под названием “гроккинг” : если модель тренировать дольше обычного, она неожиданно выходит на качественно новый уровень понимания задачи.