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 - 09:34:53 PDT