Эксперименты начинаются со всеми любимого брейнфака (кстати, не знал, что есть такой прекрасный вариант упоминания как “b**fuck”). Кто не знает, brainfuck -- минималистичный язык вдохновлённый машиной Тьюринга. Используется чуть расширенная версия языка (это семейство далее зовётся BFF) -- вместо ввода-вывода есть две головы, читающие одну общую для данных и команд ленту, и операции, копирующие данные между головами. Поскольку ввода-вывода нет, строки программ могут взаимодействовать только друг с другом. Никаких явных фитнес-функций не задаётся и программы предоставлены сами себе для выполнения кода и перезаписи себя и соседей. Как показывают авторы, этого достаточно для возникновения само-репликаторов. Основной тип используемых в статье симуляций -- вариант газа Тьюринга (Turing gas) из вышеупомянутой Algorithmic chemistry. В этом газе большое число программ (2^17) формируют первичный бульон. Каждая программа содержит 64 однобайтовых символа (которые могут быть как данными, так и инструкциями -- из 256 возможных значений 10 отведено под инструкции, одна под ноль для выхода из циклов и остальное для данных). Символы всех программ инициализированы из равномерного распределения. Большой рандомный исполнимый бульон в общем. Новые программы ни добавляются, ни убираются в процессе, только само-модификация или фоновые мутации. Программы взаимодействуют друг с другом следующим образом: в каждую эпоху выбираются случайные пары программ, программы в паре конкатенируются и результирующий код выполняется фиксированное количество шагов или пока программа не остановится. Обычно это модифицирует обе программы. В конце они разделяются и возвращаются обратно в суп. Взаимодействие между двумя программами интерпретируется как необратимая химическая реакция, где порядок важен. A + B → split(exec(AB)) = A′ + B′ B + A → split(exec(BA)) = B′′ + A′′ В этом ключе само-репликатор может выглядеть как автокаталитическая реакция программы S и пищи F: S + F → split(exec(SF)) = 2 · S Это не ловит кейсы с циклами длиной больше единицы. Также это не ловит кейсы репликации со смещением, отличным от 64. Авторы предлагают свою меру сложности -- high-order entropy, которая для строки длины n вычисляется как разность между энтропией Шеннона (посчитанной по отдельным байтам) и нормализованной (делённой на n) Колмогоровской сложности. С Колмогоровской сложностью сложно (она невычислима), поэтому здесь её аппроксимировали размером сжатой с помощью SoTA архиватора строки (использовался `brotli -q2`, https://github.com/google/brotli, вариант LZ компрессора). Эта метрика подходит по двум причинам: 1. Для последовательности из `n` i.i.d. символов ожидаемая энтропия высокого порядка сходится к нулю при n стремящемся к бесконечности (то есть случайный шум будет иметь нулевую сложность). 2. Для последовательности `k` i.i.d. символов с распределением D ожидаемая энтропия высокого порядка строки, сформированной конкатенацией n копий этих символов сходится к энтропии Шеннона для D по мере того как n стремится к бесконечности (суп из кучи копий одной и той же строки будет иметь заметно ненулевую сложность). Для отслеживания истории символов к ним цепляют дополнительную информацию, так что они являются кортежами (epoch, position, char) упакованными в int64 токены. На старте симуляции есть 2^17 строки по 64 символа, что даёт 2^23 = 8M уникальных токенов при инициализации. Анализ токенов позволяет отследить изменение состояния. Без изменения состояния количество уникальных токенов в супе постепенно уменьшается и стабилизируется на 3M уникальных токенов, где мутации и случайные репликации балансируют друг друга. Изменение состояния вызывает резкое уменьшение числа уникальных токенов и в супе начинают доминировать небольшое число id токенов. Благодаря добавленной к символам информации можно отследить конкретную эпоху и строку, где возник первый репликатор. История одного репликатора** Одна из историй развивается следующим образом (картинка 2).