一种语言可以在不支持数组的情况下实现图灵完备吗？
如果一种语言有控制结构和变量，但不支持数组、列表、内存访问和分配等，它能是图灵完备的吗？
也许如果您可以创建的变量数量没有限制，您可以通过创建诸如 array_1、array_2、... array_6000 之类的变量来模拟数组code> 并手动循环它们，并以某种方式创建复杂的数据结构和递归？
编辑：即使您无法通过名称操作访问变量（不允许array_10+i）？
If a language has control structures and variables, but no support for arrays, lists, memory access and allocation, etc, can it be Turing-complete?
Maybe if there was no limit to the amount of variables you can create, you can simulate arrays by creating variables like array_1, array_2, ... array_6000 and manually loop through them, and somehow create complex data structures and recursion?
Edit: Even if you cannot access variables by name manipulation (array_10+i is not allowed)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
当然。看看 Lambda Calculus，这是我用过的最简单的图灵完备语言之一曾经见过。基本上，您拥有的只是 lambda（函数文字）；没有赋值，没有声明，没有数据结构。这一切都非常非常瘦身。
但是，您可以通过将函数链接在一起来模拟线性数据结构，例如列表。它变得相当冗长，但它肯定是可能的，并且比拥有大量顺序命名的变量要好得多。
一般来说，一种语言是否图灵完备与它是否有数组无关。像 SML 和 Haskell 这样的函数式语言缺乏数组，就像 Lambda Calculus 一样，而这些实际上是有用的语言！说一种语言是“图灵完备”只是另一种说法，即不存在不能用该语言表达的图灵可计算函数。这是一个令人惊讶的宽松限制，允许许多完全不切实际的语言（例如 Lambda 演算）。
Certainly. Have a look at Lambda Calculus, which is one of the most minimal Turing Complete languages I've ever seen. Basically, all you have are lambdas (function literals); no assignment, no declaration, no data structures. It's all very very slimmed-down.
You can, however, simulate a linear data structure like a List by chaining functions together. It gets pretty verbose, but it's certainly possible and it's much nicer than having a large series of sequentially named variables.
Generally speaking, whether or not a language is Turing Complete has nothing to do with whether it has Arrays. Functional languages like SML and Haskell lack arrays, just like Lambda Calculus, and these are actually useful languages! Saying a language is "Turing Complete" is merely another way of saying that there is no Turing Computable function which cannot be expressed in said language. This is a surprisingly loose qualification, allowing many languages which would be completely impractical (like Lambda Calculus).
有很多图灵完备的语言甚至没有“变量”的概念！内存访问和分配是实现细节，因此它们完全无关。你必须意识到图灵机和图灵完备性是非常理论化的概念，对于证明事物很有用，但完全脱离了实际硬件的现实。
Paul Graham 写了一篇很长但非常非常有趣的关于计算机语言历史的文章，他在其中描述了计算机语言的两种截然不同的主要传统：
听起来你只知道第二个传统，但图灵完备性是一个源自与第一个传统相同原理的概念，如果你不知道这些原理就没有什么意义。
There's plenty of Turing-complete languages that don't even have the notion of a "variable"! Memory access and allocations are implementation details, so they're completely irrelevant. You have to realize that Turing machines and Turing completeness are very theoretical concepts, useful for proving things, but completely divorced from the reality of actual hardware.
Paul Graham has written a long, but very, very interesting essay on the history of computer languages where he describes the two very different main traditions of computer languages:
It sounds like you know only the second tradition, but Turing completeness is a concept that originates from the same principles as the first tradition and makes little sense if you don't know those principles.