I'm Sun

HTML + CSS3 图灵完备？别逗了

发表于 | 分类于

新奇的说法

在大概几周之前，前端圈子里突然开始流传一种说法，说 HTML + CSS3 是图灵完备的。我已无法考证这个说法最早出自哪里，但网上引用较多的是 StackOverflow 上的一篇问答：Is CSS turing complete?。 排名第一的答案指出 HTML + CSS3 是图灵完备的并给出了证明和实现。

他的逻辑是这样的：HTML + CSS3 可以实现一个 Rule 110 自动机，Rule 110 自动机是图灵完备的，因而 HTML +
CSS3 是图灵完备的。在回答里他还给出了实现方法和一个 Demo。（对细胞自动机不了解的可以看一看我的上一篇博客）

我最开始看到这个问题的时候觉得十分神奇，然后看了看他的源代码，的确是只有 HTML 和 CSS，代码挺有启发性。证明逻辑也没有错误，而且 Rule 110 的图灵完备在 2000 年就已经被证明了，没有什么争议。至于他给出的那个实现，我当时对 Rule 110 并不了解，但是看到那么多人点赞，觉得应该没什么问题吧。

然后我就按照差不多的原理用纯 HTML + CSS3 写了一个简陋的扫雷。而且写得更极端，HTML body 里没有 input 外的任何元素，没有任何 JS，所有行为都靠 CSS 完成（不支持火狐）。项目页面，Github 地址

新奇的实现

当我打算用 HTML + CSS3 写些更复杂的东西的时候却越来越疑惑了，按照那个原理，在我看来最多只能写出一个有限状态机（就像我写的扫雷那样），而且缺失了一些图灵完备的关键特性。所以我在想，他真的实现了 Rule 110 自动机了吗？

首先我们先要了解一下什么是 Rule 110 自动机，我在上一篇博客里对其进行了介绍。然后我们先看一看他实现的原理，我把 StackOverflow 上的实现代码粘了过来：

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
<!DOCTYPE html>
<html lang="en">
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
        <title>Rule 110</title>
        <style type="text/css" media="screen">
            body {
                -webkit-animation: bugfix infinite 1s;
                font-family: "Courier New";
                font-size: 28px;
            }
            @-webkit-keyframes bugfix { from { padding: 0; } to { padding: 0; } }
            /* 111 110 101 100 011 010 001 000
0 1 1 0 1 1 1 0 */
            body > input {
                -webkit-appearance: none;
                display: block;
                float: left;
                border-right: 1px solid #ddd;
                border-bottom: 1px solid #ddd;
                padding: 5px 12px;
                margin: 0;
            }
            body > input::before {
                content: "0";
            }
            body > input:nth-of-type(-n+30) { border-top: 1px solid #ddd; }
            body > input:nth-of-type(30n+1) { border-left: 1px solid #ddd; clear: left; }
            body > input::before { content: "0"; }
            body > input:checked::before { content: "1"; }
            body > input:checked { background: #afa !important; }
            input:not(:checked) +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input::before {
                content: "1";
            }
            input:not(:checked) +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input {
                background: #fa0;
            }
            input:checked +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input::before {
                content: "1";
            }
            input:checked +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input {
                background: #fa0;
            }
            input:checked +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input::before {
                content: "1";
            }
            input:checked +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input {
                background: #fa0;
            }
            input:checked + input:checked + input:checked +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input::before {
                content: "0";
            }
            input:checked + input:checked + input:checked +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input {
                background: #fff;
            }
            input:not(:checked) + input:not(:checked) + input:not(:checked) +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input::before {
                content: "0";
            }
            input:not(:checked) + input:not(:checked) + input:not(:checked) +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
                    input {
                background: #fff;
            }
            body > input:nth-child(30n) { display: none !important; }
            body > input:nth-child(30n) + label { display: none !important; }
        </style>
    </head>
    <body>
        <input type="checkbox" />
        <input type="checkbox" />
        /* A total of 900 checkboxes required */
        <input type="checkbox" />
        <input type="checkbox" />
    </body>
</html>

实现的精髓在于 CSS 选择器。关键点有两个，一个是 CSS 可以通过 :checked 伪类和 :not 运算来检查 HTML 里 checkbox 的状态，也就是 input:checked 和 input:not(:checked)；另一个是 CSS 可以通过兄弟选择器来检查位于自己之前的某个元素的状态。

1
2
3
4
5
input:checked + input:checked + input:checked +
        *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+
        input {
    background: #fff;
}

上面这段代码表示，如果从一个 input 元素往前数，第 29、30、31 个元素为 input 而且状态都是 checked 的话，那当前元素的背景色为 #fff。这就是点击一行中的 checkbox 会改变下一行 checkbox 颜色的原理。根据这个原理就能构造出 Rule 110 的演化规则了。

问题出在哪里

我们先看一下一个真正的 Rule 110 自动机和 StackOverflow 里给出的 Rule 110 有什么不同：

这是一个正常的 Rule 110

这是答案中 HTML + CSS3 实现的 Rule 110

区别已经很明显了。在正常的自动机里演化过程是自动进行的，而第二个 “自动机” 的只能根据上一行的结果告诉你下一行将会演化成什么样子，只有你手动把该行的状态点击成演化后的样子，他才能告诉你再下一次演化的结果。

说白了，这连细胞自动机都算不上，顶多算一个 “手动机”，更别提什么图灵完备（因为它的确只实现了有限状态机的功能）。如果这都可以算图灵机，那很多有限状态机都可以实现图灵机了。

不过很遗憾，这种说法已经流传甚广，在 Google 里搜索 “CSS turing complete” 就能看到大量的相关报道。连我的很多后端朋友都知道 CSS 是图灵完全的了。

CSS有没有可能图灵完全？

不过说远一点，CSS 有没有可能图灵完全呢？

个人认为这希望渺茫而且没有什么意义。CSS 曾经的一个重要原则是不发生回溯（不过 CSS3 里的一些选择器打破了这一原则），这保证了在浏览器加载的过程中，后加载元素不会影响之前元素的渲染，从而提高渲染效率，实现边加载边渲染。如果 CSS 图灵完全了，可以预想到会出现大量回溯和循环的用法，这是在令人担忧。