The Markov algorithm is a simple model of computation. For other models of computation, such as Turing machines, cellular automata, tag systems, etc., there is research on the "minimal" instances of the model that are Turing-universal. Here "minimal" is defined differently depending on the formal system in question, but it tends to mean things along the lines of a small number of states. For example, there is a 2-state, 3-symbol Turing machine that's arguably Turing-complete. Or rule 110 is an (arguably) Turing-universal cellular automaton with two states and a neighbourhood of three.

My question is whether this kind of research has been done in the context of Markov algorithms - are there "minimal" Turing-complete sets of transition rules for a Markov algorithm in the literature?

Note that I'm being deliberately vague about what "minimal" should mean in this context, since I don't want to overly constrain the answers, but I would guess that minimal would mean a small alphabet, a small number of rules, and short search/replace strings within the rules. Similarly, there is leeway in precisely how one would define Turing-universality for a Markov algorithm, but I'd be happy to see results for any half-way reasonable definition.

Note: there is a similar question over on CS.SE, but I thought it would be worth asking here and spelling out more carefully what I'm looking for.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.