FOM: Expressiveness of Language II - Into the Tarpit

[Dennis E. Hamilton]

6.	Change of Representation

If we abandon ideas of expressiveness, we can come up with a regular
expression form of all propositional expressions.  It's not pretty.

6.1	The language pex is solvable.  So there is an enumeration of its
strings.

6.2	Wonderful, just replace the expressions by their consecutive numbers in
any chosen enumeration scheme.

6.3	Express the numbers in the language pex0 ::= "0" | pex0 "+"
	(a language isomorphic to our little pv language).

6.4	I assume this does not satisfy anyone's notion of "expressiveness."  It
looks like I just changed a linear time process (in terms of pex string
lengths) into a linear time process (in terms of pex0 string lenghts) plus
extra effort.

This suggests to me that one must be extremely careful in conversations
about changes of representation.  I have no particular conversation in mind,
this just jumped out at me.  The answer is "42."

7.	Close to the Edge

7.1 One thing I notice about pex (or any more articulated language for
propositional expressions), is that it is easy to provide a linear-time
acceptor.  Instead of a finite state machine, we need an auxillary store of
some sort to keep track of the nesting depth.  A very simple push-down will
work.

7.2 So a general context-free acceptor is not required. Not even close to
it.  I don't want to say that pex is "nearly-regular," but it is
regular-plus-a-little-more and that is a modest demand.

7.3 So this leads to a natural conjecture concerning first-order logic.  If
we require fully-quantified (no free-variables at the top) expressions, then
there is no context-free grammar for FOL because we need to be able to
express having all variables bound by quantifiers, and there is no
context-free way to establish that condition in the conventional FOL
notation.  On the other hand, we don't need to deal with the general
context-sensitive case either.  Typical approaches include

 - Using a context-free grammar plus constraints to deal with binding of
free occurrences to quantifiers

 - Defining context-free-grammars plus a little more just to deal with
scopes and name bindings.

These are each genuine extensions to the grammar model, not syntactic
sugarings of already-expressible cases.

7.4. Something to muse over.  It seems that no more grammatical machinery is
required to move to FOL with equality or to PA.  I think this is not new
news, but it might give a sense of how modest our demands for expressive
power happen to be.




-----Original Message-----
From: Dennis E. Hamilton [mailto:dennis.hamilton at acm.org]
Sent: Saturday, July 20, 2002 14:28
To: fom at math.psu.edu
Cc: T.Forster at dpmms.cam.ac.uk; crouch at parc.xerox.com;
paiva at parc.xerox.com
Subject: Expressiveness of Language I - Regular versus Context-Free


[ ... ]

1.	pv ::= "p" | pv "q"

[ ... ]

2.	For the language of propositional logic, consider the simplification to
one primitive:

pex ::= pv | "/" pex1 pex2

pex1 ::= pex

pex2 ::= pex

[ ... ]

-- orcmid

------------------
Dennis E. Hamilton
http://orcmid.com/
mailto:dennis.hamilton at acm.org
tel. +1-206-932-6970
cell +1-206-779-9430
     The Miser Project: http://miser-theory.info