Functioning of Inductive Turing Machines
Mark Burgin
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 particular, it is proved that simple inductive Turing machines can solve the Halting Problem for Turing machines, while inductive Turing machines of higher orders can generate and decide the whole arithmetical hierarchy. It means that inductive Turing machines are super-recursive algorithms, which model and perform unconventional computations. At the same time, inductive Turing machines reflect pivotal traits of stabilizing computational processes. In this paper, we study relations between different modes of inductive Turing machines functioning. In particular, it is demonstrated that acceptation by output stabilizing and acceptation by state stabilizing are linguistically equivalent.
Keywords: computation, stability, Turing machine, inductive Turing machine, acceptation, mode of computation