Bounded-storage machine

From Esolang
Jump to: navigation, search

A bounded-storage machine, abbreviated BSM, is in all respects similar to a Turing machine, save that there is an arbitrary bound on the size of its data storage unit (i.e. the length of its tape.)

This model comes up with respect to esoteric programming languages, for various reasons. Sometimes it is because an esolang has been defined by forming a description of how a specific implementation (interpreter or compiler) of it behaves, and the result is that the language is overspecified. Other times it is intentional, if for example a language is presented as the language of a virtual machine.

Computational class

It turns out that, while BSMs look an awful lot like Turing machines, they are not as computationally powerful. There are two general types of BSMs worth considering: those which define unbounded input facilities, and those which define bounded ones.

BSMs with unbounded input

A BSM with unbounded (for example, interactive, or batch processing of infinite batches) input can be shown to be in the same computational class as a finite-state automaton: the storage, being bounded, results in a finite number of total configurations of the system (the Cartesian product of the states that the storage can be in, and the states that the control mechanism can be in) but the input, being unbounded, allows switching between those configurations indefinitely.

BSMs with unbounded input include typical real computing devices and the assembly languages for them. Esoteric BSMs include Malbolge.

BSMs with bounded input

If a BSM only permits bounded input (for example, batch processing of finite batches - a Turing machine with a finite tape is in this category), then all input must exist in an initial configuration which is finite. It cannot, therefore, recognize certain regular expressions that a finite-state automaton can, such as ab*a (i.e. there would be an arbitrary limit to the number of b's that the BSM could recognize). Therefore, there are some FSAs which cannot be expressed as BSMs with bounded input.

In fact, any BSM with bounded input can be shown to be equivalent to a decision tree: enumerate all the possible initial configurations of the BSM, execute each one until it halts or goes into an infinite loop, and record the results in a table associated with that initial configuration. An infinite loop in a BSM can be detected by recording every total configuration it has experienced during a run; if an identical total configuration ever occurs, it has gone into an infinite loop.

BSMs with bounded input include Smallfuck and SMETANA.

A note on complexity

The above two sections speak only about computational equivalence - they do not mean to say that a BSM has the same complexity as a FSA or a DT. The BSM is typically much smaller, while the corresponding FSA or DT is typically much faster.

Relationship to linear bounded automata

Bounded-storage machines are at face value similar to linear bounded automata, but there is a vital difference which renders LBA more powerful. BSM have an arbitrary fixed tape size, not related to the input size; as a result, there is a strictly fixed number of reachable states, regardless of input, rendering them at best equivalent to finite-state automata. LBA, contrarily, have a fixed tape size based on some formula of the input size. Therefore, any problem for which the maximum necessary amount of tape is computable based on the length of the input is itself computable by an LBA, but not necessarily computable by a BSM.