5

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

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

编辑：即使您不能通过名称操作访问变量（array_10+i不允许）？

4

2 回答 2

17

当然。看看Lambda Calculus，它是我见过的最小的图灵完备语言之一。基本上，你所拥有的只是 lambdas（函数字面量）；没有赋值，没有声明，没有数据结构。这一切都非常非常精简。

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

一般来说，一种语言是否图灵完备与它是否有数组无关。SML 和 Haskell 等函数式语言缺少数组，就像 Lambda 演算一样，这些实际上是有用的语言！说一种语言是“图灵完备的”只是另一种说法，即没有不能用该语言表达的图灵可计算函数。这是一个非常宽松的限定条件，允许许多完全不切实际的语言（如 Lambda 演算）。

于 2009-09-07T16:00:21.483 回答
5

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

Paul Graham 写了一篇很长但非常非常有趣的关于计算机语言历史的文章，他描述了计算机语言的两种截然不同的主要传统：

  • Lisp、Scheme 等 - 源自理论考虑，非常简单，但概念上强大的语言，但在很长一段时间内是不切实际的，因为它们完全无视什么是容易和有效的实现
  • 汇编程序、FORTRAN、C 和几乎所有“主流”语言 - 或多或少直接源自硬件可以做的事情，易于实现，高效，但在表达能力方面最长的时间不如（旧！）Lisp 系列.

听起来你只知道第二个传统，但图灵完备性是一个源自与第一个传统相同的原理的概念，如果你不了解这些原理，那将毫无意义。

于 2009-09-07T16:25:59.577 回答