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 some silly loop.
Despite universal machine are finite entity (like us with comp), we let
them write on wall, papers, or magnetic tape, ....
So as Russell said, the machine could enter in a infinite and never
repeated task. Of course if the machine ask for more memory, and if its
sadic user just say no, well the machine will have problem. later I
will insist heavily that universal machine are finite object. There are
important reason of not putting the "infinite tape" in the machine. The
tape of a Turing machine (for those who met her) is not part of the
machine.
>
>
>> Indeed, the diagonalisation above, where now the f_i are the *partial
>> computable functions*, meaning they are from N to N, OR from a subset
>> of N to N, does no more lead to a contradiction.
>
> I have a problem with this paragraph, could you please write more on
> this? I understand to partial computable functions as to functions
> which
> are not *defined* for every possible input (total functions are defined
> for all inputs, in my limited understanding).
That is correct. Note that such a definition makes the total function a
particular case of the partial function.
Total function: they are defined for any n.
Partial function: they are defined for any n, or not. It is possible
that for some n, they will be undefined.
> Do you say in that
> paragraph that beasts are only and only these partial functions?
Yes.
>
> Huh, now what do I mean by *defined* ... maybe I should say 'which are
> not computable for every possible input'. I am really lost here...
OK I see the ambiguity in the wording.
Let me try another wording: a function is a total function (from N to
N) if it is defined on all N. Example, the factorial function, the
successor function, etc. Then a function will be said to be a partial
function from N to N, if it is a (total) function from a subset of N to
N. Now, just remember that N is a particular case of subset of N (a non
*proper*) subset, it is said. So a total function from N to N is a
particular case of partial function.
That N is a subset of N, follows from the fact that x belongs to N
implies that x belongs to N.
(A is included in B iff (by definition) x b A -> x b B (b = belongs).
Did this help? Don't worry. Some problem can occur because the word
function is not used with the same meaning in the world (flemish and
french talker already use different definition). We can decide to be
clear on that given the international character of the mailing list. I
am sure people use different version, and that is why I have always
(re) define the notion, but I should have insisted that such a word has
just no standard definition). Even mathematicians does not always use
the term function with always the same meaning, when they go from one
branch of math to another, like when going from arithmetic to analysis.
But all serious mathematician are aware of that and usually redefine
such terms before using them.
>
>
> And my last question, consider the profound function
> f such that f(n) = 1 if there is a sequence of n consecutive fives in
> the decimal expansion of PI, and f(n) = 0 otherwise
>
> Is this an example of a partial computable function? Or is this
> function
> as such already considered as un-computable function?
This is "certainly" an example of a total function from N to N. I put
"certainly" in quote because I am using the principle of the excluded
middle.
If you agree that for each n, either there are n consecutive fives in
the decimal expansion of PI, or they are not n consecutive fives in the
decimal expansion of PI, then you agree that, on, your function f is
equal to 1 or to 0.
So the function, for a platonist, is perfectly well define on each n.
It is a total function from N to N.
Is such a function computable?
That is an open problem. What is clear, is that nobody can compute it
today, but this really proves nothing. Open question.
Note that for the bijection between the set of codes of total function
and N, we are in a different situation: such a function has been shown
(in the key post btw) to be not computable by any universal machine, as
defined even just informally like I have done. With Church thesis (the
half of comp) such a function will never been computable (by finite
humble creature).
Hope this helps a bit. I have to go, so I will not *add* spelling
mistakes, this time (g). Don't hesitate to ask any question. Take the
needed time for digesting.
Best,
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?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Thu Dec 06 2007 - 10:42:52 PST