Le 17-juin-06, à 07:56, Stathis Papaioannou a écrit :
>
> Bruno,
>
> I'll rephrase the problem - let me know if I get it wrong. It is
> proposed that all the functions f with certain attributes "A" be
> enumerated in a list: f1, f2, f3 etc. It looks like "A" in the example
> under consideration means "all the computable functions", but in fact
> there is a further implicit restriction: the list can only contain all
> the computable functions which will fit into the labelling scheme
> chosen for the list.
If I remember correctly I did make this explicit (but then it is easy
to miss a post or a paragraph in a post or just a line:). I have
defined a *computable* function (from N to N) as a function f such that
there is a language (labeling sheme as you say) L in which it can be
explained finitely and without ambiguity how for each n to compute
f(n).
Now, I have defined the notion of Universal Language UL as a language
in which *all* computable function can be defined. (I also define a
Universal Machine as a machine capable to "understand" the Universal
Language, and thus capable of computing *all* computable function from
N to N.
And then Church Thesis is the statement that there is a Universal
Language, in particular, that programming languages like FORTRAN, LISP,
Java, c++, etc. are universal languages.
> Now, when we say that g(k) is the kth function in the list +1, we are
> defining an apparently computable function that does not have a place
> on the list, since if g were the ith function on the list we would
> have fi(i)=fi(i)+1.
At this stage: you really should say what the fi are meant for. To be
sure I will treat one+three cases under the form of 1+3 lists:
0) r1 r2 r3 r4 r5 r6 r7 r8 ...
This is an arbitrary list of functions from N to N (not necessarily
computable one);
1) h0 h1 h2 h3 h4 h5 h6 ...
This is a list of total computable functions from N to N that we can
generate mechanically (I mean we can generate their codes). It means
that we can generate the codes of each hi, written in some language,
and that, for some reason, we are sure that each hi is total
computable. Examples: Caylor last funny enumeration; all the
(transfinite collection of) sequences of growing functions we have
defined in this thread (since "Smullyan Smullyan ...");
2) f0 f1 f2 f3 f4 f5 f6 f7 ...
This is a list of *all* total computable functions;
3) F0 F1 F2 F3 F4 F5 F6 F7 F8 ...
This is the list of all programmable things in some "universal
language" like fortran. CT asserts fortran is universal so that the
total computable function fi will be dispersed *among* those Fi things,
so that a universal machine can really compute all the fi, among other
things.
Now the same diagonalization argument proves 4 different propositions
according to which list we are talking about. Which one?
Before answering, I let people muse a little about what are those 4
different consequences, given that the only way to really grasp those
propositions consists in rediscovering them by oneself.
> However, this is only a contradiction if we say that the list contains
> all the computable functions; it is not a contradiction if we say that
> the list contains all the computable functions which fit into the
> labelling scheme chosen for the list, as I think we must.
(perhaps to read or reread after the musing suggested above).
It depends what sorts of "labeling scheme" you are interested in. The
key is that:
1) either you want only total functions (so that you can be sure your
machine will not crash): in that case the diagonal g is total
computable but cannot belong to your list. You would need another
labeling scheme for a language extending your previous labeling
containing that g. Like with the sequence of growing computable
functions, this label-extension can be iterated into the transfinite.
But at each of those transfinite stage your machine is NOT universal,
but it grows toward it keeping control. (it is a sort of pre-image of
the first person exploring the first person *plenitude* (Levy's
expression)).
2) or you want to capture *all* total functions at once through one
*universal* labeling scheme. Church Thesis is the statement that this
wish can be fulfilled despite diagonalization (crazily enough!). Indeed
CT asserts FORTRAN is such a universal language. And the programs can
be effectively (fortran-mechanically, Turing-mechanically, recursively,
... with CT all those terms are equivalent) enumerated, so that you get
the Fi. The price to pay for escaping the contradiction through the use
of the diagonalization: some Fi are undefined and even unpredictably
so. That is, the Fi enumerates a set much vaster than the fi, and the
fi forms a NON recursively enumerable subset of a recursively
enumerable set (the Fi), a little like the "Joconde" is a very complex
subset of a simple rectangle!
I know that George Levy does not like this too much: but the first
person plenitude, [although so big and so unnameable that you cannot
generate it in one stroke-program, but that you can yet explore into
the constructive transfinite ...] is contained in the ("simple")
effectively enumerable set of partial recursive functions. But the
border of the set of (codes of) the total function is fuzzy, it looks
like the border of the Mandelbrot set in some sense. Chaitin or Webb
would not contradicts me when asserting that life and mind (could)
emerge internally on that border, ... and then eventually physics (my
work).
> This is perhaps just the point you are making: it is not that g is not
> computable, rather that the attempt to enumerate the computable
> functions is problematic.
Yes. The attempt to enumerate effectively all AND ONLY ALL computable
functions from N to N is problematic. With CT, "effectively" can be
translated into "fortran-effectively", and then you can translate
"problematic" by "impossible". And the g defined from the fi is not
computable, because the bijection i ----> fi is not computable. g,
defined on all total fi, is not computable because the fi are not
effectively enumerable.
And with CT: a fortran program *can* enumerate ALL computable functions
from N to N. But then NOT in any effective way. Any algorithm
generating all computable functions will generate them by generating a
superset containing the possibly and unpredictably undefined partial
functions as a "poisonous" gift (the uncontrollable third person
"exterior" perspective including the ten thousand crashing (infinite)
path). G, defined on all Fi is programmable, but necessarily undefined
on their own code: if G = Fk, Fk(k) makes the universal machine
crashing.
> But is it as surprising to discover this (or what I think of as
> related results, like Russell's Paradox and Godel's Theorem) as it
> would be to discover, say, a discrepancy or contradiction in the
> addition and subtraction of integers?
We are just proving theorem by the method of reduction to
contradiction. If we find a real contradiction between addition and
multiplication statements it would be the end of classical mathematics
and physics and platonism, etc. Weak theory like Peano Arithmetic would
be inconsistent. I would quit the math job, and frankly I think the
multiverse itself would collapse. But there is no reason to doubt the
consistency of arithmetic.
>
> I'll reply to the second part of your post later.
Thanks. Take your time,
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 17 2006 - 12:21:31 PDT