问题标签 [turing-complete]

我的理解是，这意味着人们可能会编写一个程序来正式证明用静态类型语言编写的程序将没有某个（小）缺陷子集。

我的问题如下：

假设我们有两种图灵完备的语言，A 和 B。假定 A 是“类型安全的”，而假定“B”不是。假设我有一个程序 L 来检查任何用 A 编写的程序的正确性。是什么阻止我将任何用 B 编写的程序翻译成 A，应用 L。如果 P 从 A 翻译到 B，那么为什么 PL 不是用 B 编写的任何程序的有效类型检查器？

我接受过代数培训，并且才刚刚开始学习 CS，因此可能有一些明显的原因表明这不起作用，但我非常想知道。这整个“类型安全”的事情对我来说已经有一段时间了。

因此，如果一种语言满足某些标准，就可以说它是图灵完备的，并且它可以做另一种图灵完备语言可以做的任何事情。

这是否意味着我理论上可以使用 JavaScript 或Brainf_ck实现 Google ？

众所周知，UML 没有图灵完备（与通常的编程语言相比）。但在我看来，UML 比传统语言更灵活。我无法想象一个问题可以用 C++ (fe) 之类的语言来描述，但同时又不能用 UML 来描述。恰恰相反，我更容易想象存在于 UML 中但在 C++ 中不可靠的构造（Java、Delphi、VB 等......）你能帮我理解这一刻吗？我真的抓不住。

我一直在网上搜索，我发现有些矛盾的答案。一些消息来源断言，当且仅当它同时具有条件分支和无条件分支（我猜这有点多余）时，语言/机器/你有什么是图灵完备的，有人说只需要无条件，其他人只需要条件是必须的。

阅读有关德国Z3和ENIAC的信息，维基百科说：

德国 Z3（显示于 1941 年 5 月工作）由 Konrad Zuse 设计。它是第一台通用数字计算机，但它是机电的，而不是电子的，因为它使用继电器来完成所有功能。它使用二进制数学进行逻辑计算。它可以通过穿孔带进行编程，但缺少条件分支。虽然不是为图灵完备性而设计的，但它意外地是，正如在 1998 年发现的那样（但为了利用这种图灵完备性，需要复杂、聪明的 hack）。

究竟是什么复杂、巧妙的技巧？

R. Rojas 的 1998 年论文摘要也指出（请注意，我没有读过这篇论文，它只是来自 IEEE 的一个片段。）：

计算机 Z3 由 Konrad Zuse 在 1938 年至 1941 年间制造，只能执行在穿孔磁带中编码的固定浮点算术运算序列（加法、减法、乘法、除法和平方根）。从计算历史的角度来看，一个有趣的问题是这些操作是否足以进行通用计算。该论文表明，事实上，包含这些算术指令的单个程序循环可以模拟任何图灵机，其磁带具有给定的有限大小。这是通过纯算术方法模拟条件分支和间接寻址来完成的。因此，至少在原则上，Zuse 的 Z3 与当今具有有限寻址空间的计算机一样通用。

简而言之，SOers，图灵完备性究竟需要哪种类型的分支？假设内存无限，只有一个goto或jmp分支结构（没有if或jnz结构）的语言可以被认为是图灵完备的吗？

有人声称 Scala 的类型系统是图灵完备的。我的问题是：

1. 有正式的证明吗？

2. Scala 类型系统中的简单计算会是什么样子？

3. 这对 Scala 有什么好处吗？与没有图灵完整类型系统的语言相比，这是否使 Scala 在某种程度上更“强大”？

我想这通常适用于语言和类型系统。

我最近一直在用 Stata 做一些统计工作，但不太喜欢它。

我不觉得它是一种“正确的”编程语言：特别是我认为在满足条件之前没有办法循环。

我的感觉是对的，还是 Stata 真的是图灵完备的？

就图灵完备性而言，简单循环与嵌套循环一样强大吗？

正则表达式通常被认为是不完善的语言的经典示例。例如，“正则表达式”作为这个 SO 问题的答案给出，寻找不是图灵完备的语言。

在我对转动完整性概念的理解中，这可能有点基本，这意味着不能使用正则表达式来检查“平衡”的模式。平衡的含义具有与结束字符相同数量的开始字符。这是因为这样做需要你有某种状态，以允许你匹配开始和结束字符。

然而，正则表达式的 .NET 实现引入了平衡组的概念。此构造旨在让您回溯并查看之前的组是否匹配。这意味着 .NET 正则表达式：

可以匹配以下模式：

这是否意味着.NET 的正则表达式是图灵完备的？或者是否还有其他缺少的东西需要语言是图灵完备的？

判断X或Y 是（或不是）编程语言所需的标准或基本特征是什么？

我做了一些阅读（HTML被认为是一种编程语言吗？、图灵完备等），并得出结论，一种语言或语法必须是图灵完备的才能被视为一种编程语言。这个对吗？够了吗？

以及如何确定某些东西是否是图灵完备的？有什么具体的标准吗？

控制流结构（条件语句和循环）是否足以被视为图灵完备？

我儿子最近一直在玩Little Big Planet 2，我注意到游戏编辑器允许AND门，OR门和NO门......图灵完备吗？如果是这样，任何人都可以推荐一个资源来学习将这些原语变成更高级别的条件 if 吗？