Part 3. Mathematical models

Computability of integer functions by means of collectives of two automata

V. V. Uschakova

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: In this work the computability of one-place partial functions of countable-valued logic by collectives of automata is explored. The class of functions computable by two-automata collectives is found. These are periodic functions and the simplest linear functions, which, starting from some value of the argument $x$ behave like $ f(x) = x + C $ function. It is shown that the class of one-place partial functions of countable-valued logic computable by three-automata collectives is wider.

Keywords: computability, automaton, collectives of automata, periodic functions.