"The study of fixed points has been at the foundation of algorithms"
A bit of a windy road: starting, as usual, with the personal frame of reference.... PyGeo's current implementation supports the exploration of the geometry of complex numbers, and therefore speaks Mobius transformations. http://pygeo.sourceforge.net now has a pretty picture of a simple recursive transformation of 4 circles on the unit sphere (...thanks to __iter__ the ability to recursively transform any arbitrary set of geometric objects is now built-in to PyGeo). My current exploration (current as in today) is finding the mechanism to build a Mobius transformation that would be based (in part) on it's (pickable and movable) fixed points - of which a Mobius transformation has 2, which may coincide, or be located inconveniently - e.g. at infinity. Which has me stepping into the math of the fixed points of a function - it being trivial to find the fixed points, given the Mobius transformation matrix, but less trivial (from where I am sitting at the moment) to build the transformation from fixed point information. So I am struggling and researching some. In the course of which I come across this definition of "Fixed Point" in a programming glossary, @ http://carbon.cudenver.edu/~hgreenbe/glossary/second.php?page=F.html Of a function, f:X-->X, f(x)=x. Of a point-to-set map, F:X-->2^X, x is in F(x). The study of fixed points has been at the foundation of algorithms <http://carbon.cudenver.edu/%7Ehgreenbe/glossary/second.php?page=A.html#Algor...>. Having discussed here my growing interest in some study of algorithmics, but not getting there yet, but pursuing something that as far as I am aware is unconnected to such study, and then finding this statement indicating there is more of a connection - perhaps - than I had understood, is to me interesting. I have thought of "fixed point" (in programming) as connected to/opposed to "floating point", not as something directly connected to the concept of "f(x)=x" The statement above seems to be telling me otherwise. Guess I am fishing for some exposition on the statement that the "The study of fixed points has been at the foundation of algorithms" Art
Arthur wrote:
I have thought of "fixed point" (in programming) as connected to/opposed to "floating point", not as something directly connected to the concept of "f(x)=x"
The statement above seems to be telling me otherwise. Guess I am fishing for some exposition on the statement that the "The study of fixed points has been at the foundation of algorithms"
Well, in fact both meanings of "fixed point" are used, seldom by the same person. I expect Knuth is in that small group that uses both meanings regularly (since his basic training was all mathematics). Look to the "functional programming" people for examination of the whole idea of fixed points of functions (Bird & Wadler is a standard F.P. text). --Scott David Daniels Scott.Daniels@Acm.Org
Scott David Daniels wrote:
Well, in fact both meanings of "fixed point" are used, seldom by the same person. I expect Knuth is in that small group that uses both meanings regularly (since his basic training was all mathematics). Look to the "functional programming" people for examination of the whole idea of fixed points of functions (Bird & Wadler is a standard F.P. text).
thanks for the clarification as to terminology. re: "The study of fixed points has been at the foundation of algorithms" I guess what I am asking further is whether the statement is simply referencing the development of algorithms for solving the mathematical question of the fixed points of a function, in the context of mathematical programming where that particular mathematical problem might happen to present itself- or is there some implication that the problem of f(x) = x is one that has more general implications in algorithmics as a distinct area of study. .. or am I asking a question that is itself too round-about to have an answer of the kind of am looking for? ;) Art
re: "The study of fixed points has been at the foundation of algorithms"
I guess what I am asking further is whether the statement is simply referencing the development of algorithms for solving the mathematical question of the fixed points of a function, in the context of mathematical programming where that particular mathematical problem might happen to present itself- or is there some implication that the problem of f(x) = x is one that has more general implications in algorithmics as a distinct area of study. I think the answer is yes (there are such implications), and that those implications show up in the functional programming world (where they
Arthur wrote: like to think of everything as constants and pure functions). The places it shows up (if I understand correctly) have a lot to do with compilation and binding functions into environments where the functions themselves are a part of that environment. But this is simply a suspicion, I can't say that I've delved too deeply into this area. I suspect the other way into this is Category Theory, an area I am afraid I under-appreciate (though some say it is just because I don't "get it").
.. or am I asking a question that is itself too round-about to have an answer of the kind of am looking for? ;)
The above is as much as I can give you. You may get more from abstract algebra people. --Scott David Daniels Scott.Daniels@Acm.Org
Scott David Daniels wrote:
I suspect the other way into this is Category Theory, an area I am afraid I under-appreciate (though some say it is just because I don't "get it").
Read through this explanation of Category Theory. http://plato.stanford.edu/entries/category-theory/ While not being in a position to approach the concepts described in any serious way, I can - I think - at least appreciate that the ghost of Felix Klein hovers about. The discussion I am having with myself here has to do with modernism and education. My concept of educational reform has much to do with the ghost of Felix Klein, as well...in perceiving a need to have even elementary levels of instruction better informed by the kinds of modernist abstractions with which categories like Category Theory grapple. Whereas I don't think that, in general, technology has any (necessarily) important role to play in such reform - I do think that specific tools - Python certainly among them (with or without my efforts to contribute) can, and probably will. Art.
Arthur wrote:
Guess I am fishing for some exposition on the statement that the
"The study of fixed points has been at the foundation of algorithms"
Very deep in the foundations of algorithms are the foundations of computer science semantics: http://en.wikipedia.org/wiki/Denotational_semantics An other area where I've been exposed ot fixed points is concurrent constraint programming where constraint propagators are applied to a computation space until a fixed point is reached (see for instance http://www.gecode.org/ for a Open source implementation). HTH, -- Grégoire Dooms PS: Where is the connection with education with/about Python ?
Grégoire Dooms wrote:
Very deep in the foundations of algorithms are the foundations of computer science semantics: http://en.wikipedia.org/wiki/Denotational_semantics
An other area where I've been exposed ot fixed points is concurrent constraint programming where constraint propagators are applied to a computation space until a fixed point is reached (see for instance http://www.gecode.org/ for a Open source implementation).
I see your familiarity with the gecode project and its concepts are more than casual ;): http://cpgraph.info.ucl.ac.be/
HTH,
Helps - in the sense of giving me some impression of the meaning of the behind the assertion, realizing that an "impression" is all I have the prerequisites to achieve.
-- Grégoire Dooms
PS: Where is the connection with education with/about Python ?
Maybe little. Though I have certainly been *more* irrelevant than this. As I suspect you are aware. Obviously there will be more relevance once you do the Python bindings to CP(Graph) ;). I do flirt with the idea of having nothing to say here - which will certainly avoid any possibility of my raising irrelevancies. Is PyGeo relevant to education with/about Python? I am not quite ready yet, but after the next release I will be willing to argue that it is more than relevant - that it is significant. Knowing that I might have lost objectivity, but also knowing what I know. Art Art
participants (3)
-
Arthur -
Grégoire Dooms -
Scott David Daniels