- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Brent Meeker <meekerdb.domain.name.hidden>

Date: Thu, 10 May 2007 17:19:54 -0700

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

Date: Thu, 10 May 2007 17:19:54 -0700

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:

--~--~---------~--~----~------------~-------~--~----~

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:14 PST
*