Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
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,
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
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
