Jesse Mazer writes:
> The dovetailer is only supposed to generate all *computable* functions
> though, correct? And the diagonalization of the (countable) set of all
> computable functions would not itself be computable.
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.
These programs differ from functions in two ways. First, programs may
never halt and hence may produce no fixed output, while functions must
have a well defined result. And second, these programs take no inputs,
while functions should have at least one input variable.
What do you understand a dovetailer to be, in the context of computable
functions?
Hal Finney
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
Received on Tue May 30 2006 - 19:26:49 PDT