Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end just one output symbol "A" for accepting the initial input or "R" for rejecting it.

I guess a solution would be to make a Tag system simulate a specific Turing machine that simulates a finite automaton but that seems too much and too complicated. Is there perhaps a direct way from tag systems to finite automata?


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.