terminology - “完整”编程语言的术语？

Question

“图灵完备性”的完整定义需要无限的记忆。

除了受限于有限的（比如 100 字或 16 位或 32 位等）地址空间之外，还有比图灵完备更好的术语吗？

Answer 1

我想，您可以将有限的内存带入定义中。就像是

给定架构（！）的编程语言是有限图灵完备的，如果对于每个图灵机都存在一个程序，要么

a) 模拟图灵机并返回相同的结果（如果图灵机返回）或

b) 在某些时候完全使用至少一种可用的有限资源（例如内存）并返回任意结果。

问题是，这个直观的定义是否真的有帮助，或者假设您的架构具有无限的内存（即使它实际上是有限的）是否更好。请注意，您甚至不必努力满足有限的图灵完整性（如上定义），如果您只是进入一个每次 malloc 一个字节的无限循环，您就可以找到适用于所有图灵机的程序。

问题似乎是您无法固定实现特定的属性。例如，如果你有 500K 内存，你可能能够表达一个计算的程序，1+1但也许你不能，谁知道呢。

我认为像 Haskell 和 Brainfuck 这样的语言（是的，我是认真的）实际上是图灵完备的，因为它们抽象了资源。虽然像 C++ 这样的语言只是有限的图灵完备，因为在某些时候指针的地址空间已经耗尽并且不可能再处理任何数据（例如对 2^2^2^2^100 项的列表进行排序）。

Answer 2

您可以说实现需要无限内存才能真正完成图灵完备，但语言本身没有内存限制的概念。您可以为百万位机器或 4 位机器制作编译器，而无需更改语言。