Le 30-mai-06, à 19:13, Tom Caylor wrote :
>
>> From what you've said about dovetailing before, you don't have to have
> just a single sequence in order to dovetail. You can jump among
> multiple sequences. I have yet to understand how you could dovetail on
> something that is not effective. That seems to be where you're going.
> I guess we have to get to non-effective diagonalization first.
It is true that we can dovetail on multiple sequences, once we can
generate their codes, like all the sequence of growing computable
functions we have visited.
But none of them are universal.
Once I can name a sequence of growing function, and thus can program an
enumeration of their codes, I will be able to diagonalize it, showing
it was not universal.
---------------------------------------
Quentin Anciaux wrote:
> I think dovetailing is possible because the dovetailer only complete
> sequences
> at infinity. So when you construct the matrice on which you
> will "diagonalize", you are already diagonilizing it at the same time.
> Example: when you have the first number of the first growing function,
> you
> can also have the first number of the diagonalize function (by adding
> 1) and
> the first number of the diagonalize*diagonalize function and ... ad
> recursum.
> By dovetailing you execute in fact everything in "parallel" but all
> infinites
> sequences are only completed at infinity.
Same answer as the one for Tom. You can diagonalize only on the
transfinite sequences up to a nameable ordinal, and clearly this cannot
be closed for diagonalization. Even in the limit, the transfinite
construction will fail to name some computable growing function.
---------------------------------------
Hal Finney wrote:
> The dovetailer I know does not seem relevant to this discussion about
> functions. It generates programs, not functions.
So does our sequence of growing functions. They are given by the
programmable generation of the code of the growing function. The same
for the diagonalization.
> 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.
Close :)
---------------------------------
Quentin Anciaux comments on Hal Finney:
> 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.
...that will list sequentially all computable growing functions. Right.
> - But the dovetailer will not do it too, but what it will do instead is
> generate all program that list "all" growing functions.
Mmh...
> 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.
The shadow of the truth, but what you describe would still be
diagonalized out. (Or you are very unclear, to be sure, you will tell
me later ... or you will not tell me later :)
--------------------------
Jesse Mazer (on 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.
Key remark.
> 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).
Actually this is a key remark too, but it will be needed only later (I
recall that I am trying to explain a the missing link between computer
science and Smullyan's "heart of the Matter" in FU, after a question by
George Levy). This key remark is related to a simple but basic theorem
in computer science known as the SMN theorem, S for substitution and M
and N are parameter, and grosso modo the theorem says that you can
programs can be mechanically parametrized by freezing some of their
inputs.
> 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?
Yes. Do you see or know or guess the many consequences?
-------------------------------
George Levy wrote:
> To speak only for myself, I think I have a sufficient understanding of
> the thread. Essentially you have shown that one cannot form a set of
> all
> numbers/functions because given any set of numbers/functions it is
> always possible, using diagonalization, to generate new
> numbers/functions: the Plenitude is too large to be a set. This leads
> to
> a problem with the assumption of the existence of a Universal
> Dovetailer
> whose purpose is to generate all functions. I hope this summary is
> accurate.
It is a excellent summary, and even an anticipation, given that you
have replaced "sequence of computable growing functions" by just
"sequence of computable functions", and you are right (I will come back
on this soon).
We can say:
We cannot generate the set of (codes of) all computable functions.
And you are right, to dovetail on all computable functions we have to
be able to generate them all. So it looks like the DU is in peril!
But now, Church thesis tell us that Fortran (say) or Lisp, Java, Python
C++ ... can compute all computable functions, so that if you generate
all the fortran programs , you do generate all computable functions.
I can guess that Jesse and Hal can see that I am not saying something
contradictory here! But what happens really?
What will the diagonalization really prove? That Fn(n) = Fn(n)+1 so
that 0 = 1?
I let you think a little more about how much we will have to pay for
making Church thesis consistent. Of course there will be many rewards
too, including in fine some explanation of Smullyan's formula, which
will justify or explain the role of G and G* in the measure problem.
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
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 Sat Jun 03 2006 - 10:01:56 PDT