Loop-programs and polynomially computable functions

Abstract

By slightly modifying the original definition of loop-programs by Meyer and Ritchie, a modified hierarchy of loop(n) programs, is obtained, with the following characteristics. Let be the class of functions defined by programs in , be the Grzegorzcyk hierarchy. Then , where in particular has a natural counterpart in loop programs. It also turns out that can be characterized as the class of all recursive functions that are computable with a polynomial number of steps by modified programs.

Keywords:

• Loop-programs
• primitive recursive functions
• grzegorzcyk hierarchy
• polynomially computable functions

C.R. Categories:

• 5.24
• 5.25