tag:blogger.com,1999:blog-11295132.post1721695175856952435..comments2015-02-26T21:20:49.361-08:00Comments on A Neighborhood of Infinity: What does topology have to do with computability? Reloaded.Dan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-11295132.post-31134478616434181142008-03-06T09:19:00.000-08:002008-03-06T09:19:00.000-08:00Sorry, Peter, I didn't mean to show you up as the ...Sorry, Peter, I didn't mean to show you up as the class dunce. Dan (sigpfe) and Alex are presenting elementary material in a tutorial fashion that is 20-30 years old. My interjections from the back of the classroom are just meant to point out how this connects with more contemporary and advanced ideas. The URL above is my home page, for a change.Paul Taylorhttp://www.paultaylor.eunoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-55711340816165266122008-03-06T04:16:00.000-08:002008-03-06T04:16:00.000-08:00Shouldn't "the observable sets are {}, {⊤} a...Shouldn't "the observable sets are {}, {⊤} and {{}, ⊤}" be "the observable sets are {}, {⊤} and {⊤,⊥}"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-73456941565215416022008-03-06T04:14:00.000-08:002008-03-06T04:14:00.000-08:00Shouldn't "the observable sets are {}, {⊤} a...Shouldn't "the observable sets are {}, {⊤} and {{}, ⊤}" be "the observable sets are {}, {⊤} and {⊤,⊥}"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-49108571795680644652008-03-04T20:19:00.000-08:002008-03-04T20:19:00.000-08:00Paul: Sorry, I am not a toplogist of any stripe wh...Paul: Sorry, I am not a toplogist of any stripe whatsoever, so far be it for me to argue with you.<BR/><BR/>To clarify what I meant: in the pointed-CPO semantics that are occupying my brain at the moment, the Hausdorff topology is not interesting (according to Alex Simpson, lecture notes #3, bottom of p3). I drew the conclusion, without thinking too much harder, that for the traditional notions of computation (e.g. over the natural numbers, not the exact reals) the Hausdorff spaces were not interesting. By all means correct me if that's wrong.<BR/><BR/>In any case I wanted to draw attention to those lecture notes, which are a nice (formal) complement to sigfpe's post.Peterhttp://peteg.org/noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-19684266011298207212008-03-04T00:32:00.000-08:002008-03-04T00:32:00.000-08:00The analogy between observability and open sets, w...The analogy between observability and open sets, whilst nicely treated in Steven Vickers' book, pre-dates his involvement in the subject. Michael Smyth played a large part in it, though the names Abramsky, Dijkstra, Floyd, Hoare, Plotkin and Scott also come to mind.<BR/><BR/>Alex Simpson's "lecture 3" covers similar ground to this blog, but I see no mention of Hausdorffness in it. Certainly cpos (with _|_) are not Hausdoff, except trivially.<BR/><BR/>However, a space X is discrete or Hausdorff iff the diagonal X subset XxX is respectively open or closed. In these cases, there is a corresponding map to the Sierpinski space. For a discrete space it is called = (equality) and for a Hausdorff space # (inequality or apartness).<BR/><BR/>In particular, the real line is Hausdorff but not discrete. Does Peter think that this is not an important space? My paper (click on my name above). is about this space.Paul Taylorhttp://www.paultaylor.eu/ASD/lamcranoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-30915074713620404692008-03-03T21:19:00.000-08:002008-03-03T21:19:00.000-08:00Thanks for an interesting post. To nitpick, you sa...Thanks for an interesting post. To nitpick, you say:<BR/><BR/>"At this point you can turn the tools of topology to computer science and you find that terms like discrete, Hausdorff and compact, which are all standard terms from topology defined inn terms of open sets, all have computational content."<BR/><BR/>Apparently the Hausdorff space is not very interesting; take a look at <A HREF="http://www.dcs.ed.ac.uk/home/als/Teaching/MSfS/" REL="nofollow">Alex Simpson's lecture notes</A> (l3.pdf).Peterhttp://peteg.org/noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-22376416516536202392008-03-02T20:14:00.000-08:002008-03-02T20:14:00.000-08:00Anonymous,That's kind of the point. There's a long...Anonymous,<BR/><BR/>That's kind of the point. There's a long mathematical tradition of reasoning about about functions and it'd be nice to use that in programming. 'Functions' in imperative programming languages aren't functions so it's hard to apply the method there. In 'functional' programming, the things we call 'functions' still aren't quite functions in the usual sense, for the reasons you point out. But they look like something so similar to mathematical functions much of the time, so it'd be nice if there were a fix. Well this is one fix: reinterpret types as topological spaces then 'functions' are continuous functions, even when the underlying algorithm doesn't terminate. So even though we're really talking about algorithms, we can reason about them in a functional way.<BR/><BR/>You could even use a 'total' programming language where every 'function' is guaranteed to terminate. When that's the case, 'functions' become functions.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-20544028581075724052008-03-02T19:46:00.000-08:002008-03-02T19:46:00.000-08:00But not all functions terminate in a finite time, ...<I>But not all functions terminate in a finite time, so they arenâ€™t quite like ordinary functions after all.</I><BR/><BR/>I hardly know enough to be dangerous, let alone reliable, on this topic, but it seems to me like you are confusung functions with algorithms. A certain algorithm used to compute a result in a particular way may not terminate, but mathematically speaking, it would be possible, for example, to provide answers by pulling the values out of a prebuilt map of very large size.<BR/><BR/>It is not about terminating/nonterminating, but rather that the machine must be incomplete and finite so there are certain functions for which it must answer "I don't know". Non-termination is one way of doing that if it cannot be better programmed to avoid situations beyond the limits of the computer (like even simply terminating after a maximum time limit and returning the I don't know answer.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-20850120474126623132008-03-02T19:18:00.000-08:002008-03-02T19:18:00.000-08:00Every link's broken? Either I've had a complete me...Every link's broken? Either I've had a complete mental breakdown and forgotten the most basic HTML, or blogger.com is acting up.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-5982047321894373692008-03-02T18:12:00.000-08:002008-03-02T18:12:00.000-08:00The links to the paper by Escardo and Paul Taylor ...The links to the paper by Escardo and Paul Taylor aren't working but apart from that, thanks for the great post. I'm really enjoying your expositions.Mark Reidhttp://mark.reid.namenoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-27225149659759615792008-03-02T17:56:00.000-08:002008-03-02T17:56:00.000-08:00Hi! The link to your previous post is broken (some...Hi! The link to your previous post is broken (some unwanted characters got into the href).<BR/><BR/>Thanks for the introduction to topology. It was so "elegant", linking automaton theory (the basics of it) with topology. I'm very much interested in maths, but most of these "modern" theories (like topology, category theory, etc..) don't really have any good introduction. (At least I don't know of any.)PAStheLoDhttp://www.blogger.com/profile/13210315686132933148noreply@blogger.com