Path: utzoo!attcan!uunet!cs.utexas.edu!sun-barr!rutgers!mcnc!rti!tijc02!pjs269
From: pjs269@tijc02.UUCP (Paul Schmidt        )
Newsgroups: comp.lang.misc
Subject: Re: Re: Expressive Power - What is it ?
Message-ID: <483@tijc02.UUCP>
Date: 1 Jun 89 13:08:43 GMT
References: <769@cf-cm.UUCP> <494@skye.ed.ac.uk>
Organization: Texas Instr., Johnson City TN
Lines: 44

> In article <769@cf-cm.UUCP> ted@computing-maths.cardiff.ac.uk (Ted Lawson) writes:
> >
> >	Can anyone provide or (preferably) point-to a definition of,
> >	or discussion about, the oft-heard term "Expressive Power" ?
> 
> No, this doesn't seem to hold water as a complete definition.  Suppose
> that in language A I can form statements of the type S1, S2 and S3.  In
> language B I can form statements of the type S2, S3, S4,S5, ... 
> S100000. 
> 
> Then language B can be said to be more expressive than language A,
> but language A is handy if I want to execute statements of the
> form S1.
> 
> The definition you suggest does not allow for this sort of case.
> -- 
> Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN

There have been NO languages such as A and B that have ever been discovered.
If I remember correctly there are only three or four classes of expressive power
that have been discovered.  None of these classes intersect, they either contain
a class or are contained in another task.  A digram of this as best as I can
remember is:

+-------------------------+
|    Recursive            |
| +---------------------+ |
| | Partially Recursive | |
| | +-----------------+ | |
| | | ???             | | |
| | | +-------------+ | | |
| | | | ???         | | | |
| | | +-------------| | | |
| | +-----------------+ | |
| +---------------------+ |
+-------------------------+

If you know of any languages such as A and B, please post.

----------------------------------------------------------------------
    Paul Schmidt                           USENET:  rti!tijc02!pjs269
    Texas Instruments                      PHONE:  (615) 461-2461
    PO Drawer 1255 M/S 3517
    Johnson City, TN 37605-1255