Variable Complexity of Simple Programs.

The number of registers or variables of a LOOP-, WHILE-, or GOTO-program, needed to compute a certain (partial) function from non-negative integers into non-negative integers, is a natural measure of complexity. We show that the hierarchy of LOOP-computable (WHILE-, and GOTO-computable, respectively) functions f: N→N (partial functions f: N↪N, respectively) which is induced by the number of registers collapses to level four (three, respectively). So, there exist universal WHILE- and GOTO-programs with a constant number of registers. In all three cases we give a characterization of the functions that can be computed by one register only. These characterizations are used to show that the first levels of the register hierarchies are strict, and to compare these levels. Surprisingly, for total functions it turns out that the bottom level of the LOOP-hierarchy is incompa-rable (with respect to set inclusion) to the bottom levels of the WHILE- and GOTO-hierarchies. Finally we briefly discuss the impact of the register operations on the presented results. [ABSTRACT FROM AUTHOR]