Inductively Computable Hierarchies and Inductive Algorithmic Complexity

Abstract

Induction is a prevalent cognitive method in science while inductive computations are popular in many fields of computer and network technology The most advanced mathematical model of inductive computations and reasoning is an inductive Turing machine which is natural extension of the most widespread model of computing devices and computations - Turing machine In comparison with Turing machines inductive Turing machines represent the next step in the development of computer science providing better models for contemporary computers and computer networks In this paper Section 3 we study relations between inductively computable sets inductively recognizable sets inductively decidable sets and inductively computable functions In addition Section 4 we apply the obtained results to algorithmic information theory demonstrating how inductive Turing machines allow obtaining more information for essentially decreasing complexity in comparison with Turing machines