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
a sense of what it was really about.
The Universal Dovetailer is a program which generates and executes all
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
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
Russell Standish attributes it (wrongly) to Schmidhuber in his book.
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
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