Variable Complexity of Simple Programs

• Autorzy: Holzer M. , Kutrib M.
• Języki publikacji: EN

Abstrakty

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.

Słowa kluczowe

EN

computability theory; programming approach to computability; LOOP-WHILE and GOTO-programs; register complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 511--528
• Opis fizyczny: bibliogr. 14 poz.

Twórcy

autor

Holzer M.

autor

Kutrib M.

• Institute of Informatics, University of Giessen, Arndstr. 2, D-35392 Giessen, Germany,

Bibliografia

• [1] W. Ackermann. Zum Hilbertschen Aufbau der reellen Zahlen. Mathematische Annalen, 99:118-133, 1928.
• [2] C. S. Calude. Theories of Computational Complexity. North-Holland, 1988.
• [3] A. Church. An unsolvable problemof elementary number theory. American Journal ofMathematics, 58:345-363, 1936.
• [4] E. Engler and P. Läuchli. Berechnungstheorie für Informatiker. Teubner, 1988.
• [5] A. Grzegorczyk. Some classes of recursive functions. Rozprawy Matematycne, 4:1-45, 1953.
• [6] O. H. Ibarra and N. Q. Trˆan. A note on simple programs with two variables. Theoretical Computer Science, 112:391-397, 1993.
• [7] A. J. Kfoury, R. N. Moll, and M. A. Arbib. A Programming Approach to Computability. Texts and Monographs in Computer Science. Springer, 1982.
• [8] S. C. Kleene. General recursive functions of natural numbers. Mathematische Annalen, 112:727-742, 1936.
• [9] A. R. Meyer and D. M. Ritchie. The complexity of loop programs. In Proceedings of the ACM National Meeting, pages 465-469. American Mathematical Society, 1967.
• [10] M. L. Minsky. Computation: Finite and Infinite Machines. Automatic Computation. Prentice-Hall, 1967.
• [11] E. L. Post. Finite combinatory processes-formulation 1. The Journal of Symbolic Logic, 1:103-105, 1936.
• [12] J. C. Shepherdson and H. E. Sturgis. Computability of recursive functions. Journal of the ACM, 10:217-255, 1963.
• [13] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230-265, 1936.
• [14] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. A correction. Proceedings of the London Mathematical Society, 43:544-546, 1937.