Consider the following imperative programming language. The programs operate on registers storing natural numbers, the input x-vector is stored in certain registers, and a number b, called the base, is fixed to max(x-vector,1) + 1 before the execution starts. The single primitive instruction X+ increases the number stored in the register X by 1 modulo b. There are two control structures: the loop while X {P} executing the program P repeatedly as long as the content of the register X is different from 0; the composition P; Q executing first the program P, then the program Q. This is the whole language. The language is natural, extremely simple, yet powerful. We will prove that it captures Linspace, i.e. the numerical relations decidable by such programs are exactly those decidable by Turing machines working in linear space. Variations of the language capturing other important deterministic complexity classes, like e.g. Logspace, P and PSPACE are possible (see Kristiansen and Voda [5]).
展开▼
