В формате JPEG XL это изображение занимает 59 байт
Оказывается, полным по Тьюрингу может быть не только язык программирования, но и графический формат. В частности, таким потенциально является формат JPEG XL, если отменить в нём ограничение на максимальный размер группы обрабатываемых пикселей.
Новый свободный формат разработан для замены существующим форматам растровой графики (JPEG, PNG, WebP, HEIC, JPEG 2000 и проч.), может работать на сервере прозрачно, вместе с JPEG (уменьшение размера JPEG на 20% без потери качества). Финальная версия стандарта зафиксирована 25 декабря 2020 года. Новый кодек основан на инновационных разработках Google PIK и Cloudinary FUIF, но превосходит их. Самое главное, что он лишён недостатков тех графических форматов, которые основаны на видеокодеках: это WebP (основан на VP8), HEIC (HEVC) и AVIF (AV1).
Пример использования JPEG XL на сервере
Полнота по Тьюрингу — фундаментальное понятие в информатике. В теории вычислимости означает возможность реализовать на данном вычислителе любую вычислимую функцию. То есть для каждой вычислимой функции существует вычисляющий её элемент, а все функции являются вычислимыми. Свойство названо по имени Алана Тьюринга, разработавшего первый абстрактный исполнитель — машину Тьюринга, способную имитировать всех исполнителей путём ряда достаточно элементарных шагов.
Дело в том, что в формат изображений JPEG XL включает в себя так называемые «предикторы» — небольшие программы, которые улучшают сжатие, выражая цвет пикселя в терминах цветов его соседей.
В формате JPEG XL это изображение занимает 55 байт, hex-дамп:
ff 0a fa 1f 01 91 08 06 01 00 ac 00 4b 38 42 36 61 47 a9 65 f3 43 ee 2f 2a 0e 7c f9 fd 73 90 70 e0 14 0f e9 82 32 f4 64 10 32 c9 90 02 59 91 0a 01 45 06 00 60 02 00 Украинский математик и программист Даниил Богдан, бывший ведущий инженер Института математики НАН Украины первым показал, что в предикторах JPEG XL можно реализовать клеточный автомат под названием «Правило 110».
Ранее было доказано, что клеточный автомат с правилом 110 является Тьюринг-полным и с его помощью может быть реализована любая вычислительная процедура. Возможно, что это самая простая система, полная по Тьюрингу.
Построение следующего поколения одномерного клеточного автомата с использованием правила 110, cormullion
Но есть один нюанс.
Хотя правило 110 является полным по Тьюрингу, но предикторы JPEG XL не являются полными по Тьюрингу сами по себе. Чтобы обеспечить параллельное кодирование и декодирование, кодек JPEG XL работает с «группами» пикселей размером до 1024х1024. Таким образом, сам JPEG XL не является полным по Тьюрингу, но его версия без ограничения 1024*1024 пикселей была бы полной, пишет Богдан.
Даниил Богдан написал код в формате для предикторов JXL, который можно загрузить и запустить в песочнице JXL Art.
В ответ на критику с Reddit математик поясняет: «Мы можем генерировать любое начальное состояние с условиями на x для y = 0 (на одно условие меньше, чем существует непрерывных последовательностей нулей и единиц). Мы эмулируем бесконечно повторяющиеся серии правил и тактовых импульсов с помощью серий, достаточно длинных для вычислений. Начинаем с фиксированных размеров, генерируем серию и запускаем вычисления. Если система тегов не останавливается, мы удваиваем размер изображения и повторяем попытку, пока она не остановится или у нас не закончится память. Это так же близко к Тьюринг-полноте, как и другие виртуальные машины на физическом компьютере (если я не прав, исправления приветствуются!)».
Архитектура кодека JPEG XL
Основные функции JPEG XL
- Улучшенная функциональность и эффективность по сравнению с JPEG, GIF и PNG, см. сравнение JPEG XL с другими кодеками;
- Перекодирование JPEG без потерь с уменьшением размера примерно на 20%;
- Размер изображения более миллиарда (230-1) пикселей с каждой стороны;
- До 4100 каналов, т.е. оттенков серого или RGB, опционально альфа-канал, и до 4096 «дополнительных» каналов;
- Транскодирование прогрессивных JPEG поддерживается форматом, но пока не реализовано в эталонном ПО;
- Кодирование без потерь и альфа-кодирование без потерь;
- Поддержка как фотографических, так и синтетических изображений;
плавное снижение качества в широком диапазоне битрейтов;
- Оптимизированный для восприятия эталонный кодер;
- Поддержка широкой цветовой гаммы и HDR;
- Поддержка анимаций;
- JPEG XL кодируется и декодируется так же быстро, как старый JPEG с использованием libjpeg-turbo, и на порядок быстрее HEIC с x265. Он также поддаётся распараллеливанию.
- Формат совершенно свободный с эталонной реализацией и открытым исходным кодом.
По субъективной оценке качества, JPEG XL сжимает без визуальных потерь (синяя область) на тех же битрейтах, что HEVC-HM-Y444
P.S. Есть мнение, что полнота по Тьюрингу окружает нас повсюду. Вообще трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему: «В обычном смартфоне или настольном компьютере будет от пятнадцати до нескольких тысяч компьютеров в смысле тьюринг-полных устройств. Каждое из них можно запрограммировать, оно обладает достаточной мощностью для запуска многих программ и может быть использовано злоумышленником для наблюдения, эксфильтрации или атак на остальную часть системы», — писал в 2018 году американский исследователь Гверн Бранвен, приводя множество примеров:
«Наверное, в наше время многие не знают, что TrueType и многие шрифты — это программы PostScript на стековых машинах, похожие на метаданные ELF и отладочную информацию DWARF. Или что некоторые музыкальные форматы выходят за рамки MIDI, поддерживают скрипты и нуждаются в интерпретации. Если знать о тьюринг-полноте шрифтов, то уже не удивляет полнота по Тюрингу документов TeX, что естественно вызывает многие серьёзные и интересные уязвимости в безопасности шрифтов и медиа, такие как BLEND или Linux-эксплоиты SNES и NES.
Несмотря на полноту по Тьюрингу, похоже, декодер JPEG XL не представляет угрозы безопасности: говорят, что вычисления ограничены отдельными пикселями и не позволят декодеру уйти в бесконечный цикл или нечто подобное.
