patternMinor
Is unrestricted grammar equivalent to deterministic Turing machine?
Viewed 0 times
unrestrictedequivalentgrammardeterministicmachineturing
Problem
Suppose we have unrestricted grammar but with restrictions on how rules are applied: we take first rule, search in string left to right and apply it as we go. If no match found, we proceed with second rule and so on. Else, if match(es) is found, we return to first rule and start of the string and start loop again.
I have 3 questions:
I have 3 questions:
- Have anybody studied transformations with similar rules?
- Which machine accepts language corresponding to such grammars and rules?
- How one can alter described algorithm to make deterministic Turing machine such a corresponding machine?
Solution
Such a grammar system is Turing-complete. I can encode a tag system, and tag systems are known to be Turing-complete.
Context
StackExchange Computer Science Q#60673, answer score: 2
Revisions (0)
No revisions yet.