Comments on A Neighborhood of Infinity: What does topology have to do with computability?

Dana Scott's work used continuity as an approx...

2009-11-08T12:26:09.410-08:00

Dana Scott's work used continuity as an approximation for computability, but in the context of the lambda calculus.

Is there a relationship here?

I am not an expert on computability, but as a math...

2008-02-01T00:47:00.000-08:00

I am not an expert on computability, but as a mathematician I think you have to be careful with your definition of continuity. Cauchy's definition is of course correct, but note that δ might depend on ε and on x. When you write "f is continuous if for any ε there is a δ such that even if the argument, x, to f has an error of δ, f(x) still has an accuracy of ε" it sounds as if there is a δ, depending on ε, valid for all possible arguments x. This would be uniform continuity and is a stronger property than continuity. In terms of computability, continuity would mean you have to know only a finite number of digits of x to return f(x) within some margin of error, but there is no upper bound over all possible arguments x. Uniform continuity on the other hand would mean that there is a uniform upper bound of digits you have to examine for any possible argument x.

Interesting exercise.

Yet, if I understand...

2008-01-07T06:37:00.000-08:00

Interesting exercise.

Yet, if I understand what you say, I find that your 2nd "non-intuitive" result would be much more intuitively stated as "using this representation, only continuous functions can be well-defined".

This stems from the fact that you fine-tune your representation to handle well the approximation of reals by a sequence of rationals (thus making your representation apt to handle the definition of continuity), but not any other "interesting" aspects of real numbers and functions of a real variable.

I think I'll stick with symbolic computation whenever I want to perform exact operations on real numbers.

Do you know Girard's work on Geometry of Interacti...

2008-01-07T04:28:00.000-08:00

Do you know Girard's work on Geometry of Interaction ?

http://iml.univ-mrs.fr/~girard/Articles.html

Sadly, many of his most interesting (and fun !) introductory papers are only available in french.

« To find an appropriate framework to formulate theorems on computation is one of Geometry of Interaction's ultimate goals. »

(rough translation from « Titres et travaux »)

There isn't a canonical reference for compu...

2008-01-07T04:10:00.000-08:00

There isn't a canonical reference for computability and topology,
as there are several different disciplines that have come to these questions
from different directions. Fortunately, they have recently started talking
to each other, and the membership list of CCA
is perhaps the place to start looking for the most general perspective.

Your comment about equality-testing is not quite accurate. Whilst there is
no program that, when given representations of two real numbers, will
always terminate with a (correct) report that they are equal or not,
one can program a test for inequality, ie which will terminate with
a positive report if the numbers are different, but possibly diverge if
they are equal.

This main difficulty in grasping this derives from the prejudices of
classical mathematics: that negation is a symmetry between truth and falsity,
and that all topological spaces are Hausdorff. The non-Hausdorff Scott
topology plays a key role in this subject, just as it does in the
denotational semantics of programming languages to which I believe you have
referred in earlier blogs.

The work of mine to which Derek Elkins refers above is called
AbstractStone Duality.
The main paper that begins to apply it to real analysis is called
A lambda calculus for real analysis and is available from the
web page. However, I am still working on rewriting the introduction
to the calculus in sections 3-8 in order to give "need to know" accounts
of such topics as the Scott topology and lambda calculus, so please
re-visit later for more news.

Martin Escardo:
Synthetic topology
of data types and classical spaces

Of course, the myth part is only partly myth since...

2008-01-07T02:51:00.001-08:00

Of course, the myth part is only partly myth since you can only represent all real numbers from intuitionistic logic on a computer. So, it's not quite the same as all real numbers from classical logic. Maybe it's a good idea to clarify this somewhere in your article?

In fact, there is no way to implement exact real a...

2008-01-07T02:51:00.000-08:00

In fact, there is no way to implement exact real arithmetic so that equality is decidable.

Another great post!

I think I would have li...

2008-01-07T00:14:00.000-08:00

Another great post!

I think I would have like to see a more detailed exposition of how the notion of equality splits into the more refined notions of "apartness", etc. We're essentially talking about the constructively defined reals -- something that been well-investigated in foundational maths, though rarely used.

RE the compactness and the searchability -- it comes down to the fact that campactness implies certain global properties follow from local ones: see http://terrytao.wordpress.com/2007/11/20/pcm-article-compactness-and-compactification/

Finally, you should probably say something about the fact that continuous in constructive analysis doesn't quite mean the same thing as usual -- for instance, it's still perfectly possible to define the unit-step function, except that it's now continuous!

Not really to do with main the thrust of your piec...

2008-01-06T22:06:00.000-08:00

Not really to do with main the thrust of your piece, and with the qualification that my math education is very limited... surely the first example you gave (1/3) which is rational would be simpler to represent as a quotient of two integers. If you then threw in a few 'well-known' non-rational reals (such as pi and e) as 'special' values which evaluate as lazy functions as required, you could have a simple and compact representation that can represent a subset of the reals that is adequate for a large number of real world problems, no?

milos,

Equality testing is discontinuous so...

2008-01-06T20:51:00.000-08:00

milos,

Equality testing is discontinuous so it can't be implemented. In fact, even for ordinary floating point numbers we know that equality testing is a dangerous thing to do. Nonetheless, despite the fact that something as simple as equality testing is impossible, we can still exactly implement a wide gamut of useful functions on exact reals: eg. sin, cos, exp, max, integrals, derivatives and so on.

I thought that f(x = 1/x is a counter-example beca...

2008-01-06T20:45:00.000-08:00

I thought that f(x = 1/x is a counter-example because it is discontinuous and computable... except there's a problem with zero. It's impossible to check in this representation if a number equals zero. So my attempt to disprove your result did not succeed.

I don't know if you've looked at it before, but if...

2008-01-06T18:58:00.000-08:00

I don't know if you've looked at it before, but if you haven't you definitely want to look at Paul Taylor's work on . This is closely related to synthetic topology.