tag:blogger.com,1999:blog-11295132.post7183970238574966365..comments2014-09-23T07:24:59.513-07:00Comments on A Neighborhood of Infinity: What does topology have to do with computability?Dan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-11295132.post-14223330572084617502014-03-17T06:24:23.166-07:002014-03-17T06:24:23.166-07:00See this tutorial and this book. I think there i...See <a href="http://link.springer.com/chapter/10.1007%2F978-0-387-68546-5_18" rel="nofollow"> this tutorial</a> and <a href="http://www.fernuni-hagen.de/weihrauch/index_data/book.html" rel="nofollow"> this book</a>. I think there is a need to being together various streams on real computation, including EGC, BSS model, etc.rsjhttp://www.blogger.com/profile/10061019077847967684noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-69934002781480850392009-11-08T12:26:09.410-08:002009-11-08T12:26:09.410-08:00Dana Scott's work used continuity as an approx...Dana Scott's work used continuity as an approximation for computability, but in the context of the lambda calculus.<br /><br />Is there a relationship here?matthttp://matt.might.net/noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-51577380819806832732008-02-01T00:47:00.000-08:002008-02-01T00:47:00.000-08:00I am not an expert on computability, but as a math...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 ε <I>and on x</I>. When you write "<I>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 ε</I>" it sounds as if there is a δ, depending on ε, valid for all possible arguments x. This would be <I>uniform continuity</I> 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 <I>any</I> possible argument x.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-6935675393934425102008-01-07T06:37:00.000-08:002008-01-07T06:37:00.000-08:00Interesting exercise. Yet, if I understand what yo...Interesting exercise. <BR/><BR/>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". <BR/><BR/>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.<BR/><BR/>I think I'll stick with symbolic computation whenever I want to perform exact operations on real numbers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-19252669168734111902008-01-07T04:28:00.000-08:002008-01-07T04:28:00.000-08:00Do you know Girard's work on Geometry of Interacti...Do you know Girard's work on Geometry of Interaction ?<BR/><BR/>http://iml.univ-mrs.fr/~girard/Articles.html<BR/><BR/>Sadly, many of his most interesting (and fun !) introductory papers are only available in french.<BR/><BR/>« To find an appropriate framework to formulate theorems on computation is one of Geometry of Interaction's ultimate goals. »<BR/><BR/>(rough translation from « Titres et travaux »)Interested readernoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-88585028358225199492008-01-07T04:10:00.000-08:002008-01-07T04:10:00.000-08:00There isn't a canonical reference for computabilit...There isn't a <I>canonical</I> reference for computability and topology,<BR/>as there are several different disciplines that have come to these questions<BR/>from different directions. Fortunately, they have recently started talking<BR/>to each other, and the membership list of <A HREF="http://www.cca-net.de" REL="nofollow">CCA</A><BR/>is perhaps the place to start looking for the most general perspective.<BR/><BR/>Your comment about equality-testing is not quite accurate. Whilst there is<BR/>no program that, when given representations of two real numbers, will<BR/><I>always terminate</I> with a (correct) report that they are equal or not,<BR/>one can program a test for <I>in</I>equality, ie which will terminate with<BR/>a positive report if the numbers are different, but possibly diverge if<BR/>they are equal. <BR/><BR/>This main difficulty in grasping this derives from the prejudices of<BR/>classical mathematics: that negation is a symmetry between truth and falsity,<BR/>and that all topological spaces are Hausdorff. The non-Hausdorff Scott<BR/>topology plays a key role in this subject, just as it does in the<BR/>denotational semantics of programming languages to which I believe you have<BR/>referred in earlier blogs.<BR/><BR/>The work of mine to which Derek Elkins refers above is called<BR/><A HREF="http://www.PaulTaylor.EU/ASD" REL="nofollow"><I>AbstractStone Duality</I></A>.<BR/>The main paper that begins to apply it to real analysis is called<BR/><I>A lambda calculus for real analysis</I> and is available from the<BR/>web page. However, I am still working on rewriting the introduction<BR/>to the calculus in sections 3-8 in order to give "need to know" accounts<BR/>of such topics as the Scott topology and lambda calculus, so please<BR/>re-visit later for more news.Paul Taylorwww.paultaylor.eunoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-7973171641051326492008-01-07T03:37:00.000-08:002008-01-07T03:37:00.000-08:00Martin Escardo: Synthetic topologyof data types an...<A HREF="http://www.cs.bham.ac.uk/~mhe/" REL="nofollow">Martin Escardo</A>: <BR/><A HREF="http://www.cs.bham.ac.uk/~mhe/papers/entcs87.pdf" REL="nofollow">Synthetic topology<BR/>of data types and classical spaces</A>szgygnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-17105892688633971832008-01-07T02:51:00.001-08:002008-01-07T02:51:00.001-08:00Of course, the myth part is only partly myth since...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?apfelmusnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-64406374193875183932008-01-07T02:51:00.000-08:002008-01-07T02:51:00.000-08:00In fact, there is no way to implement exact real a...In fact, there is no way to implement exact real arithmetic so that equality is decidable.migmithttp://www.blogger.com/profile/06981055611018991476noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-82094191954055775742008-01-07T00:14:00.000-08:002008-01-07T00:14:00.000-08:00Another great post!I think I would have like to se...Another great post!<BR/><BR/>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.<BR/><BR/>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/<BR/><BR/>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!gennethhttp://www.blogger.com/profile/02376760053977600605noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-91569021276013472292008-01-06T22:06:00.000-08:002008-01-06T22:06:00.000-08:00Not really to do with main the thrust of your piec...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?Longhttp://www.blogger.com/profile/15201888766976517347noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-39643477193739315002008-01-06T20:51:00.000-08:002008-01-06T20:51:00.000-08:00milos,Equality testing is discontinuous so it can'...milos,<BR/><BR/>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.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-14371339200477456992008-01-06T20:45:00.000-08:002008-01-06T20:45:00.000-08:00I thought that f(x = 1/x is a counter-example beca...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.Milosnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-60762682674873628202008-01-06T18:58:00.000-08:002008-01-06T18:58:00.000-08:00I don't know if you've looked at it before, but if...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 <A HREF="http://www.monad.me.uk/ASD" REL="nofollow"/>. This is closely related to synthetic topology.Derek Elkinsnoreply@blogger.com