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/
--~--~---------~--~----~------------~-------~--~----~
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 - 07:57:51 PDT