Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!mit-eddie!uw-beaver!uoregon!will
From: will@uoregon.uoregon.edu (William Clinger)
Newsgroups: comp.lang.misc
Subject: Re: Re: Expressive Power - What is it ?
Summary: make that "primitive recursion"
Message-ID: <4809@uoregon.uoregon.edu>
Date: 3 Jun 89 01:44:01 GMT
References: <769@cf-cm.UUCP> <494@skye.ed.ac.uk> <483@tijc02.UUCP> <4808@uoregon.uoregon.edu>
Reply-To: will@fog.UUCP (William Clinger)
Organization: University of Oregon, Computer Science, Eugene OR
Lines: 15

Excuse me.  As I was walking home after posting a message to this
newsgroup, I realized that I had said "partial recursive" when I meant
"primitive recursive".  My mind was, as they say, elsewhere.  Here is
a less incorrect version of the  paragraph:

  ...and cites the fact that primitive recursion (without the minimization
  operator) is strictly less powerful than general recursion.  A less
  familiar example is that flowchart schemes (i.e. unbounded iteration) are
  strictly less powerful than recursive schemes.  Another example is that
  deterministic program schemes are strictly less powerful than certain
  classes of nondeterministic program schemes.

I apologize for the confusion this must have caused.

William Clinger