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

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


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.

You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at

Reply via email to