theory - Sub-Turing Complete Class of computational models

Question

Many programming languages and systems are Turing-complete; they can simulate any Turing machine, and therefore can simulate any finite state machine as well.

Consider the following informal model:
Language A defines a finite set of NAND gates, their connections to each other, and which gates receive input and which are outputted.

In this model, any finite state machine can be built. The NANDs can form latches, registers, busses and control structures, and in the end any finite state machine, including full computers and other systems.

The model, however, does not have the ability to simulate an infinite tape, only a tape of finite size. It cannot simulate any Turing machine because it may not have the memory to do so.

Are Language A and all other systems that can simulate any finite state machine considered Turing complete? Is there a separate class for them, or is there an opportunity to define such?

Answer 1

正如您已经意识到的那样，存在一个层次结构 - 可能具有无限多个级别 - 语言类，包括常规语言（由有限自动机识别）和可判定（由图灵机接受）。

所有真正的计算机 - 包括可用于构建它们的理论模型，例如涉及 NAND 门的模型 -都不是图灵等效的，因为它们理论上无法访问无限磁带。在实践中，物理现实中的时间、空间和物质不足以进行真正的图灵等效计算。所有物理计算都可以由有限自动机进行。在实践中，有一些常规语言过于复杂，无法通过构建真正的有限状态机或通用计算机来接受。

将语言建模为高于常规的类型是为了方便 - 它是一个谎言，就像将物质建模为连续的（例如，当计算惯性矩时）是一个谎言一样。物质实际上是由离散的分子组成的，而这些分子又由较小的离散粒子组成。