Proof-Theoretic Cellular Automata as Logic of Unconventional Computing
Andrew Schumann
Conventional logic assumes that all basic logical processes (deduction, valuation) are sequential. Almost all modern logical systems are conventional in this meaning. However, everywhere in the nature we can observe massively parallel processes that might be simulated by cellular automata. In unconventional computing there have been proposed different computational models in which massive parallelism is taken into account. Nevertheless, the question what the logic of unconventional computing is should be considered as open still. In this chapter proof-theoretic automata are proposed, where all basic logical processes (deduction, valuation) are regarded as massive-parallel ones. In these automata cell states are examined as well-formed formulas of a logical language. As a result, in deduction we can obtain not only derivation trees, but also a linear evolution of each singular premise. Thereby some derivation traces may be circular, i.e. some premises could be derivable from themselves, and hence some derivation traces may be infinite.
Keywords: Cellular automata; mobile automata; concurrent automata; spatial automata; Belousov-Zhabotinsky reaction; epidemic spreading; Physarum polycephalum