Letting Alice and Bob choose which problem to solve: Implications to the study of cellular automata

Abstract

In previous works we found necessary conditions for a cellular automaton (CA) in order to be intrinsically universal (a CA is said to be intrinsically universal if it can simulate any other). The idea was to introduce different canonical communication problems, all of them parameterized by a CA. The necessary condition was the following: if Ψ is an intrinsically universal CA then the communication complexity of all the canonical problems, when parameterized byΨ, must be maximal. In this paper, instead of introducing a new canonical problem, we study the setting where they can all be used simultaneously. Roughly speaking, when Alice and Bob – the two parties of the communication complexity model – receive their inputs they may choose online which canonical problem to solve. We give results showing that such freedom makes this new problem, that we call Ovrl, a very strong filter for ruling out CAs from being intrinsically universal. More precisely, there are some CAs having high complexity in all the canonical problems but have much lower complexity in Ovrl.