12.1372, Disc: How do You Demonstrate Recursiveness?

Fri May 18 20:37:06 UTC 2001

LINGUIST List:  Vol-12-1372. Fri May 18 2001. ISSN: 1068-4875.

Subject: 12.1372, Disc: How do You Demonstrate Recursiveness?

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:  Thu, 17 May 2001 12:59:41 -0400
From:  Stirling Newberry <stnewberry at earthlink.net>
Subject:  Re: 12.1345, Disc: New: How do you demonstrate recursion?

2)
Date:  Fri, 18 May 2001 16:04:23 +0930
From:  David Powers <powers at infoeng.flinders.edu.au>
Subject:  Re: 12.1345, Disc: New: How do you demonstrate recursion?

3)
Date:  Fri, 18 May 2001 10:56:18 -0400
From:  "Michael A. Covington" <mc at ai.uga.edu>
Subject:  Re: 12.1345, Disc: New: How do you demonstrate recursion?

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

Date:  Thu, 17 May 2001 12:59:41 -0400
From:  Stirling Newberry <stnewberry at earthlink.net>
Subject:  Re: 12.1345, Disc: New: How do you demonstrate recursion?

1. The system above (see LINGUIST 12.1345)has not been defined enough
to provide whether recursion is present.

2. One shows a grasp of recursive rules by the ability to take the
products of one verb and use them as object for the same verb.

For example give the person a set of boxes, the boxes are stacked
inside of each other like Russian dolls. The command is "empty
everything out of all of the boxes".

If the person merely takes the first box out of  the largest box,
then they have not grasped recursion.

A complete grasp of recursion is shown only if the subject
understands that it is possible for commands to recurse without
terminating.

Generally the form of recursion in symbolic analytic terms is an
iterative system  is (I am using [] for subscripts because of the
limitations of email text)

m[n]d[n] >> d[n+1]
P(m[n]d[n+1] >> d[n+2])

that is a system where the method is invarient, and it is possible
for the result of the operation to be used as data for the same
method.

-
Stirling Newberry
stnewberry at earthlink.net
http://www.mp3.com/ssn

-------------------------------- Message 2 -------------------------------

Date:  Fri, 18 May 2001 16:04:23 +0930
From:  David Powers <powers at infoeng.flinders.edu.au>
Subject:  Re: 12.1345, Disc: New: How do you demonstrate recursion?

The LINGUIST Network wrote:

> Date:  Wed, 16 May 2001 13:19:51 +1100
> From:  Dorothea Cogill <dcogill at metz.une.edu.au>
> Subject:  How do you demonstrate recursion?
>
> What does it take for someone or something to show a grasp of recursive rules?

This is generally what was addressed by the famous Gold(1967) paper and
the Horning(1969) thesis, and much work on formal grammar learning
since.

The short answer is that a system can only learn from positive
information alone given distributional/probabilistic information
if the grammar is recursive - there will always be non-recursive
grammars that would work as well.

The second question that arises specifically in your example is
whether there is any point in distinguishing between iteration and
recursion, and I would also distinguish recurrence.

> Assume you have a communication system in which some symbols stand for
> actions (let's make those symbols the vowels A E I O & U, but they could be
> anything you please), and other symbols stand for objects to which the
> actions can be applied (let's make these symbols the consonants of the
> alphabet - whatever).  Put two symbols in order, and they amount to a
> command to perform that action on that object.  The correct order is set;
> say it's ACTION + OBJECT, for example.  Then (for the symbols offered
> above) a string like "A Q" is a command to perform action A on object Q;
> throw a ball, for example, if A is  'throw' and Q is 'ball'.
>
> Now, you give these commands to your subject - perhaps a very young child,
> or a computer, or a smart dog - and they perform them correctly.  Then, for
> the first time, you give two commands at once; you might say "AQEP" , for
> example.  Your subject then goes off and performs action A on object Q and
> follows this by performing action E on object P.
>
> The question is - well, I guess there are two questions.
> 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  (I hope your computer is translating these symbols
> correctly!).

PROBABLY NOT!  While it is possible to learn recursive grammar
rules under specific assumption, there is not much evidence that
humans use strictly recursive grammars, and certainly they cannot use
strictly context-free grammars or more complex languages since these
require an infinite stack that does not fit into a finite head.

A regular language corresponds to a tail recursive or head recursive
grammar and is formally equivalent to iteration, and does not require
a stack although without recursion optimization rewrite systems do
typically use a stack even here.  It makes far more sense to see
this as a sequence of essentially independent events each of which
is an S.  The same incidentally applies also to linkages involving
coordination, relatives or various forms of attachment - there is
no contextual memory involved in most cases (leaving aside some
forms of limited centre-embedding).  Thus the "house that Jack built"
and "old woman who swallowed a fly" sentences are also iterative (or
equivalently regular).

If we consider human physiology, and connectionist possibilities for
implementing a language learning/using system, then recurrence is
a far more plausible and well attested mechanism than recursion.
I use the analogy of a painting.  We have a fixed finite memory
rather than a stack, and each new piece of information is like
an additional stroke on the painting which builds up the picture
that is being conveyed by the speaker.  All we need to remember
is what kind of units are in process - are we still extending a
noun phrase object with various attachment?  Are we just producing
a sequence of short sentences.  Recurrence simply means that
the remembered output of previous processes, along with the new
input, are available to the current processes.  Recurrent neural
networks can deal with a limited amount of context, whereas full
recursion (context-free or worse) requires dealing with a potentially
unlimited amount of context and is not a reasonable model.

> 2. does your subject show a grasp of recursive rules in responding to the
> command correctly?

DEFINITELY NOT.  There is no requirement for recursion, and recursive
grammars are relatively difficult to learn - or recursive learners
require specific assumptions of a distributional nature or limiting
the class of possible grammars (normally to being finite).

> No other examples of recursion have been created or tested for this system
> and this subject;  this is the only one you have to go on.
>
> What do you think?

You'll find some further relevant material on my website.

Cheers,
David Powers

-   powers at ieee.org    http://www.cs.flinders.edu.au/People/David_Powers
Associate Professor David M. W. Powers PhD   Facsimile:  +61-8 820 13626
Director, AILab, Informatics & Engineering   UniOffice:     08 820 13663

-------------------------------- Message 3 -------------------------------

Date:  Fri, 18 May 2001 10:56:18 -0400
From:  "Michael A. Covington" <mc at ai.uga.edu>
Subject:  Re: 12.1345, Disc: New: How do you demonstrate recursion?

The problem is, there is no difference in computing power between a
recursive system with a memory limit (a limit on depth of recursion) and a
non-recursive (finite-state) system.  The significant difference is that a
system may be much more concisely and clearly defined by using recursive
rules than by using non-recursive rules; that is, avoidance of recursion
leads to loss of generalizations.  That is the argument for using recursion
in natural language syntax even though the depth of recursion is always
bounded.

Michael A. Covington - Artificial Intelligence Ctr
The University of Georgia - Athens, GA 30602-7415 USA
http://www.CovingtonInnovations.com  http://www.ai.uga.edu/~mc <><

---------------------------------------------------------------------------
LINGUIST List: Vol-12-1372