HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is unrestricted grammar equivalent to deterministic Turing machine?

Submitted by: @import:stackexchange-cs··
0
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:

  1. Have anybody studied transformations with similar rules?



  1. Which machine accepts language corresponding to such grammars and rules?



  1. 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.