Xref: utzoo comp.theory:1747 comp.lang.functional:714
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!rex!caesar!fs
From: fs@caesar.cs.tulane.edu (Frank Silbermann)
Newsgroups: comp.theory,comp.lang.functional
Subject: Re: do computers believe in real numbers?
Message-ID: <6878@rex.cs.tulane.edu>
Date: 2 Apr 91 16:20:44 GMT
References: <7197@munnari.oz.au> <91090.154205NN1@awiwuw11.wu-wien.ac.at>
Sender: news@rex.cs.tulane.edu
Organization: Computer Science Dept., Tulane Univ., New Orleans, LA
Lines: 58


In article <91090.154205NN1@awiwuw11.wu-wien.ac.at> NN1@awiwuw11.wu-wien.ac.at writes:
>	there are several equivalent ways to define the notion
>	of computable real number.
>
>	A number a is computable, if the n-th digit of a is
>	a recursive function of n, or, equivalently,
>	if the set of all rational numbers <= a
>	is recursive (assuming some coding scheme for rational numbers).
>	...
>	Now for the more practical quesiton raised by A.E. Thomson,
>	how real numbers should indeed be represented on a computer,
>	so that at any stage one can get as many digits as requested,
>	...
>Heinrich Rolletschek
>k310670@AEARN

One difficulty with this definition would be the problem
of asking for the first 5 mantissa digits of an expression
that simplifies to:
	                                              _
	0.099999999999999999999999999999999999999999999 (9's forever).

Clearly, the result equals 0.1 exactly,
so the first five mantissa digits OUGHT to be 0.10000,
yet, most naive systems would report 0.09999 !!!
If computation with real numbers is to be "computable,"
we need a more lenient requirement than
"ability to compute any single digit in a finite amount of time,"
and we need a more lenient notion of approximation than
"truncation of the digits."

The problem is that, in mathematics, equality is defined
via convergence of infinite chains of approximations,
and _not_ by the ability to produce identical normal forms.

[MORAL:	This should be a lesson to those who believe
	functional programming should be based on some
	arbitrary lambda calculus or rewriting system.
	It should be based on domain theory,
	which takes into account the existence of
	infinite chains of approximation.

	Also, consider the fact that mathematics
	has not given us any single notation
	suitable for expressing _every possible_
	computable function over the reals (or even the rationals).
	This may be a hint that we should not worry too much
	if our functional programming languages are not "fully abstract,"
	that our domain contains objects which cannot be denoted
	by any expression in our language.
]
-- 
	Frank Silbermann	fs@cs.tulane.edu
	Tulane University	New Orleans, Louisiana  USA
--
	Frank Silbermann	fs@cs.tulane.edu
	Tulane University	New Orleans, Louisiana  USA