The complexity of loop programs

ABSTRACT

Anyone familiar with the theory of computability will be aware that practical conclusions from the theory must be drawn with caution. If a problem can theoretically be solved by computation, this does not mean that it is practical to do so. Conversely, if a problem is formally undecidable, this does not mean that the subcases of primary interest are impervious to solution by algorithmic methods. In the next section we describe such a class of programs, called “Loop programs.” Each Loop program consists only of assignment statements and iteration (loop) statements, the latter resembling the DO statement of FORTRAN, and special cases of the FOR and THROUGH statements of ALGOL and MAD. The bound on the running time of a Loop program is determined essentially by the length of the program and the depth of nesting of its loops.

REFERENCES

• 1: M DAVIS Computability and unsolvability McGraw-Hill Book Company Inc New York 1958
• 2: S C KLEENE Introduction to metamathematics Van Nostrand New York 1952
• 3: P AXT Iteration of primitive recursion Abstract 597-182 Notices Amer Math Soc Jan. 1963
• 4: A GRZEGORCZYK Some classes of recursive functions Rozprawy Matematyczne, Warsaw, 1953
• 5: A R MEYER and D M RITCHIE Computational Complexity and Program Structure IBM Research Report, RC-1817.
• 6: A R MEYER and D M RITCHIE Hierarchies of primitive recursive functions, in preparation
• 7: A COBHAM The intrinsic computational difficulty of functions Proc of the 1964 Cong for Logic Meth and Phil of Science North-Holland, Amsterdam 1964
• 8: R W RITCHIE Classes of predictably computable functions Trans Amer Math Soc Vol 106 Jan 1963 pp 139-173.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

General Terms:
Theory