Le 17-déc.-07, à 19:04, meekerdb (Brent Meeker) wrote:
>> Bruno wrote: >> Exercise: >> What is wrong with the following argument. (I recall that by >> definition >> a function from N to N is defined on all natural numbers). >> >> (false) theorem: the set of computable functions from N to N is not >> enumerable. >> (erroneous) proof: let us suppose (by absurdum) that the set of >> computable functions from N to N is enumerable. Thus there exist an >> enumeration f_1, f_2, f_3, ... f_i, .... of the computable functions >> from N to N. But then I can define the following computable function >> g, >> from N to N, by: >> >> g(n) = f_n(n) + 1 >> >> g is computable: to compute it just search in the enumeration the >> function f_n, which is computable, and then apply it on n, and then >> add 1. >> But then g has to be in that enumeration f_i of the computable >> function. >> Thus there is a k such that g = f_k. In particular g(k) = f_k(k). But >> g(k) = f_k(k) + 1, by definition of g. Thus f_k(k) = f_k(k)+1. And the >> f_i are computable functions, so f_k(k) is a well defined number, >> which >> I can subtract on the left and the right side of f_k(k) = f_k(k)+1, >> giving 0 = 1. Contradiction. So the set of computable functions from N >> to N is not enumerable. >> >> What is wrong? We know that the set of computable function has to be >> enumerable, because "computable" means we can describe how to compute >> the function in a finite expression in some language, and the set of >> all >> finite expressions has been shown enumerable. So what happens? > > If you tried to compute g(k) and g was in the list, i.e. some f_k, > then when > you searched a for g, when you came to f_k it would start with the > prescription "...just search in the enumeration..." and you would be > in a > infinite loop. This is a bit fuzzy, but then the exercise was a bit fuzzy too, so I can considered this as correct. More below. Barry Brent wrote: > Brent, I don't think this is enough. There may be a different > algorithm for f_k that escapes your infinite loop. If this > alternative algoritm doesn't exist, I think you need to show that it > doesn't exist. > > I suspect that the error in Bruno's erroneous proof has to do with > formal languages. Say a function f is computable with regard to a > formal language L when there exists an algorithm written in L to > compute f. The f_n are computable with regard to some particular > formal language. Functions computable with regard to one language > may or may not be computable with regard to another language. (If > this is false, Bruno needs to prove it's false.) Thus when Bruno > argues that the set of computable functions is enumerable, he must > mean "for any fixed language L, the functions computable with regard > to L is enumerable." Now the procedure Bruno described for computing > g is not written in a formal language--it's written in English. The > fact that this English language description is finite doesn't prove > that g is computable with regard to L, ie, doesn't prove that g is > one of the f_n. > > I'm an amateur at this--this "solution" is really just a question for > Bruno... > > > Barry (Barry Brent, not Brent Meeker!) Now, if this comment was correct, it would mean that universal languages or universal machines would not exist! Actually, I can also take this remark as a correct conclusion, but only by considering a restricted notion of universal machines or language. Barry, are you actually denying Church Thesis (which says that an universal language exists, indeed LAMBDA-CALCULUS is one!) ? Barry Brent, Brent Meeker, you are both correct, individually, but you cannot be both correct simultaneously, so what? I let you and others think a bit more, for the fun of it, for the importance of being 100% clear on this before proceeding, and because I have not the time to say more today. Don't worry, even the biggest one like Godel, Kleene, Church ... all have been wrong on this at some moment. It *is* a bit subtle. But all the possibility of my work, or more generally, the very consistency of comp relies on that subtlety. Only after a good understanding on this, will I be able to come back on less technical explanation. If I explain things non technically to soon I will have the feeling to "take you in a boat" (we say in French), meaning roughly to be dishonest. It is worth to take the time, and to play a bit with the idea, right? Bruno PS I know also, for having explained this years ago in the list that some in the list does understand what happen here, but I encourage them to go through the reasoning again, because I am not sure they did understand the *impact* of this .... It is one thing to understand a proposition, and another thing to get the importance, relatively to the TOE search of what is really going on here ... In particular, when the ASSA people invoke Kolmogorov complexity notions, they do rely on Church Thesis .... The "key post" is a key for everybody, I mean for both ASSA and RSSA type of TOE researchers. 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 -~----------~----~----~----~------~----~------~--~---