NOTION OF A PROBABILISTIC CELLULAR ACCEPTOR

The combination of the notions of a cellular automaton and a probabilistic automaton, called a probabilistic cellular automaton, was proposed in 1973 by the first author of this paper as a more adequate model of any system with unreliable components that operate in a parallel manner. In this paper a language-acceptor type of such a probabilistic cellular automaton, called a probabilistic bounded cellular acceptor (PBCA), is defined and studied. It is shown that the class of all languages accepted by one-dimensional PBCAs includes both the class of all languages accepted by bounded cellular acceptors (BCAs) and the class of all languages accepted by probabilistic acceptors (PAs). Also, it is shown that every language accepted by a d-dimensional PBCA at a given cut point is accepted by a d-dimensional PBCA at an arbitrary nonzero cut point. The class of all languages accepted by one-dimensional PBCAs at cut point 0 is shown to be precisely the class of all context-sensitive languages. Several decision problems for PBCAs are shown to be recursively unsolvable. Finally, various open problems concerning PBCAs and PBCLs are discussed. © 1979 Plenum Publishing Corporation.