Properties of Stabilizing Computations

Abstract

Models play an important role in the development of computer science and information technology applications.
Turing machine is one of the most popular model of computing devices and computations. This model, or more exactly,
a family of models, provides means for exploration of capabilities of information technology. However, a Turing
machine stops after giving a result. In contrast to this, computers, networks and their software, such as an operating
system, very often work without stopping but give various results. There are dierent modes of such functioning and
Turing machines do not provide adequate models for these processes. One of the closest to halting computation is
stabilizing computation when the output has to stabilize in order to become the result of a computational process.
Such stabilizing computations are modeled by inductive Turing machines. 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. At the same time, inductive Turing machines reflect pivotal traits
of stabilizing computational processes. In this paper, we study relations between dierent modes of inductive Turing
machines functioning. In particular, it is demonstrated that acceptation by output stabilizing and acceptation by state
stabilizing are linguistically equivalent.