Re: Grammatical Recursion

From: Helmut Richter (
Date: 12/20/04

  • Next message: Jacques Guy: "Re: Grammatical Recursion"
    Date: 20 Dec 2004 11:50:11 GMT

    [Followup-To: comp.theory]

    Jacques Guy:

    > Helmut Richter wrote:
    >> No. As I wrote (later than the posting you quoted, to wit in
    >> <>), "recursive" is
    >> not a good term to characterise languages, except if it is to mean
    >> "decidable" (or, equivalently, that the language and its complement
    >> are both recursively enumerable); and if this is intended, "decidable"
    >> is an unambiguous term not provoking misunderstandings.

    > If I understand you correctly, that is deciding whether this or
    > that is a member of this set, knowing what defines the set.


    Formal grammars are ways to *enumerate* sentences recursively. You could
    start with the start symbol (not strictly a sentence, only a sentential
    form as it still contains nonterminal symbols) as single entry in a list,
    and then go on recursively: Take up the next item F of the list, find the
    finitely many sentential forms that are produced by replacing one (of the
    finitely many) left-hand sides of rules in F by the right-hand side of one
    (of the finitely many) rules for it and add the result to the
    list. Obviously, one will thus enumerate all sentential forms and hence
    also all sentences.

    This is, however, not a *decision* procedure. For a decision procedure, it
    is required that it terminate in finite time telling whether a sentence
    candidate is indeed a sentence. The enumeration process of the last
    paragraph, however, will not tell anything if the string at hand is not a
    candidate. But if you have two enumeration procedures, one enumerating all
    sentences and one enumerating all non-sentences, you can apply them
    alternatingly, and each candidate will show up after finite time as output
    of one of the two enumerations. This is why I wrote « "decidable" (or,
    equivalently, that the language and its complement are both recursively
    enumerable) ».

    > Take a set that has been defined recursively. It could also
    > have been defined iteratively--why, even the Ackermann function
    > (see the URL to which I gave a link). And vice versa.
    > And the test for its membership can be recursive, or
    > iterative, or... (heh, heh, heh), label-jumpive :-)

    There are many ways to define precisely what a computable function
    is. Most of them turn out to be equivalent, and no meaningful notion of
    decidability or computability has been found that would be outside the
    realm of (precisely defined) recursive functions, or of Turing machines,
    or of µ-recursive functions, or of (precisely defined) computer programs
    where loops are allowed whose end is not predictable upon entry, or many
    other models. It is therefore reasonable to say, albeit not provable due
    to lack of precision of the statement, that these models do represent what
    we mean with computable or decidable (Church-Turing thesis, see

    Unfortunately, most books concentrate either on formal theory or on real
    computing but do not connect the two. A fairly old one (1973) that does is
    "Theory of Computation" by Brainerd and Landweber.

    I consider the bearing for linguistics minimal. There, most things are
    obviously decidable and nobody cares if some end cases are not (the
    meaning of an ambiguous sentence for instance). I therefore suggest to
    continue the discussion in comp.theory, if there is still interest.

    Helmut Richter

  • Next message: Jacques Guy: "Re: Grammatical Recursion"