FOM: expr. power of syntax

[Stephen Fenner]

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