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 everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Tue Dec 18 2007 - 09:49:41 PST