What is a symbol system?

[mclennan%MACLENNAN.CS.UTK.EDU@cs.utk.edu]

Steve Harnad has invited rival definitions of the notion of a
symbol system.  I formulated the following (tentative) definition
as a basis for discussion in a connectionism course I taught last
year.  After stating the definition I'll discuss some of the ways
it differs from Harnad's.


              PROPERTIES OF DISCRETE SYMBOL SYSTEMS

 A.  Tokens and Types

      1.  TOKENS can be unerringly separated from the background.

      2.  Tokens can be unambiguously classified as to TYPE.

      3.  There are a finite number of types.

 B.  Formulas and Schemata

      1.  Tokens can be put into relationships with one another.

      2.  A FORMULA is an assemblage of interrelated tokens.

      3.  Formulas comprise a finite number of tokens.

      4.  Every formula results from a computation (see below)
          starting from a given token.

      5.  A SCHEMA is a class of relationships among tokens that
          depends only on the types of those tokens.

      6.  It can be unerringly determined whether a formula
          belongs to a given schema.

 C.  Rules

      1.  Rules describe ANALYSIS and SYNTHESIS.

      2.  Analysis determines if a formula belongs to a given
          schema.

      3.  Synthesis constructs a formula belonging to a given
          schema.

      4.  It can be unerringly determined whether a rule applies
          to a given formula, and what schema will result from
          applying that rule to that formula.

      5.  A computational process is described by a finite set of
          rules.

 D.  Computation

      1.  A COMPUTATION is the successive application of the
          rules to a given initial formula.

      2.  A computation comprises a finite number of rule appli-
          cations.


               COMPARISON WITH HARNAD'S DEFINITION

 1.  Note that my terminology is a little different from Steve's:
     his "atomic tokens" are my "tokens", his "composite tokens"
     are my "formulas".  He refers to the "shape" of tokens,
     whereas I distinguish the "type" of an (atomic) token from
     the "schema" of a formula (composite token).

 2.  So far as I can see, Steve's definition does not include
     anything corresponding to my A.1, A.2, B.6 and C.4.  There
     are all "exactness" properties -- central, although rarely
     stated, assumptions in the theory of formal systems.  For
     example, A.1 and A.2 say that we (or a Turing machine) can
     tell when we're looking at a symbol, where it begins and
     ends, and what it is.  It is important to state these
     assumptions, because they need not hold in real-life pattern
     identification, which is imperfect and inherently fuzzy.
     One reason connectionism is important is that by questioning
     these assumptions it makes them salient.

 3.  Steve's (3) and (7), which require formulas to be LINEAR
     arrangements of tokens, are too restrictive.  There is noth-
     ing about syntactic arrangement that requires it to be
     linear (think of the schemata used in long division).
     Indeed, the relationship between the constituent symbols
     need not even be spatial (e.g., they could be "arranged" in
     the frequency domain, e.g., a chord is a formula comprising
     note tokens).  This is the reason my B.5 specified only
     "relationships" (perhaps I should have said "physical rela-
     tionships").

 4.  Steve nowhere requires his systems to be finite (although it
     could be argued that this is a consequence of their being
     PHYSICAL systems).  I think finiteness is essential.  The
     theory of computation grew out of Hilbert's finitary
     approach to the foundations of mathematics, and you don't
     get the standard theory of computation if infinite formulas,
     rules, sets of rules, etc. are allowed.  Hence my A.3, B.3,
     C.5, D.2.

 5.  Steve requires symbol systems to be semantically interpret-
     able (8), but I think this is an empty requirement.  Every
     symbol system is interpretable -- if only as itself (essen-
     tially the Herbrand interpretation).  Also, mathematicians
     routinely manipulate formulas (e.g., involving differen-
     tials) that have no interpretation (in standard mathematics,
     and ignoring "trivial" Herbrand-like interpretations).

 6.  Steve's (1) specifies a SET of formulas (physical tokens),
     but places no restrictions on that set.  I'm concerned that
     this may permit uncountable or highly irregular sets of for-
     mulas (e.g., all the uncomputable real numbers).  I tried to
     avoid this problem by requiring the formulas to be generat-
     able by a finite computational process.  This seems to hold
     for all the symbol systems discussed in the literature; in
     fact the formation rules are usually just a context-free
     grammar.  My B.4 says, in effect, that there is a generative
     grammar (not necessarily context free) for the formulas, in
     fact, that the set of formulas is recursively enumerable.

 7.  My definition does not directly require a rule itself to be
     expressible as a formula (nearly Steve's 3), but I believe I
     can derive this from my C.1, C.2, C.3, although I wouldn't
     want to swear to it.  (Here's the idea:  C.2 and C.3 imply
     that analysis and synthesis can be unambiguously described
     by formulas that are exemplars of those schemata.  Hence, by
     C.1, every rule can be described by two examplars, which are
     formulas.)

Let me stress that the above definition is not final.  Please
punch holes in it!

               Bruce MacLennan
               Department of Computer Science
               107 Ayres Hall
               The University of Tennessee
               Knoxville, TN 37996-1301

               (615)974-0994/5067
               maclennan at cs.utk.edu