问题标签 [turing-complete]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
html - HTML 图灵完备吗？
看完这个问题CSS Turing 是否完整？——收到了一些深思熟虑、简洁的答案——这让我想知道：HTML 图灵完备吗？
尽管简短的回答是肯定的是或否，但也请提供简短的描述或反例来证明 HTML 是否是图灵完备的（显然不能两者兼而有之）。其他版本的 HTML 的信息可能很有趣，但正确的答案应该是HTML5的答案。
cpu - 可以从 ROM 执行代码的最简单的图灵完备 CPU 指令集是什么？
我相信下面的所有 OISC 都要求程序从 RAM 中执行，才能实现图灵完备。
https://en.wikipedia.org/wiki/One_instruction_set_computer
是这样吗？
可以从 ROM 执行代码的最简单的图灵完备 CPU 指令集是什么？即不需要修改未来的指令来进行条件跳转等。
algorithm - 每个算法的最佳时间复杂度要求？
算法的时间复杂度可能因编程语言而异，因为某些事情不可能用一种语言而不是另一种语言来完成。图灵完备性也没有说明所述语言的时间复杂度可能性。
我的问题是，对于一种编程语言，能够以任何语言可能的最佳时间复杂度解决每个算法的要求是什么？图灵完备并增加了在恒定时间内检查/编辑数据结构的可能性就足够了吗？
turing-machines - 现实世界中的图灵完备性
真正的程序可以在有足够的时间和空间的情况下解决问题。对于每个已知大小的问题实例，所消耗的空间量都有固定的上限。
给定“仅”足够大的内存，是否存在无法解决的问题（即无法计算的函数）？
更具体地说，是否存在只能由图灵机（具有无限磁带）计算而不能由传统程序计算的函数？
scala - 图灵完备类型系统的原因是什么
Scala 和 Haskell 有“图灵完备的类型系统”。通常，图灵完备性是指计算和语言。在类型的上下文中它的真正含义是什么？
有人可以举一个程序员如何从中受益的例子吗？
PS 我不想比较 Haskell 和 Scala 的类型系统。它更多地是关于一般的术语。
PSS 如果可能有更多 Scala 示例。
gremlin - 图灵完备的图查询语言
可以准确地说，在现有的图形查询语言（Cypher、Datalog、Sparql 等）中，Gremlin 是唯一一个图灵完备的语言吗？
万一这很重要，我不是在寻找像 Magic: the Gathering 的图灵完整性证明这样的边缘案例；我的问题的目的是 Gremlin 是否是唯一适合在实践中对图执行任意计算的图查询语言。
bpmn - BPMN 2.0 图灵完备吗？
我正在使用 BPMN 2.0 开始一个新项目。图灵语言是完整的吗？乍一看，我想说的是，但我发现了一些讨论（例如，https ://groups.google.com/forum/#!topic/vertx/Q1fql6BxYpg ），其中提到它不是。但是，我不确定这些说法有多正确。
我提出这个问题的主要动机之一是支持 BPMN 2.0 的工作流引擎允许包含脚本活动（例如，使用像 Groovy 这样的图灵完备语言）。我想知道这样做的唯一目标是允许流程工程师实现业务流程的简单定制，还是脚本语言也应该涵盖 BPMN 2.0 的表达性问题？
grammar - 不受限制的语法：{ sss | s 存在于 {a,b}* }
什么是为 sss 构建不受限制的语法的方法？我知道为了构造 ss，你需要构造 ss^r 然后重新反转第二个字符串，但是对于 sss 该怎么做呢？
mysql - 选择没有行和没有列？
是否可以编写一个 SELECT 语句，它返回零行和零列的数据集？
nlp - 自然语言图灵完备吗？
我很确定人类语言（例如英语）足以模拟图灵机，这将使图灵机完整。然而，这意味着自然语言的表达能力并不比编程语言多或少，这似乎是有问题的。
自然语言图灵完备吗？