Hello Mirek,
Le 05-déc.-07, à 23:08, Mirek Dobsicek a écrit :
thank you for your post. I read it a couple of times in order to more
or
less grasp it, but it worth it. I have some questions...
Suppose there is a secure universal machine M. The set of expressions
it can compute provide a secure universal language L. That set is not
only enumerable (given that it is a subset of an enumerable set) but
above all, it can be enumerated effectively (by the ashole).
What do you mean here by effectively? I understand it as you just want
to emphasize that the set is really enumerable.
I guess I will come back on this in the next post. But the point is
that a set can be enumerable, yet NOT effectively enumerable.
Effectively enumerable means enumerated by following unambiguous
instructions in some language (universal or not). A dumb idiotic can do
that.
To sum up a bit:
Recall that by a function from A to B, I always mean a function defined
for all elements of A having value in B. In particular a function from
N to N is defined on all natural number. To emphasize on this I will
say sometimes TOTAL function. Then I will say strictly partial
function for a function from S to N, when S is a proper subset of N.
Cantor's diagonal on N^N shows that the set of functions from N to N,
i.e. N^N, is not enumerable (uncountable, ... mathematician have a lot
of synonyms). So there is no bijection from N to N^N.
Let us define N^N-comp as the set of computable functions in the sense
described in the key post. It is the set of total computable
functions, or better described (but less usual) it is the total
functions which are computable.
Then N^N-comp is enumerable (indeed their corresponding
set-of-instructions is a subset of all expressions in the language,
which is already enumerable).
Diagonalisation on N^N-comp shows that, although N^N-comp is
enumerable, it is *not effectively enumerable*. The bijection between
N^N-comp and N exist, yes, but is not a computable function. If it was,
then the diagonal function g (with g(n) = f_n(n) +1) would be
computable, in the list, and then 0 = 1, as I have try to explain. So
it is really the bijection sending n on f_n which is not computable,
and which makes g not computable.
We can still believe there is a universal language in which we can
define all total computable function, but then the language has to
define more than the total computable one. In that case we get a
language L which defines a more general class of computable
functions, the one which are no more defined on all inputs. In that
case the diagonal function g can be defined in the language, but then
such function has to be undefined on its godel number k, that is, the
number k such that g = f_k.
And the key point is that no set of instructions at all can help the
universal machine to distinguish in all case a code of a total function
from a code of a strictly partial function. For if that was possible,
then we could securise the universal machine making it computing only
total functions, and then the diagonal will strike again and prove 0 =
1.
Note this discovery:
If A is enumerable, and if B is included in A, then B is enumerable.
But if A is effectively enumerable (meaning really that the ass..., er
I mean the dumb one can enumerate A), it DOES NOT follow that any
subset of A is effectively enumerable.
There is a bijection between the set of code (instructions,
expressions) of total computable function and N, but what the second
diagonalization shows, is that such a bijection is not a computable
bijection. The set of code of total function is an enumerable, but not
effectively enumerable subset of the set of code of the partial (strict
and not strict) functions.
So, as you know, Church did *define* a computable function by a
function computable by a lambda expression, in its conversion
calculus.
Why do you introduce here the term 'lambda expression'? I'm asking this
because in the sequel you work just with 'a well specified language
which is promised to be universal' and you prove that such a promise is
not ruled out.
I do not see how you reached the conlusion:
But thanks to that crashing, *Church thesis remains consistent*. I
would just say An existence of a universal language is not ruled out.
OK. But Church thesis says that Lambda is universal, and so a weaker
form of Church thesis (the one which asserts the existence of a
universal language) remains consistent. OK.
Each expression like that denotes now either a computable function
from
N to N, or as we have to expect something else. And we have to expect
they are no computable means to distinguish which U_i represents
functions from N to N, and which represents the other beast.
Can I say that the other beasts are only and only infinite loops? I
assume that the machine cannot destroy itself, so it either stops after
computing a computable function or enters
