Re: Grammatical Recursion

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

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