Bruno Marchal wrote:
> 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 (?).
>
Not to try to answer the Puzzle, but just some thoughts for the
conversation:
At one glance, it seems that the argument is trying to transcend
Godel's Incompleteness theorems. The Universal Language is trying to
be both universal (complete) and consistent.
This Puzzle seems to corresponding to part of Step 7 in your Universal
Dovetailer Argument (UDA). In that Step, you perhaps answer the Puzzle
so I don't want to simply quote the answer, which might short-circuit
my/our understanding. But I have a problem with answering that the
programs which conclude that 0 = 1 simply run forever. Couldn't you
build any "complete" system or theories by simply letting programs run
forever. This seems to be an artificial/arbitrary path to the truth.
Couldn't you conclude whatever you want with this method? Perhaps I'm
just proving your point.
Tom
> 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/
It is probably mainly because of English being not your native
language. My familiarity with a few non-English Latin-based languages
helps in my understanding, I hope. If only there was a Universal
Language.
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 Mon Jun 05 2006 - 12:39:00 PDT