\(n\)-dimensional Markov-like algorithms (Q2769247)

The authors define with some effort and illustrate by examples a notion of Markov-like algorithms operating on \(n\)-dimensional words, i.e., patterns given by partial functions (with finite domains) from \(\mathbb{N}^n\) into some alphabet. Slicewise representations of \(n\)-dimensional words by \((n-1)\)-dimensional ones are the basis of comparing the computational power of (classes of) algorithms operating on different dimensions. The main theorem is not surprising: with respect to those representations, the \(n\)-dimensional Markov algorithms are just as powerful as the usual (one-dimensional) normal Markov algorithms.