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
-~----------~----~----~----~------~----~------~--~---

Reply via email to