View Related Documents

Abstract

In this paper, we investigate time-constructible functions in one-dimensional cellular automata (CA). It is shown that (i) if a function t(n) is computable by an O(t(n) − n)-time Turing machine, then t(n) is time-constructible by CA and (ii) if two functions are time-constructible by CA, then the sum, product, and exponential functions of them are time-constructible by CA. As an example for which time-constructible functions are required, we present a time-hierarchy theorem based on CA. It is shown that if t 1(n) and t 2(n) are time-constructible functions such that $ \lim _{n \to \infty } \frac{{t_1 (n)}} {{t_2 (n)}} = 0 $ \lim _{n \to \infty } \frac{{t_1 (n)}} {{t_2 (n)}} = 0 , then there is a language which can be recognized by a CA in t 2(n) time but not by any CA in t 1(n) time.

Fulltext Preview

Image of the first page of the fulltext document