On Some Open Problems in the Theory of Cellular Automata

1 June 1974

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-23 (6), 561-565
https://doi.org/10.1109/T-C.1974.223995

Abstract

Some open problems in the theory of cellular automata are considered: the tradeoff between machine complexity and interconnection complexity, linear time pattern recognition and transformation problems, and the noncomputability of the constant of linearity of linear time problems.

Keywords

TRADEOFF
INTERCONNECTION
AUTOMATA
OPEN PROBLEMS
TIME PROBLEMS
MACHINE COMPLEXITY
THEORY OF CELLULAR
NONCOMPUTABILITY
TRANSFORMATION PROBLEMS

Cited by 32 articles