In Herre & Schroeder-Heister's "Formal Languages and Systems", on p7,
Like grammars, rule-based systems (e.g. deductive systems in logic) are as powerful as Turing machines, i.e. they can be used to express any algorithm.
By "express any algorithm", does it mean that an algorithm is expressed as a string in a language?
How is any algorithm expressed by any of the three?
For a grammar, does it mean that a grammar generates a language?
For a Turing machine, does it mean that a Turing machine accepts a language?
How is a rule-based system used to express an algorithm?
Does their equivalence for "express any algorithm" mean the same as equivalence for computability in Church-Turing thesis:
Church[3] and Turing[4][6] proved that these three formally defined classes of computable functions coincide: a function is λ-computable if and only if it is Turing computable, and if and only if it is general recursive.
- Does a rule-based system correspond to lambda calculus?
- What does a grammar correspond to?
Thanks.