Bruno Marchal wrote:
> Le 15-juin-06, à 18:40, Tom Caylor a écrit :
>
> >
> >
> > Bruno Marchal wrote:
> >>
> >> Let us be specific (also for the others).
> >>
> >> Let us continue to write f1 f2 f3 f4 f5 f6 f7 ... for the sequence of
> >> total computable functions.
> >> Let us continue to write F1 F2 F3 F4 F5 F6 F7 ... for the sequence of
> >> partial computable functions (this includes the fi but in a hidden
> >> way).
> >> Let us write, as usual, g for the diagonalization of the fi, and G for
> >> the diagonalization of the Fi.
> >>
> >> So: g(n) = fn(n)+1; and G(n) = Fn(n)+1
> >>
> >> Now g cannot be computable, it would be total and it would belongs to
> >> the sequence fi, and thus there would be a number code k such that g =
> >> fk, and then fk(k) = fk(k)+1, and then 0 = 1 by substracting the well
> >> defined number fk(k). Obviously each fn(n) is computable, and adding
> >> one is computable, so only the bijection between the fi and N can be
> >> the source of uncomputability. Conclusion the bijection between i and
> >> fi, although well defined mathematically, is not computable.
> >>
> >
> > OK. You've shown by contradiction that g is not computable. I was
> > just trying to go back to the definition of computable to see which
> > part of the definition is violated. I think I overlooked the fact that
> > you alluded to the answer to this question when you said "...you just
> > will never been able to give me a finite set of instructions for doing
> > that". I.e. g violates the finite description part of computability.
> > I think Brent Meeker was trying to get at this idea, too, in answer to
> > your diagonalization explanation in 2001.
> >
> > http://www.mail-archive.com/everything-list.domain.name.hidden/msg01002.html
> >
> > But both then and now, you said that this is not the right reason, and
> > then you went on to repeat the proof by contradiction, which we already
> > understand.
>
> You have perhaps miss the difference between two resembling proof. I
> think A summary will be necessary. It should be easy because the proofs
> are short.
>
>
>
> > If finiteness does not correspond with the reason for
> > non-computability, this implies that there are g's formed by this
> > diagonalization method, which have a finite description, but that take
> > an infinite time to execute (thus fulfilling the definition of
> > non-computable).
>
> Are you talking about the diagonal function g build on from the set of
> all fi, and which is not computable, or about the G get from the Fi,
> which is partial computable, or about some given effective enumeration
> of total function (where we have used also the letter fi)?
> Or just wait for a summary where the proposition will be numerated for
> the sake of future use of them. Well here apparently you were talking
> about the Fi.
>
> >
> > So apparently we are still missing something. You need to tell us
> > *why* this is not the right reason. The set of instructions for g is
> > precisely a big "case" statement (if you will) on n, like this:
> >
> > switch n:
> > begin
> > case 1:
> > set of instructions for f1:
> > case 2:
> > set of instructions for f2:
> > case 3:
> > set of instructions for f3:
> > ...
> > end (after an infinite number of cases)
> >
> > This is an infinitely long program. You need the whole program to
> > define g, not just the portion you need for a given input. Is there a
> > finite version of g? I don't see how.
>
> But here you talk distinctly about the fi.
> if your fi denotes all the total computable functions, then, what we
> have proved, is that not only your "program" for g would be infinite,
> but, above all, could not be generated by any computational process:
> you cannot generate the sequence of all, and only all, total computable
> function f1, f2, f3, ...
> CT is the statement that the fi are among the Fi, so that you can
> generate computably a superset of the fi.
>
> Bruno
>
> http://iridia.ulb.ac.be/~marchal/
Yes. I am talking about the fi in all of the above. I think we are
actually in agreement about this. I understand the argument, given the
acceptance of the Church Thesis.
Tom
--~--~---------~--~----~------------~-------~--~----~
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 17 2006 - 23:59:30 PDT