{%- extends "article/base.html" -%}

{%- block meta -%}
{
"date": "2022.04.22",
"number": 1
}
{%- endblock -%}


{%- block title -%}
Тьюринг-полнота CSS
{%- endblock -%}


{%- block description -%}
Создание чуть более близкой к полноте по Тьюрингу веб-странички без JS.
{%- endblock -%}


{%- block article -%}
{%- filter markdown -%}

Если загуглить что-то вроде "Является ли CSS полным по Тьюрингу", первыми ответами в
поисковом запросе будут реализации [Правила 110][R110] - одномерного клеточного автомата
с доказанной полнотой по Тьюрингу. Пример другого известного клеточного автомата -
[игра "Жизнь"][GoL]. Он тоже полон по Тьюрингу, но излишне сложен в силу двухмерности.

![Rule 110 illustration][img_rules]
*Первые 16 шагов правила 110, Стартовая позиция - 1 клетка в центре. [Источник][S]*

[R110]: https://ru.wikipedia.org/wiki/Правило_110
[GoL]: https://ru.wikipedia.org/wiki/Игра_«Жизнь»
[S]: https://mathworld.wolfram.com/ElementaryCellularAutomaton.html


## Что уже есть

Реализаций можно найти множество: на [Stackoverflow][SO], на [Github][GH], на [сайтах
других людей][NL]. Однако все, что я нашёл, имеют существенное "но" - HTML + CSS
страничка во всех этих примерах требует от пользователя прокликивать подсвеченные ячейки.
Данное действие тоже автоматизируется, например в [этом примере][EF] выше достаточно
многократно нажимать Tab и пробел, однако у меня возник вопрос: можно ли минимизировать
ввод от пользователя, сохранив функциональность?

[SO]: https://stackoverflow.com/a/5239256/11842314
[GH]: https://github.com/brandondong/css-turing-machine
[NL]: https://notlaura.com/is-css-turing-complete
[EF]: http://eli.fox-epste.in/rule110-full.html


## Чем можно воспользоваться

С 2016 года [большинство][CIU] современных браузеров начали поддерживать
"пользовательские свойства", или, проще говоря, переменные в CSS. Это может звучать как
ультимативное решение, однако стоит учесть их ограничения: в CSS нет массивов, нет
логического типа данных, есть всего 4 базовые арифметические операции (стандартные
`+`, `-`, `*` и `/`), и, что самое главное - куда сложнее организовать подобие циклов.

[CIU]: https://caniuse.com/css-variables

Любой CSS с рекурсивным вычислением переменных в одной области видимости автоматически
перестаёт вычислять их значения, так что придётся хитрить. Первая идея - использовать
рекурсивно вложенные блоки. Так как CSS - это *каскадные* таблицы стилей, значение
переменной, вычисленной в конкретном блоке, доступно только в нём и его потомках. Но его
можно переопределить в любом подблоке, как в более локальной области видимости, по
аналогии с обычными языками программирования.

Саму логику вычислений можно организовать, используя числа 1 и 0 и логические операторы
из арифметических операций. Я нашёл целую [статью][CL] про то как их можно собрать и
применить на практике для 3D на чистом CSS. 

[CL]: https://css-tricks.com/logical-operations-with-css-variables

Формула правила 110 есть на русской википедии (на английской нет):
`(p, q, r) ↦ (q AND (NOT p)) OR (q XOR r)`.

Простейший способ записать `NOT` арифметически - `(1 - x)`, `AND` - `(x * y)`. Этих
двух операторов уже достаточно для функционально полной системы, и из них легко
выводится `OR` по закону де Моргана - `(1 - (1 - x) * (1 - y))`,
и `XOR` - `(x + y - 2 * x * y)`.

Итоговая формула в арифметической записи:
``` CSS
1 - (
    1 - (q * (1 - p))
) * (
    1 - (q + r - 2 * q * r)
)
```

## Первая реализация

[Висит тут][v0]. [Исходник на Jinja][vs0].

Ввод данных работает так же, как и в других примерах - на чекбоксах в первой строке.

Во избежание циклических формул каждая последующая строка находится на 2 уровня
вложенности глубже, чем предыдущая: на первом значение из переменных `v` дублируется в
`b`, а на втором значение более локальных `v` вычисляется по формуле из `b`. Итоговое
количество переменных - по две на столбец, с нумерацией с нуля: `--v0` и `--b0`, `--v1` и
`--b1` и так далее.

Вывод данных осуществляется при помощи классов `ci`, которые меняют цвет по формуле
`hsl(0, 0%, calc(100% - 100% * var(--vi)))`, становясь чёрными, если соответствующая
переменная `--vi` равняется единице.

После небольшой доработки декоративной части пример заработал... первые 4 шага.

![Rule110 v0][img_v0]
*Строка ввода, вычисленные 4 шага и пустые ряды внизу.*


## Оптимизация

Вполне ожидаемо в браузерах есть существенные ограничения, которые останавливают
вычисление формулы на четвёртой итерации. Из интересного, в Firefox эти ограничения куда
меньше - вычисляется сразу 6 шагов, что всё ещё мало, но больше, чем в Chromium.

Опытным путём выяснилось, что браузеру не важно количество операторов в формуле, но важно
количество использованных в формуле упоминаний переменных - чем меньше ссылок на
предыдущий ряд, тем больше строк вычисляется. В формуле в Википедии в записи с логическими
операторами переменных всего 4, однако оператор `XOR` в аналитическом виде имеет в себе по
2 записи входных переменных, итого 6. У меня получилось сократить её до 5:
`(p, q, r) ↦ (q OR r) AND NOT (p AND q AND r)`
с соответствующей куда более короткой аналитической записью:
`(1 - (1 - q) * (1 - r)) * (1 - p * q * r)`.

[Страничка c новой формулой][v1], [её исходник][vs1]. Оптимизация формулы добавляет по ещё
одному шагу как в Chromium, так и в Firefox, что позволяет в полной мере раскрыть
потенциал правила и вывести амогуса.

![Rule110 v1][img_v1]
*sus.*

Любопытному читателю предлагается (в интересах автора, конечно же) попробовать
оптимизировать формулу ещё сильнее или доказать невозможность выразить её записью менее
чем с 5 переменными.

Второй идеей для оптимизации было попробовать убрать промежуточные переменные `--bi`, для
чего я убрал вложенность и сделал отдельную переменную для каждой ячейки, но как оказалось
это ни на что не влияет - как не ухудшает ситуацию из-за 100 отдельных переменных в CSS
вместо 20, так и не улучшает из-за отсутствия дублирования значений и меньшей вложенности.

В любом случае посмотреть на попытку можно [тут][v2], [исходник][vs2].

![Rule110 full result][img_v2]
*Последняя версия в Firefox*

## Можно ли это применить?

В виде машин Тьюринга - вряд ли, но на одном CSS можно делать очень даже интерактивные
игры, я нашёл [целый сборник][CG] таких. Из самого примечательного в ней есть полностью
рабочий [сапёр][MS], хоть и с неудобным управлением, и ["платформер"][PG] с персонажем в
виде мышки.

![Minesweeper][img_ms]

[CG]: https://codepen.io/collection/AKkZro?cursor=ZD0wJm89MCZwPTEmdj00
[MS]: https://codepen.io/bali_balo/pen/BLJONZ
[PG]: https://codepen.io/nathantaylor/pen/KaLvXw


## Не пригодившееся

Помимо статьи про логические операторы, я нашёл и [статью][CO] про более сложные
математические функции (для реализации 3D): модуль, [сигнум][SGN], округление и остаток
от деления, но все они построены на экспериментальном правиле `@property`, которое пока
что [поддерживается не всеми браузерами][CIU_P].

[CO]: https://css-tricks.com/logical-operations-with-css-variables/
[SGN]: https://ru.wikipedia.org/wiki/Sgn
[CIU_P]: https://caniuse.com/mdn-css_at-rules_property

{% set dl = "/articles/turing_complete_css" %}
{% set rl = "/raw/content" + dl %}
{% set sl = "/source/content" + dl %}

[img_rules]: {{rl}}/rule110.svg
[img_v0]: {{rl}}/v0.png
[img_v1]: {{rl}}/v1.png
[img_v2]: {{rl}}/v2.png
[img_ms]: {{rl}}/ms.png
[v0]: {{dl}}/v0.j2
[v1]: {{dl}}/v1.j2
[v2]: {{dl}}/v2.j2
[vs0]: {{sl}}/v0.j2
[vs1]: {{sl}}/v1.j2
[vs2]: {{sl}}/v2.j2

{%- endfilter -%}
{%- endblock -%}