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 [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---