One class of exactly solvable quantum many-body systems is the set of dual unitary quantum circuits, whose fundamental quantum gate is also unitary in the space direction. In these models the infinite temperature dynamical correlation functions can be calculated exactly both for integrable and chaotic systems. For local dimension N=2 the complete classification is known, and multiple general construction procedures were studied in the case of higher N. One special class is formed by classical cellular automata corresponding to cases when the quantum gate is simply a permutation. Our recent study with Balázs Pozsgay focused on these models and led to some unexpected results. The presence of conserved quantities induces non-ergodic behaviour, which we studied by investigating the recurrence time. We found models lacking the Yang-Baxter integrability structure but still possessing an infinite number of charges. We also observed that maximally chaotic circuits can show signs of non-ergodicity if they are constructed from a linear map over finite fields.