Inductive Turing Machines of Higher Orders: Computability, Acceptability and Decidability

Abstract

In this paper, the basic forms of information processing by inductive Turing machines of the order n are explored where n  1. It is demonstrated that different types of acceptability, recognizability, and computability of sets and formal languages by inductive Turing machines of the order n are equivalent. This allows high flexibility in modeling functioning of computers and computer networks by choosing the better suited forms of information processing. In addition, it is described how these forms are related to decidability of sets and formal languages by inductive Turing machines of the order n. Based on the obtained results, examples of undecidable, noncomputable and unrecognizable languages of inductive Turing machines of the order n are constructed.