[FOM] computing over the reals
John McCarthy
jmc at steam.Stanford.EDU
Tue Feb 21 17:07:41 EST 2006
This reminds me of a dispute in the Algol 60 committee in 1960
January. I and some others advocated real number Algol with the
implementations on computers of various word length as approximations.
Ad van Wijngarden insisted that Algol be defined in terms of
operations on bit strings.
> Date: Tue, 21 Feb 2006 02:24:38 -0500 (EST)
> From: Alasdair Urquhart <urquhart at cs.toronto.edu>
> X-X-Sender: urquhart at dvp.cs
> X-Scanned-By: MIMEDefang 2.49 on 128.122.80.107
> X-Scanned-By: MIMEDefang 2.49 on 128.122.80.78
> X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-2.0.1 (mx.cims.nyu.edu [127.0.0.1]); Tue, 21 Feb 2006 15:11:53 -0500 (EST)
> X-Greylist: Default is to whitelist mail, not delayed by milter-greylist-2.0.1
> (mx.cims.nyu.edu [128.122.80.78]);
> Tue, 21 Feb 2006 02:24:44 -0500 (EST)
> X-Mailman-Approved-At: Tue, 21 Feb 2006 15:11:22 -0500
> X-BeenThere: fom at cs.nyu.edu
> X-Mailman-Version: 2.1.6
> Precedence: list
> Reply-To: Foundations of Mathematics <fom at cs.nyu.edu>
> List-Id: Foundations of Mathematics <fom.cs.nyu.edu>
> List-Unsubscribe: <http://www.cs.nyu.edu/mailman/listinfo/fom>,
> <mailto:fom-request at cs.nyu.edu?subject=unsubscribe>
> List-Archive: </pipermail/fom>
> List-Post: <mailto:fom at cs.nyu.edu>
> List-Help: <mailto:fom-request at cs.nyu.edu?subject=help>
> List-Subscribe: <http://www.cs.nyu.edu/mailman/listinfo/fom>,
> <mailto:fom-request at cs.nyu.edu?subject=subscribe>
> Received-SPF: none (cs-smtp-3.Stanford.EDU: 128.122.80.107 is neither permitted nor denied by domain of cs.nyu.edu) client-ip=128.122.80.107; envelope-from=fom-bounces at cs.nyu.edu; helo=mx.cims.nyu.edu;
> X-Spam-Status: No, score=-4.9
> X-Spam-Checker-Version: SpamAssassin 3.0.4-cs-csdcf (2005-06-05) on cs-smtp-3.Stanford.EDU
> X-Scan-Signature: b64bce576883819501cf77c9371f4538
>
>
>
> > I have difficulty locating the notion of computation behind the Blum
> > et al model. Blum lectured on it at U of Chicago a few years ago and
> > spoke as though there were two ideas of computation, one starting
> > with the *assumption* of discreteness and the other with continuity.
> > But Turing's analysis didn't *start* with the assumption of
> > discreteness. As I understand him, he began simply with the aim of
> > analyzing the notion of (human) mechanical computation, and
> > discreteness was a result of his analysis. (As I recall, he derived
> > it from the requirement that states be readable.)
>
> If I understand the Blum et al model correctly, it can perhaps
> most easily be understood as a model involving an imaginary
> calculator with infinite precision. In other words, the data
> structures are arbitrary real numbers. This might sound
> unreasonable, since our computational practice involves only
> rational approximations (hence the bit model), but on the
> other hand, if you think of the classical theory of
> geometrical constructions, it seems more sensible,
> since these constructions also are thought of as operating
> on arbitrary real numbers.
>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
More information about the FOM
mailing list