turing-complete - 一种语言可以在不支持数组的情况下实现图灵完备吗？

Question

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

也许如果你可以创建的变量数量没有限制，你可以通过创建像 array_1 这样的变量来模拟数组。 , array_2 , ... array_6000并手动遍历它们，并以某种方式创建复杂的数据结构和递归？

编辑:即使您无法通过名称操作访问变量(不允许 array_10+i)？

Answer 1

当然。看看Lambda Calculus ，这是我见过的最少的图灵完备语言之一。基本上，您所拥有的只是 lambdas(函数文字)；没有赋值，没有声明，没有数据结构。这一切都非常非常瘦身。

但是，您可以通过将函数链接在一起来模拟类似于 List 的线性数据结构。它变得非常冗长，但它肯定是可能的，而且比拥有大量按顺序命名的变量要好得多。

一般来说，一门语言是否图灵完备与它是否有数组无关。像 SML 和 Haskell 这样的函数式语言，就像 Lambda 微积分一样，缺少数组，而这些实际上是有用的语言!说一种语言是“图灵完备”只是另一种说法，即没有不能用该语言表达的图灵可计算函数。这是一个令人惊讶的松散限定，允许许多完全不切实际的语言(如 Lambda 微积分)。