On time computability of functions in one-way cellular automata
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.