ИСТИНА |
Войти в систему Регистрация |
|
ФНКЦ РР |
||
The notion of computability of unary partial functions f: N0 '→N0 by collection of automata on the integer line is considered. The value of the argument is set by the distance between certain automata of the collection in its initial arrangement, and the result is equal to the distance between certain automata of the collection in its final arrangement, provided that the collection stops. Small collections of automata have more limited computational capabilities than Turing machines. Accordingly, the classes of functions computable by collectives of automata are subclasses of computable functions. This work is aimed at stratifying all unary computable functions into subclasses according to the minimum number n of automata in the collection required to compute this function. The class of partial functions calculated by collections of n automata is denoted as Fn. Starting from some number n, a collection of n automata can simulate any, including the Universal Turing machine, i.e. the corresponding subclass of functions Fn becomes equal to the class of all computable functions F. We can assume that the function is more complex, the more automata are required to compute it. Thus, in this work, one of the new types of computability complexity of functions is studied, which until recently has not been studied by anyone. The class F3 is partially found.