Bruno Marchal wrote:
> Le 11-juin-06, à 08:49, Tom Caylor a écrit :
>
> >
> > Bruno Marchal wrote:
> >> There is just no algorithm which can generate
> >> the sequence of codes of the computable functions from N to N. So,
> >> although each fn is a computable function (from N to N), you cannot
> >> diagonalize it for getting g, because to compute g on n, g(n) you need
> >> to generate the n first programs corresponding to f1, f2, f3, ... fn,
> >> and then apply it to n (and then add one), but you just will never
> >> been
> >> able to give me a finite set of instructions for doing that. If {f1,
> >> f2, f3, ...} are all computable function from N to N, and if the
> >> sequence is complete (con,tains all such function) then g, although
> >> mathematically well defined, is just not programmable.
> >>
> >
> > Here, I would think that to compute g(n), you would only have to
> > generate fn and apply it to n and add one. In saying that you have to
> > "generate the n first programs", perhaps you are looking ahead to the
> > Universal Dovetailer starting at f1 which is the smallest program, etc.
> > But if we are just considering the math/definitions here, I'd reason
> > differently to show that the bijection is not computable. It seems
> > that the way to prove that g is not computable, we could show that one
> > (or both) of the following is false:
> >
> > 1) g can be specified in a finite number of symbols.
> > 2) g can be executed in a finite number of steps, given any single
> > input.
> >
> > I think that #2 above is actually true. To compute g(n), you just
> > compute fn(n) and add one (like you said). Since fn can be executed in
> > a finite number of steps, then #2 follows. Even if you had to compute
> > all of the fi from 1 to n in a dovetailer fashion, it would still
> > compute g(n) in a finite time, since all of the fi's are computable. I
> > guess even if this was the Universal Dovetailer computing the fi's
> > interspersed with non-computable Fi's, it would still compute the fi's
> > in a finite amount of time, along with a finite amount of the
> > non-computable Fi's computation (even though it will not finish the
> > Fi's computation).
> >
> > On the other hand, I think that #1 above is false. This is because, in
> > order to specify g as a bijection from N to N, you need an infinite
> > number of symbols: you need *all* of the programs {f1, f2, f3, ...},
> > which is a countably infinite number of finite programs, which added
> > together makes a countably infinite number of symbols. Am I off track?
>
> I think you are a little bit off the track here (and less in your other
> post).
>
> 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. 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).
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.
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 Thu Jun 15 2006 - 12:41:08 PDT