FOM: expr. power of syntax

[Steve Stevenson]

>From what I see, you can't parse ~~~~~~~x1 or ~(p->v). Your "var"
definition doesn't have to be that restrictive.

steve




Stephen Fenner writes:
 > On Thu, 18 Jul 2002, Thomas Forster wrote:
 > 
 > > Yes, that's the easy bit.  The harrd bit is to find a formal way
 > > of saying something like: no language with the expressive power of
 > > propositional logic can be regular.  It's pretty clear that something
 > > like that must be true, but i'm not sure how to state it!
 > >
 > >
 > 
 > >From a programming languages perspective, assembly/machine languages
 > (which are regular, or can be idealized to be regular), are every bit as
 > expressive as higher-level programming languages, i.e., they are
 > "general-purpose"--able to compute any computable function.  This is clear
 > from the fact that compilers routinely translate high-level languages into
 > machine language.
 > 
 > For propositional logic, consider the regular language given by the
 > following rules (named regular expressions):
 > 
 > digit  = 0|1|2|3|4|5|6|7|8|9
 > number = {digit}{digit}*
 > var    = X{number}
 > neg    = ~{var}
 > literal= {var}|{neg}|true|false
 > conj   = {literal}&{literal} | {literal}
 > disj   = {conj}v{conj} | {conj}
 > rule   = {var}:={disj}
 > formula= {rule}*
 > 
 > [Here, "|" means union and "*" means Kleene closure and {name} means
 > substitute the regular expression previously bound to that name.]
 > 
 > The language is given by the last regular expression ({formula}).  Any
 > propositional formula is computably translatable into a string in this
 > language which preserves meaning and vice versa, given an appropriate
 > semantics on the latter.
 > 
 > Steve
 > 
 > 
 >