A natural generalization of the Turing computability model

Abstract

The Turing computability model is a model of algorithmic symbolic transformations that can be performed by humans. The Church-Turing thesis is a statement about the completeness of their formalisms with respect to this model. Algorithmic transformations are applicable not only to symbols, but also to physical objects. Some of these transformations can be analyzed by means of Turing formalism by way of special character encoding. At the same time, there are physical algorithms that go far beyond the standard Turing model. Examples are recipes, medical procedures, technological processes, etc. Their common feature is not only the operation of physical objects, but also the appeal to external physical processes. The general definition of an algorithm, as prescriptions for a sequence of actions to obtain the desired result, is satisfied by well-known phenomena of goal-directed behavior. Symbolic calculations are a special case of goal-directed behavior.

Models of combined temporal and dynamic logic can be used to analyze goal-directed behavior. Such an analysis allows us to conclude that there are at least three types of elementary rules underlying complex purposeful behavior: 1) passively-processual – "If there is a process $P$, then do nothing, but wait for it to lead you to the desired goal $G$"; 2) constructive – "If there is a $C$, perform action $d$, the immediate result of which is the desired goal $G$"; 3) constructively-processual – "If $C$ takes place, perform action $d$ so that its immediate result $R$ initiates process $P$, which will lead to the desired goal $G$". The combined logic allows you to determine the conditions for the correctness of these rules. Constructively-processual rules have the property of universality, since two other types of rules are reduced to them.

In the paper we define a T-machine (teleological machine) that implements complex goal-directed behavior, and conduct a comparative analysis with Turing machines. It is shown that within the framework of the new algorithmic model there are functions that are computable in it, but not computable in Turing model. In the new model, algorithms have the status of laws of living nature related to the emergence of life and evolution. The algorithmic model of goal-directed behavior can be naturally applied to describe and analyze many phenomena of the social sphere.