# Re: Grammatical Recursion

**From:** Helmut Richter (*a282244_at_mail.lrz-muenchen.de*)

**Date:** 12/20/04

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

**Previous message:**Mitch Harris: "Re: Silly Recurrence"**Next in thread:**Jacques Guy: "Re: Grammatical Recursion"**Reply:**Jacques Guy: "Re: Grammatical Recursion"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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
*

*>> <slrncs82lv.qe0.a282244@lxhri01.lrz.lrz-muenchen.de>), "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.
*

Exactly.

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

http://mathworld.wolfram.com/Church-TuringThesis.html).

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"

**Previous message:**Mitch Harris: "Re: Silly Recurrence"**Next in thread:**Jacques Guy: "Re: Grammatical Recursion"**Reply:**Jacques Guy: "Re: Grammatical Recursion"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]