A string rewriting system that uses grammar-like rules
to operate on strings of symbols.
Register Machine
is a theoretically interesting idealization of a computer.
There are more variants. In most of them, each register
can hold a natural number (of unlimited size), and the
instructions are simple (and few in number), e.g. only
decrementation (combined with conditional jump) and
inrementation exist (and halting). The lack of the infinite
(or dynamically growing) external store (seen at Turing
machines) can be understood by replacing its role with
Gödel numbering techniques: the fact that each
register hold a natural number allows the possibility
of representing a complicated thing (e.g. a sequence,
or a matrix etc.) by an appropriate huge natural number
— unambiguity of both representation and interpretation
can be established by number theoretical foundations
of these techniques.
P''
Like Turing machines, P'' uses an infinite tape of symbols
(without random access), and a rather minimalistic set
of instructions. But these instructions are very different,
thus, unlike Turing machines, P'' does not need to maintain
a distinct state, because all “memory-like”
functionality can be provided only by the tape. Instead
of rewriting the current symbol, it can perform a modular
arithmetic incrementation on it. P'' has also a pair
of instructions for a cycle, inspecting the blank symbol.
Despite of its minimalistic nature, it has become the
parental formal language of an implemented and (for
entertainment) used programming language called Brainfuck.
In addition to the general computational
models, some simpler computational models are useful
for special, restricted applications. Regular expressions,
for example, are used to specify string patterns in
many contexts, from office productivity software to
programming languages. Another formalism mathematically
equivalent to regular expressions, Finite automata are
used in circuit design and in some kinds of problem-solving.
Context-free grammars are used to specify programming
language syntax. Non-deterministic pushdown automata
are another formalism equivalent to context-free grammars.
Primitive recursive functions are a defined subclass
of the recursive functions.
Different models of computation have
the ability to do different tasks. One way to measure
the power of a computational model is to study the class
of formal languages that the model can generate; this
leads to the Chomsky hierarchy of languages. |
