This article is cited in 2 papers

Intelligent systems and technologies

Computability via cellular automata

S. V. Gavrilov^a, I. V. Matyushkin^b, A. L. Stempkovsky<sup>a

a</sup> Institute for Design Problems in Microelectronics of Russian Academy of Sciences, Moscow
^b Molecular Electronics Research Institute

Abstract: This review addresses the issues of computations using cellular automata (CA). It is shown that the generality of the connectionism paradigm allows some methods applicable to neural networks to be transferred into the domain of CA. Some special issues of computability are discussed based on the examples of the density classification task, the firing-squad synchronization problem, and the queen-bee problem, as well as sorting algorithms and Atrubin’s parallel multiplication algorithm.

Keywords: cellular automata, computability, signal, sorting, parallel multiplication, Atrubin’s algorithm, Turing machine, time-constructability.

 English version: , 2017, 44:5, 314–328

Bibliographic databases:

•