# Re: *THE* PUZZLE (was: ascension, Smullyan, ...)

Le 17-juin-06, à 07:56, Stathis Papaioannou a écrit :

<x-tad-bigger>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.

<x-tad-bigger>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.

<x-tad-bigger>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.

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).

<x-tad-bigger>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.

<x-tad-bigger> 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?</x-tad-bigger>

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.