Ograniczanie wyników
Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 1

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  LOOP-WHILE and GOTO-programs
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Variable Complexity of Simple Programs
EN
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:\mathbbNŽ \mathbbN (partial functions f:\mathbbN\hookrightarrow \mathbbN, 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 incomparable (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.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.