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 ?
Message-ID: <4808@uoregon.uoregon.edu>
Date: 3 Jun 89 00:02:47 GMT
References: <769@cf-cm.UUCP> <494@skye.ed.ac.uk> <483@tijc02.UUCP>
Reply-To: will@fog.UUCP (William Clinger)
Organization: University of Oregon, Computer Science, Eugene OR
Lines: 26

In article <483@tijc02.UUCP> pjs269@tijc02.UUCP (Paul Schmidt        ) writes:
>If I remember correctly there are only three or four classes of expressive
>power that have been discovered....

and cites the fact that partial recursion (i.e. bounded iteration)
is strictly less powerful than 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.

The problem with discussing expressive power is that powerful data
structures (e.g. integers of unbounded size) can in theory simulate
powerful control structures, and vice versa, but this theoretical
result is of no practical importance since nobody in their right mind
is going to simulate (e.g.) recursion by encoding the program state
as an (e.g.) integer.  By abstracting away from the data types using
schemes, you can make finer distinctions that have more to do with
the expressive power of languages in practice.

Would you believe that Fortran IV (assuming integers of bounded size,
and a finite set of representable reals) would not have been Turing
equivalent without the REWIND statement?

Peace,
William Clinger