Le 19-janv.-06, à 02:45, Russell Standish a écrit :
> On Mon, Jan 16, 2006 at 04:32:15PM +0100, Bruno Marchal wrote:
>>
>> Le 15-janv.-06, ? 19:04, Benjamin Udell a ?crit :
>>
>>> The "dovetailer" keeps sounding like a powerful idea. I do remember
>>> that it has often been mentioned here, but somehow I failed to pick
>>> up
>>> a sense of what it was really about.
>>
>>
>> The Universal Dovetailer is a program which generates and executes all
>> programs.
>> Its existence is a non trivial consequence of Church thesis. Please
>> recall me to explain this in detail in one or two weeks.
>> The necessity to dovetail (that is to run successiveley on the initial
>> segement of the execution never waiting any programs stop is due to
>> the
>> fact that the always defined programs cannot be generated mechanically
>> (this can be done in the case of all programs).
>> Actually I have already explain this on the list (in 2001) but the
>> escribe archive seems no more working again, and the new archive seems
>> not go enough backward in time.
>> The first published paper where I define it, is "Mechanism ans
>> Personal
>> Identity" paper:
>> http://iridia.ulb.ac.be/~marchal/publications/M&PI_15-MAI-91.pdf
>> Russell Standish attributes it (wrongly) to Schmidhuber in his book.
>> My
>
> To be precise I do not attribute it to Schmidhuber, but I can see why
> you came to that conclusion. I will be revising this section to make
> this point clear in the final version of my book. The dovetailer
> algorithm is
> certainly well known, and not apparently attributable to anyone, and
> at the time when I wrote that part of ToN, I was unaware that the
> specific application of the dovetailer to computing all possible
> programs is your idea.
Yes, the key was to realize that church's thesis allows *universal*
dovetailing, and forces the "dovetailing" part: i.e. there is no
universal machine capable of running all programs without dovetailing.
For exemple, there are no universal dovetailer for the total computable
functions. See the diagonalization posts (when available).
> My mistake actually is using the qualified name
> "universal dovetailer" to describe a dovetailer generating all
> possible strings (Schmidhuber's work), when the universal dovetailer
> actually runs the programs too. I do not use the qualified name in
> "Why Occam's razor".
But a program generating all the strings does not need to dovetail at
all. The expression "dovetailing on all strings" is quite confusing. I
think it would be preferable to keep Schmidhuber terminology when you
describe his work, which I have already described as interesting
"constructive physics", but not entirely relevant when searching a
TOE, as the philosophical remarks ending his first everything paper
illustrated, and as it has been confirmed when he dismissed the 1/3
distinction.
Bruno
http://iridia.ulb.ac.be/~marchal/
Received on Thu Jan 19 2006 - 09:25:15 PST