Diagonalization and Elementary Complexity

By means of the definition of predicative recursion, we introduce a programming language that provides a resource-free characterization of register machines computing their output within polynomial time O(n^k), for each finite k. We extend the language with a constructive diagonalization scheme, and we define a transfinite hierarchy of programs with exponential-time complexity (at level omega^omega), and with elementary complexity (at level epsilon_0). This is achieved by means of predicative operators, contrasting to previous results. We discuss the feasibilit