Semantics, I suppose. Those ANNs were Markov chains, in a sense.

Pop a loop around a Markov chain that provides a "tape interface" and you have something capable of simulating a Turing machine. So when people bring up the Markov chains argument, they're saying next to nothing about the potential computational abilities of the system, even though they usually intend to dismiss it.

I tend to see people bringing that up in a dismissive way (not suggesting you are) as a clear indication they either haven't thought the argument through or do not understand how little it takes for a system to be Turing complete, and so for that argument to be meaningless.

I mean, I’m not sure what you’re trying to prove by asking for a Markov chain model like that. It’s trivially true that you can have a Markov chain output whatever you like (somewhat artificially, but we are talking about memorisation here) if you pick your training data carefully.

So "pick the training data carefully," and show me what I'm asking for, given that it is "trivial."

The data consists of a graph whose vertices correspond to the output sequence you desire and where there is an edge (with probability 1) from string x to string y if and only if x precedes y.

This model will arise from the desired sequence as a single training example (learning the probability of each pair of consecutive tokens), provided none are repeated.

Now run your Markov chain with initial input {first token in your sequence}.

Put a loop around a Markov chain where you provide a 'tape interface' taking instructions from and feeding input back to, the state, and you have a Markov decision process with a hard-wired decision maker acting as the tape. Provide the right Markov chain, and you have a universal Turing machine. So the extension needed from a Markov chain to something that could be programmed to do what you describe - say by running an ML model - is only very slight. And we do provide loops, and state when we run inference, just not infinite.

I'm agreeing with your overall point, to be clear - my point is that calling something a Markov chain is effectively calling it trivially extendable to something that can in principle compute everything any physical entity confined to the known laws of physics can, and so what it boils down to is whether or not the model is trained in a way that gives it those abilities, and not the put-down of the potential ability of such a system that people usually intend the "just a Markov chain" as.