The head of a Turing machine is a Markov chain, even simpler even as it transitions completely predictably. But give it a tape and it can compute anything.