Home
/ source / content / articles / turing_complete_css / .about.html
Download Direct linkSettings
Aa
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
Copy 
{%- 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 -%}