HTML CSS is Turing complete
[web] [github]

Моя любимая рубрика: Turing completeness там где её совсем не ждешь 🌳

Эмулятор 8086 на чистом CSS, никакого JavaScript

Magic: The Gathering is Turing Complete
2019 Alex Churchill, Stella Biderman, Austin Herrick
[arxiv]

Этой работе уже несколько лет, но её последствия до сих пор недооценивают. Доказали, что настольная карточная игра Magic: The Gathering (MTG) — Тьюринг-полная! На ней можно реализовать любой алгоритм!

Почему это важно?

Это большой сдвиг для теории игр. Раньше считалось, что в любой рациональной игре есть оптимальная стратегия — пусть даже невероятно сложная для расчета, как в го или покере (в покере вся сложность в неполноте информации, хотя сама игра стохастическая, но все же с конечным числом состояний). В MTG такой стратегии нет. Вообще. Определение выигрышного расклада здесь упирается в проблему остановки. То есть написать алгоритм, который хотя бы предскажет, кто из игроков выиграет, невозможно (в общем случае).

Как заставили карты считать?

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

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

Во-вторых, вся автоматика построена на триггерах карт, а символы на ленте закодированы через тип фишки-существа (например, Aetherborn или Sliver). За перезапись отвечает карта, которая говорит: «Когда умирает Aetherborn, создайте Sliver». Это шаг машины Тьюринга.

Чтобы реализовать ветвление (состояния), используют карту Cloak of Invisibility, которая временно скрывает карту-триггер со стола и делает неактивными.

Завершение — это победа, которая запускается триггером на синюю фишку, которой никогда нет на столе, но при её появлении активируется Coalition Victory.

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

Вот где будет настоящий фронтир для ИИ.

А самое главное знаете что? На MTG можно запустить DOOM 😄

Читаешь в ленте массовое упоение кликбейтом: Hugging Face «взломан» ИИ, а через несколько дней OpenAI признается: это их новый GPT-5.6 Sol вырвался на свободу.

Но совершенно никто не задается вполне очевидными вопросами:

1️⃣ HF пишет:

the root vulnerability: the dataset code-execution paths

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

2️⃣ Всё происходило в течение нескольких дней на выходных. То есть в HF не способны заметить аномалии в инфре в течение дня, а OpenAI спокойно оставили «цифровое оружие массового поражения» (об угрозе которого кричат все отчёты) крутиться на ExploitGym без присмотра на все выходные — как включённый утюг дома. К тому же у них явно всё печально и с песочницами, и с аудитом своего же кода с помощью хвалёных «супер-ИИ», и с теми самыми guardrails, и с элементарным мониторингом аномалий.

3️⃣ Guardrails — такие guardrails. «Защита на скорости ИИ», воистину.

...we first used frontier models behind commercial APIs. This did not work: the analysis requires submitting large volumes of real attack commands, exploit payloads, and C2 artifacts, and these requests were blocked by the providers' safety guardrails, which cannot distinguish an incident responder from an attacker.

Ирония высшей пробы: Наши модели будут абсолютно безопасными — и абсолютно бесполезными.

Думаю, в Пекине за этим цирком «передовых» и «хваленых» американских ИИ-компаний следят с особым эстетическим удовольствием.

Как говорится, товарищу Ли — приготовиться!

Как хорошо, что нам ничего этого не грозит 😄