Thanks, Bruno. I did know that - just forgot because it's been a long time. I don't think it's related to Brouwer's fixed point theorem though: that assumes a continuous topology. But I see what you mean by a fixed point of computation.
I'm now reading your elsevier paper. Brent Meeker Bruno Marchal wrote: > Brent, > > Let me try to illustrate a simple example of (relative) "meaning" fixed > point. > > A simple notion of meaning with machines or programs is given by the > set of input/output of the machine, or still more easily, the output > (in case the machine has no inputs). > > So for example meaning("fact-5") = 120, or meaning(CONSTANT-PI) = > 3,141592... > > A simple but important example of fixed point semantics is illustrated > by the problem of building a machine (or a program) which can duplicate > itself (relatively to the universal environment which supports the > machine/program). This is a program on which Descartes has worked all > his life without solving it---He was motivated in showing animals to be > both machine and self-duplicating entities. > > Let us suppose the environment is rich enough to sustain a simple > duplicator D. > So the environment can "execute" DA giving AA, and this for all machine > describable in that environment. Thus DB gives BB, DC gives CC. With > the semantics above: "DA gives AA" can be written as meaning(DA) = AA. > Of course here the meaning is given by the work of the universal > environment. > > Thus: > meaning(DA) = AA > meaning(DB) = BB > meaning(DC) = CC > > Now, the secret of self-duplication can be seen as a fixed point of the > function meaning. Given that Dx = xx for all x, we have, with x = D > itself: > > DD gives DD. (just substitute x by D), so that > > meaning(DD) = DD > > in this case the duplicator applied to itself gives a self-replicator, > which is indeed an example of fixed point "semantics". > > This simple idea is used ad nauseam in theoretical computer science, > and you have perhaps recognize a typical double diagonalization (Dx = > xx; DD = DD). For sure, denotational semantics based on topology single > out a lesser class of less "dangerous" (more controllable) fixed > points, but in our context all that is not necessary. Note also that > the universal environment does not need to be real; it could be > virtual, arithmetical, etc. > > Actually the technics behind the interview of the lobian universal > machine about *herself* is based on that very idea. > > I make the relation with the combinators in my elsevier paper: > > http://linkinghub.elsevier.com/retrieve/pii/S1571064505000242 > > People could perhaps tell me if they cannot access it freely, in that > case wait a version on my Web Page asap (I'm preparing myself to make > some change in my web page ...) > > Hope this helps, > > Bruno > > > > > Le 10-mai-07, à 11:02, Bruno Marchal a écrit : > >> >> Le 09-mai-07, à 18:50, Brent Meeker a écrit : >> >>> Bruno Marchal wrote: >>>> Le 09-mai-07, à 09:08, [EMAIL PROTECTED] a écrit : >>>> >>>>> Of course reality doesn't change. The question of map versus >>>>> territory is *not* an all or nothing >>>>> question. *sometimes* the map equals the territory. Most of the >>>>> time >>>>> it does not. >>>> >>>> This is an important point where I agree with Marc. With or without >>>> comp the necessity of distinguishing the map and the territory cannot >>>> be uniform, there are "meaning"-fixed-point, like when a map is >>>> embedded continuously in the territory (assuming some topology in the >>>> map and in the territory, this follows by a fixed point theorem by >>>> Brouwer, which today admits many interesting computational >>>> interpretations. >>>> >>>> Bruno >>> I don't think you can define a topology on "meaning" that will allow >>> the fixed point theorem to apply. >> >> >> A whole and rather important subfield of computer science is entirely >> based on that. It is know as denotational semantics. Most important >> contributions by Dana Scott. You can look on the web for "Scott >> domains". Or search with the keyword "fixed point semantics topology". >> Sometimes the topology is made implicit through the use of partial >> order and a notion of continuous function in between. Indeed the >> topological space used in this setting are not Hausdorff space, and are >> rather different from those used in geometry or analysis. >> >> A nice book is the one by Steve Vickers. It has provide me with >> supplementary reason to single out the Sigma_1 sentences as >> particularly important in the comp frame. (Topology via Logic, >> Cambridge University Press, 1989: >> http://www.amazon.ca/Topology-via-Logic-Steven-Vickers/dp/0521576512). >> >> Here are some links: >> >> http://www.ercim.org/publication/Ercim_News/enw50/schellekens.html >> >> http://www.cs.uiowa.edu/~slonnegr/plf/Book/Chapter10.pdf >> >> http://dimacs.rutgers.edu/Workshops/Lattices/slides/zhang.pdf >> >> I could say more in case I come back on the combinators. Cf: >> http://www.mail-archive.com/everything-list@eskimo.com/msg05958.html >> because there are strong relation between fixed point semantics, the >> paradoxical combinators, and the use of the (foirst and second) >> recursion theorem in theoretical computer science. But ok all that >> could become very technical of course. >> >> ... I thought you knew about fixed point semantics, perhaps I miss your >> point ... >> >> >> Bruno >> >> >> http://iridia.ulb.ac.be/~marchal/ >> >> > http://iridia.ulb.ac.be/~marchal/ > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---