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 [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---
