Каталог программных конструкций, языков и API, которые неожиданно являются полными по Тьюрингу; последствия этого для безопасности и надёжности. Приложение: сколько компьютеров в вашем компьютере? Любая достаточно сложная программа на Си или Фортране содержит заново…
ВведениеМы покажем, что система, имеющая лишь команды GNU find и mkdir, полна по Тьюрингу.Хорошо известно, что команды sed и awk сами по себе полны по Тьюрингу, но мне не удалось найти информации о Тьюринг-полноте find + mkdir.Доказательство основано на реализации таг-системы.Мы по порядку рассмотрим реализацию цикла, FizzBuzz и таг-системы. Читать далее
В формате JPEG XL это изображение занимает 59 байт Оказывается, полным по Тьюрингу может быть не только язык программирования, но и графический формат. В частности, таким потенциально является формат JPEG XL, если отменить в нём ограничение на максимальный размер группы обрабатываемых пикселей. Читать дальше →
Задавались ли вы когда-нибудь вопросом, можно ли полноценно программировать при помощи директивы #define в языке C? Полнота по Тьюрингу шаблонов C++ известна весьма широко, например, люди пишут трассировщики лучей, делающие все вычисления во время компиляции (вместо времени…