LINGUIST List 12.1372

Fri May 18 2001

Disc: How do You Demonstrate Recursiveness?

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

Directory

1. Stirling Newberry, Re: 12.1345, Disc: New: How do you demonstrate recursion?
2. David Powers, Re: 12.1345, Disc: New: How do you demonstrate recursion?
3. Michael A. Covington, Re: 12.1345, Disc: New: How do you demonstrate recursion?

Message 1: 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
stnewberryearthlink.net
http://www.mp3.com/ssn

Message 2: 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 <dcogillmetz.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

- powersieee.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: 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 <><