Affiliations: Institut für Informatik, Technische
Universität München, Boltzmannstraße 3, D-85748 Garching bei
München, Germany. E-mail: [email protected] | Institut für Informatik, Universität
Gießen, Arndtstraße 2, D-35392 Gießen, Germany. E-mail:
[email protected]
Abstract: 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.
Keywords: Computability theory, Programming approach to computability, LOOP-,WHILE-, and GOTO-programs, Register Complexity
