12.1385, Disc: How Do You Demonstrate Recursion?

[The LINGUIST Network]

LINGUIST List:  Vol-12-1385. Sun May 20 2001. ISSN: 1068-4875.

Subject: 12.1385, Disc: How Do You Demonstrate Recursion?

Moderators: Anthony Aristar, Wayne State U.<aristar at linguistlist.org>
            Helen Dry, Eastern Michigan U. <hdry at linguistlist.org>
            Andrew Carnie, U. of Arizona <carnie at linguistlist.org>

Reviews (reviews at linguistlist.org):
	Simin Karimi, U. of Arizona
	Terence Langendoen, U. of Arizona

Editors (linguist at linguistlist.org):
	Karen Milligan, WSU 		Naomi Ogasawara, EMU
	Lydia Grebenyova, EMU		Jody Huellmantel, WSU
	James Yuells, WSU		Michael Appleby, EMU
	Marie Klopfenstein, WSU		Ljuba Veselinova, Stockholm U.
	Heather Taylor-Loring, EMU	Dina Kapetangianni, EMU

Software: John Remmers, E. Michigan U. <remmers at emunix.emich.edu>
          Gayathri Sriram, E. Michigan U. <gayatri at linguistlist.org>

Home Page:  http://linguistlist.org/

The LINGUIST List is funded by Eastern Michigan University, Wayne
State University, and donations from subscribers and publishers.



Editor for this issue: Karen Milligan <karen at linguistlist.org>

=================================Directory=================================

1)
Date:  Sat, 19 May 2001 22:31:01 -0400
From:  "Mike Maxwell" <Mike_Maxwell at sil.org>
Subject:  Re:      12.1376, Disc: How Do You Demonstrate Recursion?

-------------------------------- Message 1 -------------------------------

Date:  Sat, 19 May 2001 22:31:01 -0400
From:  "Mike Maxwell" <Mike_Maxwell at sil.org>
Subject:  Re:      12.1376, Disc: How Do You Demonstrate Recursion?

Dorothea Cogill <dcogill at metz.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_Mandel at dragonsys.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 (powers at ieee.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_Maxwell at sil.org

---------------------------------------------------------------------------
LINGUIST List: Vol-12-1385