Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!decwrl!ucbvax!CERC.UTEXAS.EDU!lynch
From: lynch@CERC.UTEXAS.EDU (Tom Lynch)
Newsgroups: comp.ai
Subject: Re: Artificial vs. ''real'' intelligence
Message-ID: <9007170054.AA10142@cerc.utexas.edu>
Date: 17 Jul 90 00:54:58 GMT
References: <599@dlogics.COM>
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: University of Texas at Austin
Lines: 65

To Net land,
   I have been trying to post this since early July, my apologizes
   for repeated material ...  If someone, by some strange hapenstance,
   sees this on comp.ai, please send me some mail.
  

   Penrose, and Searle have claimed that 'understanding' is not
Turing computable.  Anyway  the thought occurs to me that a
 random process may be important in machine learning .. and AI in general.

   An interesting phenomena in caches is that random replacement
has similar performance to least recently used.  This is well
known.  A friend mentioned a similar statistic in
knowledge bases -- random forgetting has similar performance to 
weighted least recently used forgetting!  

   More specifically, in the microprocessor instruction cache
problem there is a fast on chip instruction memory that fails to
contain a required instruction.  So, the required instruction
must be fetched from the slow external memory.  When the required
instruction arrives at microprocessor it must replace something
already in the cache.  A good replacement policy is to write the
new required instruction over the least recently used instruction
in the cache.  In other words, forget the instruction that hasn't
been used for the longest amount of time.  Randomly picking an
instruction to replace works just as well -- as was found and
implemented on some real microprocessors.  It is not the case
that replacement policies are just bad -- caches can achieve very
high hit rates with either random or least recently used
replacement!

   Apparently a similar phenomena exists in machine learning when
picking which rule in a knowledge base to forget, in order to
decrease search time.  Apparently some knowledge bases will work
more efficiently if they don't "know too much".  This sounds
intuitive - at some point search time must overwhelm the benefit
of knowing more.   When something new and important must replace
something already known I was surprised to hear that a popular
algorithm was the same as for instruction caches - throw out the
least recently used knowledge.  It was also surprising to learn
that RANDOM forgetting was almost as good as least recently used!

   It is very interesting that a random decision can be
better than many 'thoughtful' decisions - and as good as at least
one thoughtful decision!  I think this counter intuitive phenomena
may be important.  Perhaps the random forgetting and the
impreciseness of human cognition and learning may not just be
important - but be REQUIRED.

   Anyway wouldn't it be interesting to propose a turing machine
which has a randomly corrupted tape?  There would be some finite
probability that the information on the tape would change. 
Such a machine would not necessarily become random in its control
sequences, since the control unit could recover from a small
number of errors (although a small probability of failure would
exist).  I bet the machine would actually become 'smarter'. 
Would 'understanding' be computable by Penrose's argument with a
machine like this?  I am calling the machine a Political Machine
since it is corrupted :-).  Do you know how to go about finding
the language accepted by a Political Machine? 
                        
                -tom  lynch@cerc.utexas.edu