Algorithmic complexity of recursive and inductive algorithms

摘要

The main goal of this paper is to compare recursive algorithms such as Turing machines with such super-recursive algorithms as inductive Turing machines. This comparison is made in a general setting of dual complexity measures such as Kolmogorov or algorithmic complexity. To make adequate comparison, we reconsider the standard axiomatic approach to complexity of algorithms. The new approach allows us to achieve a more adequate representation of static system complexity in the axiomatic context. It is demonstrated that for solving many problems inductive Turing machines have much lower complexity than Turing machines and other recursive algorithms. Thus, inductive Turing machines are not only more powerful, but also more efficient than Turing machines.