🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.lang.misc
Article #6519

Re: Re: Expressive Power - What is it ?

#6519
From: William Clinger
Date: Sat, 03 Jun 1989 01:44
15 lines
1291 bytes
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
Technical Details
Message-ID: <4809@uoregon.uoregon.edu>
Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!mit-eddie!uw-beaver!uoregon!will
References: <769@cf-cm.UUCP> <494@skye.ed.ac.uk> <483@tijc02.UUCP> <4808@uoregon.uoregon.edu>

Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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