Bruno--
Ahh, my amateur status is nakedly exposed. I'm going to expose my
confusion even further now.
Never heard of a universal language. I thought I was familiar with
Church's thesis, but apparently no. I thought it was the claim that
two or three or four concepts (including recursive function and
computable function) were extensionally equivalent. I have heard of
the lambda calculus, but I don't know what it is, or what its
connection is with Church's thesis. I have a rough guess, based on
what you're saying. I'm surprised. I imagine that the claim of
existence of a universal language must be made in the context of a
theory of languages? Never heard of that theory.
Well, if I imagine such a theory, it must involve both syntax and
semantics, yes? Semantics connects a language to a world, right?
(The experts are cringing, I'm sure....) Can one language encompass
all possible worlds? Can't we imagine worlds, the structures of
which are so dissonant, that their languages could never be
consistently subsumed under some single larger ("universal")
language? (More cringing, no doubt....) Or, is it that when we
restrict the worlds in question to some suitable realm--say, numbers--
all these things work out? (Cringes redoubled!) I can imagine other
ways out. Maybe we're concerned with just one world, suitably
described. Maybe structural inconsistencies of possible worlds are
no more an impediment to being expressible in one language than
logical inconsistencies? (But how do we know?)
What about cardinality? From your remarks, I imagine that the number
of elementary symbols in any language, including the universal
language, is supposed to be finite, so that the set of algorithms is
countable? If there are lots of worlds and languages, I wonder how
people make that work. Is such a language going to be adequate for
expressing propositions about all possible worlds? How do we know?
My poor excuse is, I've only been on this list a little while, and I
made my (sketchy) acquaintance with these ideas a very long time
ago. Sorry if I'm way off topic. Tell me to go look it up
somewhere, or stop wasting time, if you want to...
Barry Brent
On Dec 18, 2007, at 8:49 AM, Bruno Marchal wrote:
>
>
> 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/
>
>
> >
Dr. Barry Brent
barrybrent.domain.name.hidden
http://home.earthlink.net/~barryb0/
--~--~---------~--~----~------------~-------~--~----~
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 - 13:33:32 PST