Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!panda!talcott!harvard!seismo!mcvax!ukc!ptb
From: ptb@ukc.ac.uk (P.T.Breuer)
Newsgroups: net.ai,net.research
Subject: Re: String reduction
Message-ID: <1089@eagle.ukc.ac.uk>
Date: Thu, 24-Apr-86 07:32:50 EDT
Article-I.D.: eagle.1089
Posted: Thu Apr 24 07:32:50 1986
Date-Received: Sun, 27-Apr-86 07:22:25 EDT
References: <1031@eagle.ukc.ac.uk>
Reply-To: ptb@ukc.ukc.ac.uk (P.T.Breuer)
Organization: U of Kent at Canterbury, Canterbury, UK
Lines: 26
Xref: watmath net.ai:3428 net.research:463
Summary: some info on string reduction

In article <1031@eagle.ukc.ac.uk> sjl@ukc.ac.uk (S.J.Leviseur) writes:
>Does anybody have any references to articles on string reduction
>as a reduction technique for applicative languages (or anything
>else)? They seem to be almost impossible to find! Anything welcome.

John Horton Conway (the Prince of Games, memorably Life) of Cambridge
University (UK) Pure Maths. Dept. some years ago invented a computing
language that seems to me to proceed by Markovian string reduction.
 It is extremely sneaky at recognising substrings for substitution -
obviously the major cost in any such approach - and does this task
efficiently.  The trick is to make up your strings as the product of
integer primes instead of by alphanumeric concatenation. The production
rules of a program script consist of single fractions. To apply the
rules to an incoming 'string' you choose the first fraction in the script
that gives an integer result on multiplication with the integer 'string'
and take the result as the outgoing string, then go to the top of the
script with the new string and start again. The indices of prime powers
in the string serve as memory cells 'x'. The denominator of the fractions
serve as 'if x> ..' statements, with the numerators as 'then x=x+-..'
components. J.H.C.'s (the middle initial is to help him remain incognito)
interest was in the fact that the Godel numbers of programs written in this
language are easily calculable. Conway has written out on a single sheet of
paper the Godel number of the program that simulates any given program from its
Godel number. The G-No. of the prime number program is relatively short.
   I will intervene with J.C. to obtain more info, if requested.
           U.No.Hoo advises generic statement here.