3 ms·

Maybe I'm being too literal, but how can a grammar be Turing complete? The usual definition of Turing completeness is being able to simulate an arbitrary Turing

Maybe I'm being too literal, but how can a grammar be Turing complete? The usual definition of Turing completeness is being able to simulate an arbitrary Turing machine. Typical human languages don't do beta reductions like Lambda Calculus, so I fail to see how a grammar (or the language produced by the grammar) can be said to compute anything.

aleeds 10y ago
From what I understand, the idea is you have some string S and an input T, and running a grammar G on ST will produce an output. Sometimes they won't halt. Just like a Turing machine. In this analogy G is the 'universal Turing machine'
- zingermc 10y ago
  Interesting! I think I am starting to get it. To double check, is running a grammar the same as parsing?
  - thesz 10y ago
    The two-level grammars are doing things in two steps: parsing of part of the text yields a grammar for parsing the rest of it. The Algol-68 was specified using two level grammar and if I understand it correctly, the declaration part constrained parsing of the statement part so that only valid expressions can be parsed. Parsed statements are valid in the semantic sense, i.e., the subscription can be applied only to array values and parser will reject subscription for scalar values. To generate the grammar you need to execute some function. And this function depends on the part of input.
    - zingermc 10y ago
      Wow, the two-level grammar concept is incredible! I have some learning to do. Thank you for sharing.
mcguire 10y ago
Regular expressions = regular languages. Stack machines = context free languages = primitive recursive functions. (?) Turingmachines = context sensitive languages = total recursive functions. (?) Or something like that.
- thesz 10y ago
  You are wrong. Primitive recursive functions alone are able to recognize formal languages: https://en.wikipedia.org/wiki/PR_(complexity) https://en.wikipedia.org/wiki/PR_(complexity) PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided by such a function.

aleeds 10y ago

From what I understand, the idea is you have some string S and an input T, and running a grammar G on ST will produce an output. Sometimes they won't halt. Just like a Turing machine. In this analogy G is the 'universal Turing machine'

zingermc 10y ago
Interesting! I think I am starting to get it. To double check, is running a grammar the same as parsing?
- thesz 10y ago
  The two-level grammars are doing things in two steps: parsing of part of the text yields a grammar for parsing the rest of it. The Algol-68 was specified using two level grammar and if I understand it correctly, the declaration part constrained parsing of the statement part so that only valid expressions can be parsed. Parsed statements are valid in the semantic sense, i.e., the subscription can be applied only to array values and parser will reject subscription for scalar values. To generate the grammar you need to execute some function. And this function depends on the part of input.
  - zingermc 10y ago
    Wow, the two-level grammar concept is incredible! I have some learning to do. Thank you for sharing.

mcguire 10y ago

Regular expressions = regular languages. Stack machines = context free languages = primitive recursive functions. (?) Turingmachines = context sensitive languages = total recursive functions. (?) Or something like that.

thesz 10y ago
You are wrong. Primitive recursive functions alone are able to recognize formal languages: https://en.wikipedia.org/wiki/PR_(complexity) https://en.wikipedia.org/wiki/PR_(complexity) PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided by such a function.