39

看完这个问题CSS Turing 是否完整？——收到了一些深思熟虑、简洁的答案——这让我想知道：HTML 图灵完备吗？

尽管简短的回答是肯定的是或否，但也请提供简短的描述或反例来证明 HTML 是否是图灵完备的（显然不能两者兼而有之）。其他版本的 HTML 的信息可能很有趣，但正确的答案应该是HTML5的答案。

4

2 回答 2

33

就其本身（没有 CSS 或 JS）而言，HTML（5 或其他）不可能是图灵完备的，因为它不是机器。询问是否是，本质上等同于询问苹果或橙子是否是图灵完备的，或者举一个更相关的例子，一本书。

HTML 不是“运行”的东西。它是一种代表。它是一种格式。它是一种信息编码。不是一台机器，它不能在图灵完整性级别或任何其他级别上自行计算任何东西。

于 2015-06-08T21:30:51.300 回答
17

我似乎很清楚，状态和转换可以分别用页面和超链接在 HTML 中表示。有了这个，人们可以实现确定性有限自动机，其中点击链接在状态之间转换。例如，我实现了一些简单的 DFA，可在此处访问。

虽然 DFA 比图灵机简单得多。为了实现更接近 TM 的东西，除了基本的状态/转换功能之外，还需要一个涉及读取和写入内存的额外机制。但是，HTML 似乎没有这种特性。所以我会说 HTML 不是图灵完备的，但能够模拟 DFA。

编辑：在写这个答案时，我想起了关于 PowerPoint 的图灵完整性的视频。

编辑：用 DFA 定义和说明补充这个答案。

定义

来自https://en.wikipedia.org/wiki/Deterministic_finite_automaton#Formal_definition

在计算理论中，作为理论计算机科学的一个分支，确定性有限自动机 (DFA)——也称为确定性有限接受器 (DFA)、确定性有限状态机 (DFSM) 或确定性有限状态自动机 (DFSA)——是一个有限状态机，它通过运行由字符串唯一确定的状态序列来接受或拒绝给定的符号字符串。

确定性有限自动机 M 是一个 5 元组 (Q, Σ, δ, q0, F)，包括

  • 一组有限状态 Q
  • 一组有限的输入符号，称为字母 Σ
  • 转移函数 δ : Q × Σ → Q
  • 初始或开始状态 q0
  • 一组接受状态 F

以下示例是具有二进制字母表的 DFA M，它要求输入包含偶数个 0。

M = (Q, Σ, δ, q0, F) 其中

  • Q = {S1, S2}
  • Σ = {0, 1}
  • q0 = S1
  • F = {S1} 和
  • δ 由以下状态转移表定义：
0 0
s1 s2 s1
s2 s1 s2

M的状态图：

M的状态图

状态 S1 表示到目前为止输入中有偶数个 0，而 S2 表示奇数。输入中的 1 不会改变自动机的状态。当输入结束时，状态会显示输入是否包含偶数个 0。如果输入确实包含偶数个 0，则 M 将在状态 S1 结束，这是一个接受状态，因此输入字符串将被接受。

HTML 实现

上面举例说明的 DFA M 以及一些最基本的 DFA 是在 Markdown 中实现的，并由 Github 转换/托管为 HTML 页面，可在此处访问。

按照 M 的定义，其 HTML 实现详述如下。

  • 状态集 Q 包含页面s1.html和s2.html，以及接受页面acc.html和拒绝页面rej.html。这两个附加状态是一种“用户友好”的方式来传达单词的接受情况，并且不会影响 DFA 的语义。
  • 符号集合 Σ 定义为符号 0 和 1。还包括空字符串符号 ε 以表示输入的结束，导致输入acc.html或rej.html状态。
  • 初始状态 q0 是s1.html。
  • 接受状态的集合是 { acc.html}。
  • 转换集合由超链接定义，使得页面s1.html包含一个链接，文本“0”s2.html指向 ，文本“1”指向s1.html，以及文本“ε”指向acc.html。根据下面的转换表，每一页都是类似的。Obs：acc.html并且rej.html不包含链接。
0 1 ε
s1.html s2.html s1.html acc.html
s2.html s1.html s2.html rej.html

问题

  • 这些 HTML 页面以何种方式成为“机器”？这些机器不包括浏览器和点击链接的人吗？链接以什么方式执行计算？

DFA 是一个抽象机器，即一个数学对象。通过上面所示的定义，它是一个元组，根据一组符号定义状态之间的转换规则。这些规则的实际实现（即谁跟踪当前状态、查找转换表并相应地更新当前状态）则超出了定义的范围。就此而言，图灵机是一个类似的元组，其中包含更多元素。

如上所述，HTML 实现完整地表示了 DFA M：每个状态和每个转换分别由一个页面和一个链接表示。浏览器、点击和 CPU 在 DFA 的上下文中是无关紧要的。

换句话说，正如@Not_Here 在评论中所写：

规则本身并不是天生的，它们只是实现应该遵循的规则。这样想：图灵机不是真正的机器，图灵没有制造机器。它们是纯粹的数学对象，它们是集合（状态、符号）的元组和状态之间的转换函数。图灵机是纯粹的数学对象，它们是关于如何实现计算的指令集，HTML 中的这个示例也是如此。

关于抽象机器的维基百科文章：

抽象机，也称为抽象计算机，是用于定义计算模型的理论计算机。计算过程的抽象用于计算机科学和计算机工程学科，并且通常假定离散时间范式。

在计算理论中，抽象机器经常用于关于可计算性的思想实验或分析算法的复杂性（参见计算复杂性理论）。典型的抽象机由输入、输出和用于将前者转换为后者的一组允许操作的定义组成。最著名的例子是图灵机。

于 2020-06-01T00:12:46.907 回答