On 21-Aug-01, Marchal wrote:
>                                         in memory of James,
> ==============================
> 2. A paradox ?
> I will say that a function f is computable if there is
> a well defined formal language FL in which I can explained
> non ambiguously how to compute f on arbitrary input (number).
> I must be able to recognise if an expression in my language
> is a grammaticaly correct definition of a function, that is
> syntax error must be recoverable.
> All expression in the language must be of finite length, and
> the alphabet (the set of symbols) of the language is asked to
> be finite.
> Now all finite strings, a fortiori the grammatically correct
> one, form a countable set. Just use the lexicographic order
> defined above.
> So the set of function computable with FL is countable. 
> A synonym of countable is *enumerable*, and is used by
> computer scientist, so I will also use it. 
> So I can enumerate the functions computable with FL, that is
> I can put them in sequence like f_0, f_1, f_2, f_3, ...
> going through all functions computable in or with FL.
> Let us consider the function g defined again by
>                   g(n) = f_n(n) + 1
> Now, g is not only well defined, but is even computable. To
> compute it on n, just search in the enumeration f_i the nth
> function, apply it to n (this gives an answer because the f_i
> are computable) and add 1.
> So, there is a number k such that g = f_k, but then, again
>                g(k) = f_k(k) = f_k(k) + 1
> But f_k(k) is a well defined number (f_k is computable), and
> no numbers can be equal to "itself + 1". Contradiction.
> Could the set of computable functions in FL be uncountable, after
> all, or is g not expressible in FL, or what? 
> Where is the error?   I let you think a little bit. You can
> ask question. (Notably in case of notational problem).

I think there is a cheat here.  "Computable" requires that the function 
be defined finitely.  While                                             
                   g(n) = f_n(n) + 1                                    
appears to be a finite description, it implicitly calls an the infinite 
list of functions f_n.  So it's description is only given in terms of a 
enumerable, but infinite string, and hence does not occur in the list   

Brent Meeker

Reply via email to