语言可以在不支持阵列的情况下完成图灵完整吗？

Question

如果一种语言具有控制结构和变量，但对数组，列表，内存访问和分配等不支持，它可以完成吗？

也许如果您可以创建的变量数量没有限制，则可以通过创建变量（例如）模拟数组 array_1, array_2, ... array_6000 并手动循环通过它们，并以某种方式创建复杂的数据结构和递归？

编辑: ：即使您无法通过名称操纵访问变量（array_10+i 不被允许）？

Answer 1

当然。看一下 lambda演算, ，这是我见过的最小的图灵完整语言之一。基本上，您拥有的只是lambdas（函数文字）；没有作业，没有声明，没有数据结构。一切都非常苗条。

但是，您可以通过将功能链接在一起来模拟线性数据结构，例如列表。它变得非常详细，但这肯定是可能的，而且比拥有一系列依次命名的变量要好得多。

一般来说，图灵完成是否与有数组无关。像Lambda演算一样，SML和Haskell等功能性语言缺乏数组，这些语言实际上是有用的语言！说一种语言是“图灵完整”只是另一种说法，说没有图灵的可计算函数无法用所述语言表达。这是一个令人惊讶的松散资格，允许许多语言完全不切实际（例如Lambda微积分）。

Answer 2

有很多图灵完整的语言甚至没有“变量”的概念！内存访问和分配是实现细节，因此它们完全无关。您必须意识到，图灵机和图灵完整性是非常理论上的概念，可用于证明事物，但与实际硬件的现实完全不同。

保罗·格雷厄姆（Paul Graham）写了很长但非常非常有趣的 散文 关于计算机语言的历史，他描述了两种截然不同的计算机语言主要传统：

• LISP，方案等 - 源自理论考虑，非常简单但在概念上有力的语言，但最长的时间是不切实际的，因为它们完全无视容易实施的东西
• 汇编器，Fortran，C和几乎所有“主流”语言或多或少地源自硬件可以做的事情，易于实现，高效，但最长的时间不如（较旧的！）Lisp家族，就表现力而言。

听起来您只知道第二个传统，但是Turing完整性是一个概念，它源自与第一个传统相同的原理，如果您不知道这些原则，则毫无意义。