Hal Finney wrote:
>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
I was being a little sloppy...it's true that a non-halting program would not
be equivalent to a computable function, but I think we can at least say that
the set of all computable functions is a *subset* of the set of all
programs. As for the programs taking input or not, if you look at the set of
all programs operating on finite input strings, each one of these can be
emulated by a program which has no input string (the input string is built
into the design of the program). So for any computable function, there
should be some member of the set of all halting programs being run by the
dovetailer that gives the same output as the function, no?
Jesse
--~--~---------~--~----~------------~-------~--~----~
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 Wed May 31 2006 - 20:05:17 PDT