LINGUIST List 12.1385

Sun May 20 2001

Disc: How Do You Demonstrate Recursion?

Editor for this issue: Karen Milligan <karenlinguistlist.org>

Directory

1. Mike Maxwell, Re: 12.1376, Disc: How Do You Demonstrate Recursion?

Message 1: Re: 12.1376, Disc: How Do You Demonstrate Recursion?

Dorothea Cogill <dcogillmetz.une.edu.au> wrote in LINGUIST List 12.1345:

>What does it take for someone or something to show a grasp of recursive
rules?
>...
>1. does your system possess recursion? After all, if a sentence S is
>ACTION + OBJECT, then two in a row can be written S-> S(S), which can be
>expanded indefinitely...

To which Mark A. Mandel (Mark_Mandeldragonsys.com) replied:
>I wouldn't call that recursion, but simply compounding. As I understand the
>term, you don't have recursion until the output of an operation can serve
>as the input to another instance of the same operation, whether directly or
>via a chain of intervening operations.

Mark is correct; maybe this will help clarify: while "two in a row" _could_
be written (almost--I'll come back to that in a moment) as S-> S(S), it
could also be written U-> S(S), where 'U' is mnemonic for 'Utterance', which
makes it clear that there is no recursion. If you want potentially
infinitely many Ss (which is what S-> S(S) actually gives you, not just
two), it could be written nonrecursively as U --> S+, where '+' is like
Kleene star (usually written with an asterisk), but means "one or more"
('Kleene star' means zero or more). As David Powers (powersieee.org) wrote
(in 12.1372), this is iteration, not recursion.

To be precise, the two notations (S-> S(S) and U-> S+) are weakly, but not
strongly equivalent. That is, they produce the same terminal string, but
not the same structure.

Kleene star/ plus is finite state (not recursive). Note that if S -->
Action Object, then U --> S+ can be rewritten without loss as
 U --> (Action Object)+
and since the "U" doesn't really buy you anything (it can't be used in
another rule), this is really equivalent to the finite state expression
(Action Object)+ all by itself.

There is some discussion of this kind of thing in Chomsky's "Syntactic
Structures", in which he notes that a finite state machine can produce a
potentially infinite set of sentences. (His example is s.t. like "The
man"--"The old man"--"The old old man"...) He then goes on to argue that
the syntax of human language is not finite state (although the human parser
might be). It was written in 1957, but IMHO it's still worth reading.

 Mike Maxwell
 Summer Institute of Linguistics
 Mike_Maxwellsil.org