HTML图灵是否完整？
Luk*_*uke 16 html html5 turing-complete
看完这个问题后,CSS图灵完成了吗？- 它收到了一些深思熟虑的简洁答案 - 它让我想知道:HTML图灵是否完整？
虽然简短的答案是肯定的肯定或否定,但也请提供一个简短的描述或反例来证明HTML是否是图灵完全(显然不能同时).关于其他版本的HTML的信息可能很有趣,但正确的答案应该回答HTML5.
小智 14
单独(没有CSS或JS),HTML(5或其他)不可能是Turing-complete,因为它不是一台机器.询问它是否是基本等同于询问苹果或橙子是图灵完整,还是采取更相关的例子,一本书.
HTML不是"运行"的东西.这是一种表现形式.这是一种格式.这是一种信息编码.它不是一台机器,它无法在图灵完整性或任何其他级别上自行计算任何东西.
- @TravisJ当然,我可以用IFRAME或许多其他方式代表各州.但要成为一台机器,我们必须能够在各州之间转换.怎么会发生这种情况？ (7认同)
- 虽然我希望"不"是正确的,你会详细说明为什么HTML不是正式的"机器",为什么这是图灵完整性的要求？当浏览器解析HTML时,HTML不能被视为"运行",就像JavaScript文件一样吗？ (5认同)
- 对于初学者来说,HTML没有任何做出"决定"的方法,比如`if ... then ... else`.它也没有循环,没有变量等.它本身不是编程语言,它只是声明性的. (5认同)
- 这是不准确的。您可以将 html 变成一个状态机，其中每个状态都由一个 iframe 表示。 (3认同)
- HTML5和CSS3即将完成，因为其中写入了Rule 110实施 (3认同)
- @AnthonyYershov WWW 由 HTML、CSS 和 JS（以及其他一些）组成。三个独立的规格可以协同工作。JS 和 CSS 都不直接包含在 HTML 规范中，也不是 HTML 工作所必需的。脚本标签本身仅定义加载行为/属性，实际实现在其他地方。仅支持 HTML 但不支持 CSS 或 JS 的浏览器仍然符合 HTML 规范（请参阅 Lynx 文本浏览器）。因此，这个答案是正确的。 (2认同)
bwd*_*wdm 12
我似乎很清楚，状态和转换可以分别用页面和超链接在 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
- 称为字母表的有限输入符号集 ?
- 过渡函数 ? ：问×？? 问
- 初始或起始状态 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的状态图：
状态 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 中的这个示例也是如此。
维基百科关于抽象机器的文章：
抽象机器，也称为抽象计算机，是一种用于定义计算模型的理论计算机。计算过程的抽象用于计算机科学和计算机工程学科，并且通常假设离散时间范式。
在计算理论中，抽象机器经常用于有关可计算性的思想实验或分析算法的复杂性（参见计算复杂性理论）。典型的抽象机器由输入、输出和用于将前者转变为后者的一组允许操作的定义组成。最著名的例子是图灵机。
- @Anthony Yershov 可计算性理论比这更抽象。您不需要解释器，甚至不需要 CPU 来确定此类规则（例如形式语法）的计算能力。这种分析都是关于语法的，而不是状态之间转换机制的实现。所以我想说它是纯 HTML，就像任何正式语法都是“纯”的一样。 (3认同)
- 超链接不仅代表状态转换，而且还“有效”。您可以自己[测试](https://brunodantas.github.io/html-fda)。 (3认同)
- @AnthonyYershov 在你的引言中“*数据操纵规则系统*”与你试图争论的内容相悖。规则本身并不是自动实现的，它们只是实现时应该遵循的规则。这样考虑：图灵机不是实际的机器，图灵没有建造机器。它们是纯粹的数学对象，它们是集合（状态、符号）的元组和状态之间的转换函数。图灵机是纯粹的数学对象，它们是如何实现计算的指令集，这个 HTML 示例也是如此。 (3认同)
- “在可计算性理论中，如果数据操作规则系统可以用来模拟任何图灵机，则该系统被认为是图灵完备的或计算通用的。这意味着该系统能够识别或决定其他数据操作规则集”。- 维基定义。您的系统还包括负责点击的人员，因此它不是纯 HTML。我很确定当人们说 javascript 是图灵完备时，他们指的是引擎而不是语法。 (2认同)