On time computability of functions in one-way cellular automata

Files in this item
Date
1995Author
Buchholz, Thomas
Kutrib, Martin
Quotable link
http://dx.doi.org/10.22029/jlupub-1982Abstract
The capability of oneway (spacebounded) cellular automata (OCA) to timecompute functions is investigated. That means given an constant input of length n a distinguished cell has to enter a distinguished state exactly after f(n) time steps. The family of such functions (C (OCA)) is characterized in terms of formal language recognition. Several ... functions are proved to be timecomputable and properties of C(OCA) are given. The timecomputation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time.