是什么使图灵语言完整？

#1 楼

Turing tarpit是一种深奥的编程语言，它在使用尽可能少的元素的同时努力做到图灵完备。 Brainfuck可能是最著名的tarpit，但是有很多。


Iota和Jot是基于SK（I）组合器演算的函数语言，分别具有两个和三个符号。
OISC（一台指令集计算机）表示一种命令式计算，只需要一个指令即可包含一个或多个参数，通常是“如果小于或等于零，则减去并分支”，或者“如果借用，则反向减去并跳过”。 x86 MMU实现了前一条指令，因此是图灵完成的。

通常，要使命令式语言成为图灵完成的，它需要：


有条件重复或有条件跳转的一种形式（例如while，if + goto）
一种读写某种形式的存储方式（例如变量，磁带）的方法

要基于TC的基于演算的功能语言，它需要：


在参数上抽象函数的能力（例如，lambda抽象，引用）
将函数应用于参数的能力（例如减少量）

当然还有其他查看计算的方法，但是这些是Turing tarpit的常见模型。请注意，实际计算机不是通用的图灵机，因为它们没有无限的存储空间。严格来说，它们是“有界存储机器”。如果您要继续为它们增加内存，那么它们将逐渐接近图灵机的势力。但是，即使有界存储机器和有限状态机对于计算也是有用的。

严格来说，图灵完备性不需要I / O； TC仅断言某种语言可以计算所需的功能，而不能断言它可以向您显示结果。实际上，每种有用的语言都有一种与世界互动的方式。

#2 楼

从更实际的角度来看：如果您可以将图灵完备的语言中的所有程序翻译成您的语言，那么（据我所知），您的语言必须是图灵完备的。因此，如果要检查设计的语言是否为图灵完备的语言，则只需向BrainLanguage编译器编写Brainf ***，并证明/证明它可以编译所有合法的BF程序。

为了澄清，我的意思是，除了要为YourLanguage解释器之外，还要编写一个编译器（使用任何语言），该编译器可以将任何BF程序编译为YourLanguage（当然，保持相同的语义）。

#3 楼

仅当系统可以执行通用图灵机可以执行的任何操作时，才可以认为该系统是图灵完整的。由于据说通用图灵机可以在给定的时间内解决任何可计算的功能，因此图灵完整的系统也可以通过扩展来解决。

要检查图灵是否完整，请查看是否您可以在其中实现图灵机。换句话说，检查它是否可以模拟以下内容：读取和写入“变量”（或任意数据）的能力：几乎可以自我解释。

模拟移动读/写头的能力：仅能够检索和存储变量还不够。还必须能够模拟移动磁带磁头以引用其他变量的能力。这通常可以在编程语言中使用数组数据结构（或等效方法）进行模拟，或者在某些语言（例如机器代码）的情况下，可以通过使用“指针”（或等效方法）来引用其他变量。

模拟有限状态机的能力：尽管没有经常提及，但图灵机实际上是AI开发中经常使用的有限状态机的变体。艾伦·图灵（Alan Turing）表示，状态的目的是模拟一个人的“各种问题解决方式”。

“停止”状态：尽管经常提到一组规则必须能够重复以算作图灵完成，但这并不是一个很好的标准，因为对算法是状态的形式化定义必须始终最终得出结论。如果他们不能以某种方式得出结论，则说明它不是图灵完成的，或者所说的算法不是可计算的函数。图灵完整的系统在技术上由于它们的工作方式而无法得出结论（例如游戏机），因此可以通过某种方式“模拟”停止状态来解决此限制。不要与“停止问题”混淆，该函数的不确定性证明，如果给定输入将导致另一个系统无法得出结论，则不可能构建可以100％可靠性进行检测的系统。是图灵完整系统的真正最低要求。仅此而已。如果它不能以某种方式模拟其中的任何一种，则说明图灵不完整。其他人提出的方法只是最终目的，因为有几个图灵完整的系统没有这些功能。

请注意，没有已知的方法可以真正构建真正的图灵完整系统。这是因为没有一种真正的方法可以真实地模拟图灵机磁带在物理空间内的无限性。

#4 楼

如果您可以用它进行任何计算，则编程语言即将完成。不仅有一套功能使语言能够完整完成，所以回答说您需要循环或需要变量是错误的，因为有些语言既没有完成又没有完成。

Alan Turing制作了通用图腾机，并且如果您可以翻译设计为在通用机上工作的任何程序以使用您的语言运行，那么图灵也已经完成。这也可以间接起作用，因此，如果可以将用于翻译完整语言Y的所有程序都翻译为X，则可以说语言X正在完成，因为所有通用图灵机程序都可以翻译为Y程序。

复杂性，空间复杂性，易于输入/输出格式以及易于编写任何程序的方程式均未包括在内，因此，如果该计算不受功率损耗或地球被太阳吞没的影响，则该机器理论上可以进行所有计算。

通常为了证明图灵完整性，他们会为任何证明是图灵完整的语言提供翻译，但是要使其正常工作，您需要输入和输出方式，这对于语言图灵完整来说实际上并不需要两件事。您的程序可以在启动时更改其状态，并且可以在程序停止后检查内存。

要使语言成功，它不仅需要保持完整性，对于甚至巡视柏油场。如果没有,和.，我认为BrainFuck不会流行。

#5 楼

您无法确定它会无限循环还是停止。

-----------------

解释：给定一些输入，它是在任何情况下（使用另一台Turing机器）都无法判断事物是否将无限循环或最终将停止，除非运行它（如果它确实停止了，它会给出答案，但如果它循环了，则不会给出答案！）。 br />
这意味着您必须能够以某种方式存储可能无限量的数据-无论卷度如何，都必须有与无限磁带等效的数据！ （否则，只有有限数量的状态，然后您可以检查您以前是否经历过该状态并最终停止）。通常，图灵机可以通过某些可控制的方式来增大或缩小其状态的大小。

由于图灵的原始通用图灵机存在无法解决的暂停问题，因此您自己的图灵完整机也必须具有无法解决的暂停问题。

Turing完整系统可以模拟任何其他Turing完整系统，因此，如果您可以为系统中某个知名的Turing完整系统构建仿真器，则证明您的系统也是Turing完整的。 />
例如，假设您要证明蛇和梯子是图灵完整的，给定的板具有无限重复的网格图案（顶部和左侧具有不同的版本）。知道2计数器Minsky机器是图灵完备的（具有2个无限制计数器和1个有限数量的状态），您可以构造一个等效板，其中网格上X和Y位置是2个计数器的当前值并且当前路径是当前状态。砰!您刚刚证明了蛇和梯子已经完成了图灵。

#6 楼

一个必要条件是在迭代之前未确定具有最大迭代次数的循环，或者在未事先确定最大递归深度的情况下进行递归。例如，对于... in ...循环，当您在许多较新的语言中找到它们时，不足以使该语言完成学习（但它们将具有其他手段）。请注意，这并不意味着有限的迭代次数或有限的递归深度，而是必须提前计算最大迭代次数和递归深度。

例如，没有这些功能，就无法用一种语言来计算Ackermann函数。另一方面，不需要这些功能就可以编写许多高度复杂且非常有用的软件。

另一方面，通过预先计算每个迭代计数和每个递归深度，不仅可以确定程序是否停止，而且可以停止。

#7 楼

我知道这不是形式上正确的答案，但是一旦您从“ Turing-complete”中剔除了“ minimal”并把“ practical”放回了它所属的位置，您将看到最重要的功能，它们将编程语言与标记语言是


变量
条件变量（如果/则...）





匿名和命名函数

要测试这些断言，首先要使用一种标记语言，例如HTML。我们可以发明一种仅包含变量或仅具有条件的HTML +（MS使用条件注释来做到这一点），或某种循环构造（在没有条件的情况下最终可能会像<repeat n='4'>...</repeat>一样）。进行上述任何一项操作都将使HTML +比纯HTML更加强大（？），但与编程语言相比，它更像是一种标记；有了每个新功能，您将使它不再是声明式语言，而更多是命令式语言。

追求逻辑和编程上的最低限度的追求固然重要且有趣，但是如果我要教n00bie男女老少“编程是什么”和“如何学习编程”，我几乎不会从图灵完整性理论基础的广度和宽度入手。烹饪和编程的全部精髓是按照正确的顺序进行操作，直到妈妈准备好为止，重复进行直到准备就绪。

然后，我再也没完成我的CS。