Le Mercredi 31 Mai 2006 00:21, Hal Finney a écrit :
> The dovetailer I know does not seem relevant to this discussion about
> functions. It generates programs, not functions. For example, it
> generates all 1 bit programs and runs each for one cycle; then generates
> all 2 bit programs and runs each for 2 cycles; then generates all 3
> bit programs and runs each for 3 cycles; and so on indefinitely. (This
> assumes that the 3 bit programs include all 2- and 1-bit programs, etc.)
> In this way all programs get run with an arbitrary number of cycles.
In fact it is relevant because of this :
- Bruno showed us that it is not possible to write a program that will list
sequentially all growing functions.
- But the dovetailer will not do it too, but what it will do instead is
generate all program that list "all" growing functions.
So it will first generate the programme that create the first sequence and
also the pogram that create the sequence composed of diagonalisation of the
first and so on... it can because program are countable because they are
mapped to N. So the dovetailer will not list all the growing function but
will generate (and execute in dovetailing) the infinite sequence of programs
that generate all of them.
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To post to this group, send email to firstname.lastname@example.org
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at