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, marc.geddes.domain.name.hidden 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.domain.name.hidden/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 everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Thu May 10 2007 - 20:20:08 PDT