语言是否可以完全没有阵列支持？

Question

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

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

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

Answer 1

当然.看看Lambda Calculus,这是我见过的最小的图灵完整语言之一.基本上,你所拥有的只是lambdas(函数文字); 没有任务,没有声明,没有数据结构.这一切都非常精简.

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

一般来说,语言是否为图灵完全与它是否具有数组无关.像SML和Haskell这样的函数语言缺少数组,就像Lambda Calculus一样,这些语言实际上是有用的语言!说一种语言是"图灵完成"仅仅是说没有图灵可计算函数的另一种方式,它不能用所述语言表达.这是一个令人惊讶的宽松资格,允许许多语言完全不切实际(如Lambda Calculus).

Answer 2

有很多图灵完整的语言,甚至没有"变量"的概念!内存访问和分配是实现细节,因此它们完全不相关.你必须意识到图灵机和图灵完整性是非常理论的概念,对于证明事物很有用,但完全脱离了实际硬件的现实.

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

• Lisp,Scheme等 - 源于理论上的考虑,非常简单但概念上强大的语言,但由于完全无视实现简单有效的语言,因此最长时间不切实际
• 汇编程序,FORTRAN,C和几乎所有"主流"语言 - 或多或少地直接来自硬件可以做什么,易于实现,高效,但是在表达性方面最长时间不如(较老的!)Lisp家族.

听起来你只知道第二种传统,但图灵的完整性是一个源于与第一传统相同的原则的概念,如果你不了解这些原则就没什么意义.