Bruno Marchal wrote:
> ...
> It looks like g is computable isn't it. All fn are computable and can
> be computed on each n, and certainly adding one ("the + 1") is
> computable too. Right?
>
> Well, if you say "all right" here, we are in trouble. Because if g is
> really computable, then g is in the sequence of all computable
> functions fi. But then *there is* a k such that g = fk, and then g(k)
> is equal to both fk(k) and fk(k)+1, and that gives 0 = 1, by
> substracting the well-defined number fk(k).
>
> So g just cannot be a computable!
>
> How could g looks like being computable? It is true that all fn are
> computable, and it is obviously true that "+ 1" is computable.
> So, the only thing which is not computable is .... the bijection
> itself, between N and the fi.
>
> It is the correspondence:
>
> 1 --- f1
> 2 --- f2
> 3 --- f3
> 4 --- f4
> ....
>
> which is NOT computable! 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?
>
> BUT THEN .....
>
> Saying this, it could look like the Universal Dovetailer is still in
> peril. But I have given you the shape of the solution when I show you
> the proof of the existence of a irrational number which exponentiated
> to an irrational number gives a rational number. That precise problem
> is irrelevant, but the non constructive reasoning I did to prove it is
> very relevant here. I was telling that there exist some mathematical
> object, but I was unable to give it. I was only able to give you a bow
> with the shape
>
> { a b }
>
> telling you the "solution" was in that box (but not saying if it was a
> or if it was b).
>
> The same here, but with an infinite box. I cannot generate mechanically
> the set {f1, f2, f3, ...} of computable functions, but there is still
> hope (Church Thesis CT will just express that hope) that I can generate
> some BIGGER set, containing all computable functions AND MANY OTHER
> THINGS TOO. The hope is that the OTHER THINGS will help us escaping the
> diagonal contradiction.
>
> Well, actually CT says more: it says not only that there is a universal
> language/machine, but that fortran is such a one! And fortran programs
> are fortran generable, so I can generate a sequence of all fortran
> one-variable program F1 F2 F3 F4 F5 F6 F7 F8 .... ("all" means that
> soon or later this sequence goes trough any fortran programs: it is of
> course an infinite set)
>
Here, the Fi's are all still computable but not necessarily from N to N
(i.e. total). Right?
Why is it that we are interested only in total computable functions?
The first paragraph in my previous post, on "motivation", addressed the
motivation for computable, but why total? Do total functions have some
attribute that is required in your comp?
> So, given that the sequence F1, F2, F3, F4, F5, ... is generable, the
> corresponding diagonal function G defined by
>
> G(n) = Fn(n) + 1
>
> *is* programmable in fortran. So there *is* a k such that G = Fk
>
> And what will happen if I apply G on its own number-code k?
>
> Just this: your machine will crash! The fortran interpreter will go in
> loop or in an infinite computations.
>
> Well, in some formal sense I will get G(k) = G(k) + 1. But I can no
> more substract G(k) on both sides like we have always do at that stage,
> because G(k) is just not a well-defined number.
> It looks like the OTHER THINGS are the function from a subset of N to
> N. Functions, now, if we want to associate them to the fortran
> programs, can be only partially defined functions.
>
> So I can still hope the sequence Fi of Fortran programs goes trough,
> among OTHER THINGS, all computable functions everywhere defined, but
> the price will be that I will got the undefined programmable functions
> by the same token.
>
I can see why a *non-computable* function would run forever, because if
it is generatable it must admit a finite description, so the only other
attribute of computability it can fail to have is finite execution.
But why would a computable partial function run forever? Why would it
even crash? Wouldn't the Universal Dovetailer just generate the
program for that function and run it on all numbers that it is defined
on?
When we are jumping from functions to programs crashing, I am getting
confused. It would seem that a program running forever and a program
crashing (stopping without the right answer) would have different
effects on a Universal Dovetailer.
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 Sun Jun 11 2006 - 02:50:15 PDT