Bruno Marchal wrote:
> Hi,
>
> Ok Tom, put your security belt because we will leave the constructive
> area, because it is the price we need to pay, in front of machine, for
> NOT leaving the finite area.
>
> Let me recall the problem.
>
> 1) Obviously the set of all computable function from the set of natural
> number N to the set of natural numbers N is countable (synonym:
> enumerable, in bijection with N). The reason is that a computable
> function, by definition, has a code (synonym: a description, a program,
> a finite machine), that is any finite things which can be used by some
> entity/machine for computing the functions, and (infinite) sets of
> finite things are always (infinite and) countable.
If I may, I'd like to revisit why (the motivation) we are considering
functions from N to N. I guess it is because all computations are
equivalent to taking a number from N (i.e. each uniquely meaningful
input of a computation can be put into a one-to-one correspondence with
a number from N, because there are countably many inputs) and produce a
number from N (same reasoning for output as for input). I guess that
you are interested in computations because this is what your comp is
based on. Your "sufficient level of substitution" is a description of
a person with countably many symbols. Right?
> Note that a (one) computable function is an infinite object, but giving
> that that infinite set is computable and generable from a code, the set
> of computable functions is in bijection with the set of their codes,
> which itself is in bijection with N, and so the infinite set of
> infinite objects which are the computable function is in bijection with
> N.
>
When you say "infinite object" here, you mean that the function
computes an infinite number of values, i.e. all the numbers in N.
Right? Even though the function is programmed with a finite number of
symbols, equivalent to a finite number from N. A function programmed
with a finite number of symbols, say digits, I can think of as a finite
number, or if I put a decimal point in front, a rational number. This
is equivalent to saying that the rational numbers can be put in a
one-to-one correspondence (bijection) with N, which is true. We can
see that this does not remain true if we allow for infinite programs,
i.e. a program defined by an infinite number of symbols/digits. The
number of such programs is equivalent to the cardinality of the reals
or the continuum. So we have to keep in mind that "infinite object"
refers to the domain of the function, not the description of the
function. Right?
> 2) Now it looks like we have already a contradiction. let us write f1
> for the computable function having the least code, f2 the second one,
> etc. So we get the sequence f1, f2, f3, f4, f5, ... fn, .... And let
> us define the function g by
>
> g(n) = fn(n) + 1
>
> 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.
>
This seems to be a result of the fact that we have given *meaning* to
the symbols, by specifying that the symbols have to make sense in some
language. This seems to imply that "attributing meaning to symbols" is
not algorithmically codable. If you could code it, then it would be
programmable (and even computable if it halts). But then it would just
be a bunch of numbers being crunched without meaning.
>
> 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)
>
> 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 give you an infinite box:
>
> {F1 F2 F3 F4 F5 F6 F7 F8 F9 ...}
>
> but then, I can no more use any algorithmic way to filter out the
> "solutions" (the computable function from N to N) from the "non
> solution" (the functions no more everywhere defined, or the function
> defined on proper subset of N). Why? because if I could do that, I will
> be able to build an algorithmically sequence of everywhere defined
> computable functions, and from that, I hope you are convinced that I
> *can* prove that 0 = 1.
>
> The lesson is not yet Godel's incompleteness, but is very close: the
> price of going through the whole controllable world of computable
> functions is to accept, hidden among it, the whole uncontrollable world
> of the undefined functions. They are hidden due to that impossibility
> of filtering the code of the everywhere define functions from those who
> are not.
>
> Put in another way: all universal machine can crash. If someone want to
> sell you a computer with a so clever operating system that the machine
> never crash, then you know the machine is not universal, or the seller
> says a falsity.
>
> Hal and Jesse were close. For example:
>
> > I was being a little sloppy...it's true that a non-halting program
> > would not
> > be equivalent to a computable function, but I think we can at least
> > say that
> > the set of all computable functions is a *subset* of the set of all
> > programs.
> >
> > Jesse
>
> The key point if, I may insist, is that
>
> 1) the superset (of programmable functions, not everywhere defined) is
> MECHANICALLY enumerable. You can write a fortran program generating
> their codes.
> 2) the subset of (computable function from N to N) is enumerable, but
> is NOT MECHANICALLY enumerable. The bijection with N exists, but is not
> programmable, in *any* programming language!
>
I've been wondering about this in the background for a while, so now I
can ask this question. OK, I think I understand everything so far.
But... if there are functions (in the list of *all* programmable
functions) which will run forever, and you cannot (computably?) know
which ones they are (otherwise you could solve the Halting problem?...
or... at least by the digaonalization reasoning you've given), then
isn't the Universal Dovetailer going to run into one of these programs
and run forever? Alternatively, if the UD executes the first
instruction of each program, there are a (countably) infinite number of
programs, so you would never get to the second instruction.
Alternatively again, are we really allowed to sort the infinite number
of programs so that we execute the one-instruction programs first,
followed by the two-instruction programs, etc.? Isn't this
non-constructive?
Tom
>
> George ? Are you ok. Now that we have undefined functions; we will be
> interested in the domain of definition of the programmable functions,
> and those domain *are* Smullyan's reasoners (in FU). The godelized
> universe is related with the functions F1 F2 F3 F4 F5 ..., and their
> domains traditionally noted: W1 W2 W3 W4 W5 W6 W7 ....
> What we have learned is that we have no algorithm to solve the Wn = N
> question (you see that? saying Wn = N is the same as saying Fn is
> defined everywhere or saying Fn is a computable function from N to N).
> It is an insolubility result. It will be easy, once we get the notion
> of "theory", or "chatting machine", or "recursively enumerable set" to
> transform that into an incompleteness theorem.
> Mmh... To get G and G*, more is needed to be honest, but not so much
> more, just that some "theories" can follow, *in some sense*, all those
> current posts. But this, is what Smullyan shows, albeit very concisely,
> in his "heart of the matter".
>
> 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 10 2006 - 20:01:51 PDT