More comments on George Levy + *THE PUZZLE*.
Le 30-mai-06, à 20:42, George Levy a écrit :
>
> To speak only for myself, I think I have a sufficient understanding of
> the thread. Essentially you have shown that one cannot form a set of
> all
> numbers/functions because given any set of numbers/functions it is
> always possible, using diagonalization, to generate new
> numbers/functions: the Plenitude is too large to be a set.
The first person plenitude will be too large or too complex to be a
mechanically generable set.
Just to give the exact wording of the conclusion. The explanation will
follow. I am glad you describe the tranfinite extensions of the set of
(growing or not) computable functions as a plenitude, and it models
indeed well the notion of first person plenitude on which we will
converge with Church thesis, and which describes a quasi solipsistic
transfinitely self-extending self, building from "controllable sets" to
bigger one.
But the sequel should show how Church thesis will force us to accept a
third person comp realm which will somehow transcend the limitation of
the first person, but then with *the* big price.
> This leads to
> a problem with the assumption of the existence of a Universal
> Dovetailer
> whose purpose is to generate all functions. I hope this summary is
> accurate.
Completely. Let me give you *the puzzle*. What is wrong with the
following "refutation" of Church thesis:
Let me just recall what is a computable function from N to N. It is
function from N to N which is such that it is exist a finite way to
explain how to compute it in a finite number of steps on any natural
numbers. More precisely: f is computable if there is a language L such
that f admits a finite code/program/description/number explaining how
to compute f(n), in a finite time on any number natural n.
I will say that that a language L is universal, if all computable
functions from N to N admit a code in L.
A weak form of Church thesis can be put in this way: there exists a
universal language.
I will say a digital (or finitely describable) machine M is universal
if M can "understand" a universal language L, in the sense of being
able to compute any computable functions described in L (and thus all
given that L is universal) . In term of digital machine, Church thesis
becomes: there exists a universal digital machine.
Now what is wrong with the following argument: if there is an universal
language or machine, the computable functions can be described by
finite description in that language, or program for that machine.
Such a set is obviously enumerable. There is a bijection between N and
the set of those descriptions:
1 f1
2 f2
3 f3
4 f4
etc.
So the following function g is well-defined by:
g(n) = fn(n) + 1
Then, to compute it on the number n (439 say), just generate the
description/program of f1 f2 f3 ... until fn, that is f439, apply it
on n to get fn(n), f439(439), and add 1 to get g(n) = fn(n)+1, that is
here: f439(439)+1.
But then g cannot be described in the language L! Why? Suppose g is
described by a code in the language L: then g belongs somewhere in the
list f1, f2, f3, f4, f5, .... Thus there would exist a number k such
that g = fk, and thus g(k) = fk(k); but g(k) = fk(k)+1. And thus
fK(k) = fk(k)+1 (*)
And fk(k) is a well defined number given that the fi are all computable
functions from N to N. So I can substract fk(k) on both sides of (*)
just above, and I get 0 = 1 (contradiction). So there is no universal
language, we cannot generate all computable functions, still less,
then, to dovetail on them.
Where is the error? How could Church still assert that its
"lambda-conversion calculus" (an ancestor of Lisp) is universal? What
about Fortran, Lisp, Python or other Rational Unitary Matrices?
I (re)assure you (?), I will keep Church thesis, without which there is
no just no UD. What does the above reasoning really prove then? What
price will be asked upon us for keeping consistently our belief in
universal language and universal machine?
It is not important to find the answer, but it will be capital to
understand it, and for that, it is capital to get the question, to see
the problem. I think that you, George, have seen the problem, and I am
just making higher the probability that others see as clearly as
possible the problem too. Hal and Jesse made big hints toward the
solution but I am not sure they have put the fingers on the very very
pricy consequence (?).
Bruno
PS Rereading some recent mails I wrote, I am ashamed of my style (when
I complete a sentences!) and by my enduring mishandling of the
singular/plural (the "s" problem). Please accept my apologies, and
don't hesitate to correct me or to ask questions in front of
ambiguities. Thanks for the interest anyway.
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 Mon Jun 05 2006 - 08:29:06 PDT