theoryturing-complete

Sub-Turing Complete Class of computational models


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?


Solution

  • As you have realized, there is a hierarchy - with potentially infinitely many levels - of classes of languages, including regular languages (recognizable by finite automata) and decidable (accepted by a Turing machine).

    All real computers - including theoretical models which can be used to construct them, like yours involving NAND gates - are not Turing equivalent because they cannot in theory access an infinite tape. In practice, time, space and matter are insufficient in physical reality to allow for real Turing-equivalent computation. All physical computation can be carried out by a finite automata. There are regular languages, in practice, too complex to ever accept by constructing a real finite state machine or general-purpose computer.

    Modeling languages as being of a type higher than regular is for convenience - it is a lie in the same way that modeling matter as continuous (e.g., when computing moment of inertia) is a lie. Matter is really made of discrete molecules, which in turn are comprised of smaller discrete particles.