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 feasibility
Diagonalization and Elementary Complexity
Emanuele Covino;Giovanni Pani
2018-01-01
Abstract
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 feasibilityFile in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
