Re: Diagonalisation 1

From: Brent Meeker <meekerdb.domain.name.hidden>
Date: Wed, 22 Aug 2001 18:02:54 -0700

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
f_k.

Brent Meeker
Received on Wed Aug 22 2001 - 19:10:21 PDT