Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!decwrl!ucbvax!ucbcad!zen!ucla-cs!berke
From: berke@CS.UCLA.EDU
Newsgroups: sci.lang,comp.ai,comp.ai.neural-nets
Subject: Re: Infinite alphabets - (Turing via Berke)
Message-ID: <8583@shemp.UCLA.EDU>
Date: Mon, 12-Oct-87 21:26:36 EDT
Article-I.D.: shemp.8583
Posted: Mon Oct 12 21:26:36 1987
Date-Received: Wed, 14-Oct-87 05:34:05 EDT
References: <154@Aragorn.UUCP> <114400001@exunido.UUCP> <364@su-russell.ARPA> <17@krafla.UUCP>
Sender: root@CS.UCLA.EDU
Reply-To: berke@CS.UCLA.EDU (Peter Berke)
Organization: UCLA Computer Science Department
Lines: 68
Summary: Quotation of Turing on alphabet size
Xref: mnetor sci.lang:1553 comp.ai:884 comp.ai.neural-nets:1


I thought you might find Turing's words on the subject interesting.
These are from his 1936/7 article "On Computable Numbers, with
an application to the Entscheidungsproblem."  I think they are 
important.  I also quote them in my article "That Does Not Compute"
from ICNN '87, distinguishing brains from computers from neural
networks, an expanded version of which I have submitted to Computer 
Magazine. Turing:

"If we regard a symbol as literally printed on a square... The symbol
is defined as a set of points in theis square, viz. the set occupied
by the printer's ink.  If these sets are restricted to be measurable,
we can define the "distance" between two symbols as the cost of 
transforming one symbol into the other if the cost of moving unit area 
of printer's ink unit distance is unity..."

He later goes on...

"I shall also suppose that the number of symbols which may be printed
is finite.  If we were to allow an infinity of symbols, then there would
be symbols differing to an arbitrarily small extent.  The effect of this
restriction of the number of symbols is not very serious.  It is always 
possible to use sequences of symbols in the place of single symbols.
Thus an Arabic numeral such as 17 or 999999999999 is normally treated
as a single symbol.

"Similarly, in any European language words are treated as single symbols
(Chinese however, attempts to have an enumerable infinity of symbols).
The differences from our point of view between the single and compound
symbols is that the compound symbols, if they are too lengthy, cannot
be observed at one glance.  This is in accord with experience.  We
cannot tell at a glance whether 999999999999999 and 9999999999999999
are the same."


These passages led me to suggest that what we want to do with neural 
networks is to mechanize perception, not simply to build faster computers.
(Though that is a desirable goal in its own right.)
Please note that it is Turing claiming Chinese "attempts" to have an
enumerable infinity of symbols.  I am ignorant of Chinese.  At some point,
with an increasing number of symbols, all members of an alphabet cannot be
recognized at-a-glance.  Or, looking at it another way, if you presume
an infinity of symbols upon which you are operating, you are not computing.

This is also the intuitive reason I claim ambiguity resolution 
is not computable.  I think of ambiguity resolution as the
general case of "object recognition" and "problem formulation." 
Imagine a vague scene or situation not already described by a finite
enumeration of the objects in it and their relationships, etc.
Such a vague scene is equivalent, in Turing's sense, to supposing
an infinite number of things in the scene, which you are going to reduce
to a finite number of options from which to choose.  Since you are
supposing an infinite alphabet (or the equivalent "vague" scene) technically,
you are not computing.  

By Turing's above remarks, I think by his definition, Chinese cannot
succeed at having an enumerable infinity of symbols.  It can only
"attempt" to have them.  Unless you "go down a level" and consider
"things that make up" Chinese symbols "the symbols."  Then, there
must be a finite number of them.  Does anyone know if this is true
about Chinese?  It would seem that even in English it does not apply to
orthography, though it apparently does to letters, 
since we use in hand-writing no fixed "alphabet" of strokes, etc.  Well, 
I meant only to introduce Turing's words, forgive me for going on.

Regards,

Peter Berke