Ebook: Super-Recursive Algorithms

The main achievement of the theory of computations is the elaboration of an exact mathematical model of an algorithm done less than seventy years ago by introducing recursive and partial recursive functions, Turing machines, and Post formal systems. The famous Church-Turing Thesis claims that these models (called recursive algorithms) are the most general. The reason of this is that all mathematical models of algorithms that appeared later were either equivalent or even weaker than Turing machines (or equivalently, partial recursive functions). Theory of super-recursive algorithms refutes this Thesis because computing power of super-recursive algorithms is much greater than that of the conventional, or recursive, algorithms. Consequently, the discovery of super-recursive algorithms provides for a new understanding of some important mathematical results including the famous Gödel incompleteness theorem. In 'Super-Recursive Algorithms,' fundamentals of the theory of super-recursive algorithms will be explained. It will be demonstrated that while recursive algorithms gave a correct theoretical representation of computers at the beginning of the 'computer era', super-recursive algorithms are more adequate as mathematical models for modern computers. In addition to this, super-recursive algorithms provide for a better theoretical frame for computing methods in various areas: for numerical analysis, for search and other operations with huge data arrays, for control and monitoring systems, etc. In the lecture, emphasize will be given to applications related to search in huge and, especially, in dynamic data arrays.