问题标签 [turing-complete]

Scala 使用基于 System F ω 的类型系统，通常被认为是强规范化的。强归一化意味着非图灵完备性。

尽管如此，Scala 的类型系统是图灵完备的。

与正式的算法和系统相比，哪些更改/添加/修改使 Scala 的类型系统图灵完备？

你如何论证 lambda 演算是图灵完备的（以最简单的方式）？

我希望创建一个最小的、计算通用的字母数字 x86 操作码子集。最终，我希望子集包含尽可能少的指令，如果有多个最小子集，我也想知道这一点。该子集应该能够模拟可以使用整套字母数字指令编写的任何程序。说明应仅涵盖与字符“AZ”、“az”和“0-9”相对应的说明。

到目前为止，我认为 a push, pop, inc, dec, cmp, andje就足够了，但我确信还有一个较小的集合。我如何证明我生成的集合能够使用所有字母数字指令模拟任何程序？我怎么能证明这样的集合是最小的？有谁知道这样的指令子集是否存在？

我花了一两个星期编写一个简单的逻辑求解器。构建它之后，我发现自己想知道它所解决的语言是否是图灵完备的。所以我编写了一小组方程，它们接受 SKI 组合子演算中的任何有效表达式，并生成一个包含该表达式的正常形式的结果集。由于 SKI是图灵完备的，证明我的语言可以执行 SKI 将证明其图灵完备。

但是，有一个小故障。求解器不会按正常顺序减少表达式。实际上它所做的是尝试所有可能的减少顺序。这意味着解决方案集通常是巨大的。如果一个范式存在，它会在某个地方，但很难说在哪里。

这给我带来了两个问题：

• 我的语言图灵完备吗？还是我需要找到更好的证据？

• 解决方案的数量是输入的可计算函数吗？

（起初我假设解决方案集的大小是输入大小的指数或阶乘。但仔细观察，这是不正确的。你可以编写已经是正常形式的巨大表达式，以及不会终止的微小表达式.我有一种感觉，确定解决方案集的大小可能等同于解决停止问题，但我不完全确定......）

众所周知，C++ 模板是图灵完备的，CSS 是图灵完备的（！），并且C# 重载解决方案是 NP-hard（即使没有泛型）。

但是 C# 4.0（具有协/逆变、泛型等）编译时图灵是否完整？

我无法理解维基百科文章或这里的答案所说的内容。有人可以简单地解释第 110 条规则吗？它如何保证图灵完备？

一些编程问题不需要图灵机的全部能力来解决。他们可以用更少的力量来解决。我正在寻找一种功能较弱的编程语言。

是否存在仅限于支持这些功能的高级编程语言：

1. 具有将值压入堆栈和将值从堆栈中弹出的操作的堆栈。

2. 一个有限状态机 (FSM) 用于输入值、从一个状态移动到另一个状态、与堆栈交互并输出结果。

我意识到我可以使用 Java 或 C 或 Python（等）并通过编写仅使用堆栈和 FSM 的程序来限制语言。但是，我正在寻找一种仅具有这些功能的编程语言，仅此而已。

换句话说，我不想使用图灵完备的编程语言来解决只需要确定性下推自动机功能的问题。我想使用一种仅具有确定性下推自动机功能的编程语言。

也就是说，图灵机能否将形式系统 S 作为其输入并确定 S 是否是图灵完备的？

我认为这是一个无法确定的问题，对吗？

如果它是不可判定的，为什么我们（作为人类）可以决定图灵完备性？

是否可以用 HTML+CSS 编写编译器？我知道他们（一起）应该是图灵完备的，至少是 HTML5/CSS3 组合。所以应该可以为Java编写一个编译器，对吧？还是我对图灵完备性的含义有某种基本的误解？由于 HTML+CSS 本身不是编译语言，这是否意味着不可能用它们编写编译器？（你也可以为 HTML/CSS 编写一个编译器吗？）

Wolfram 即将发布其“基于知识的编程语言”，但它真的像 C#、Java 等一样是一种真正的编程语言吗？

为了避免这过于主观，我将澄清“真正的编程语言”是指：图灵完备吗？