- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Tom Caylor <Daddycaylor.domain.name.hidden>

Date: Sat, 17 Jun 2006 20:58:27 -0700

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

Date: Sat, 17 Jun 2006 20:58:27 -0700

Bruno Marchal wrote:

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:11 PST
*