Article View: comp.lang.misc
Article #6519Re: Re: Expressive Power - What is it ?
From: William Clinger
Date: Sat, 03 Jun 1989 01:44
Date: Sat, 03 Jun 1989 01:44
15 lines
1291 bytes
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!willReferences:
<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