Periodic Turing Machines

Abstract

It is proved that 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. Inductive Turing machines are a particular case of periodic Turing machines. Thus, periodic Turing machines are super-recursive algorithms, which are more powerful than Turing machines. At the same time, periodic Turing machines reflect pivotal traits of periodic computational processes. In this paper, we study relations between periodic and inductive Turing machines.

Keywords: computation, stability, Turing machine, inductive Turing machine, periodic Turing machine