Nonlinear phenomena in spaces of algorithms

Abstract

Nonlinear phenomena, which are so important in nature and society, are considered here in relation to the world of algorithms and computations. To have a mathematical model for this world, formal computability spaces are introduced. It is demonstrated that the traditional approach to algorithms, which is based on such popular models as Turing machines, results in linear subspaces of the computability space. Nonlinear phenomena appear when we go to the more powerful class of such super-recursive algorithms as inductive Turing machines. It is demonstrated how this nonlinearity imports much higher computing power of inductive Turing machines in comparison with conventional Turing machines. This provides a base to consider problems of chaos, emergent computations and infinity from the algorithmic point of view.

Keywords:

• Emerging computation
• Recursive algorithm
• Super-recursive algorithm
• Arithmetical hierarchy
• Computability space
• Chaos
• Inductive Turing machine