>> 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. > > Brent Meeker
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!) --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
