Hi Mirek,
Le 30-janv.-08, à 13:42, Mirek Dobsicek a écrit :
>
>
> Hi Bruno and everybody,
>
>>> I
>>> hope to send my comments and/or 'OK' sign :-) on Monday.
>>
>> Take it easy. There is no deadline on the list.
>
> Making a declaration helps me to get things done. Yet I'm late.
> Whenever
> you see such sentences in my posts, you can skip it, they are mostly
> for
> me :-)
Am I suppose to skip this one too? :)
>
> ---
> I'll try to write a summary in my own words. Let's see how much I did
> understand.
>
> Prepositions:
> A finite alphabet
> A* finite words over A (it is enumerable, moreover effectively
> enumerable)
> L . a language over A.
> E a subset of A*, a set of valid expressions in L (obviously, it
> is at least enumerable)
> M . a machine which understands to L
> f . a total function from N to N.
>
> Goal: I want to develop a universal language L which describes all
> and only all functions f. Given an expression from E, M computes the
> result in finite time. Given the restrictions on L, the result is a
> number and nothing else.
>
> The set of all functions f from N to N is not enumerable (by Cantor's
> diagonal). Thus there is no bijection to E. Thus, I have to find a
> smaller set of functions. I will call this set a set of computable
> functions, C. Inevitably, this is computability by definition, by
> definition of L. So L should be 'really good' in order to encompass as
> much functions f from N to N as possible.
>
>
> Now, I think of a bijection between E and C.
> 0 --- E_0 ~ f_0
> 1 --- E_1 ~ f_1
> 2 --- E_2 ~ f_2
> 3 --- E_3 ~ f_3
>
>
>
> Since E are efficiently enumerable, C are efficiently enumerable ...
I guess you want to say "effectively enumerable". Typo error.
> ... as well. Yes, it might happen that f_i = f_j for i != j, but is
> does not
> matter as long as all unique f_i are in the enumeration.
>
> Time for the Kleene diagonal argument. Opps, a language L that I dreamt
> of does not exist. I have to relax from the condition that M on E_i
> always return a number in a finite time. Well, what to return if not a
> number ... nothing -> M experiences an infinite loop.
>
> What a world, ok, my language has to describe total functions from N to
> N and as well as strict partial functions from N to N.
OK.
> And it is clear
> that I cannot know whether E_i corresponds to a total function or a
> strict partial function.
Clear for you, apparently. Is it clear for everybody? This follows from
the Diagonal argument applied on the "programs" in L.
> f' stands for any function descriable by L.
>
> 0 --- E_0 ~ f'_0
> 1 --- E_1 ~ f'_1
> 2 --- E_2 ~ f'_2
> 3 --- E_3 ~ f'_3
>
>
>
> N, E and C are enumerable, moreover obviously effectively enumerable.
> Any subset of C is at least enumerable. A subset of C corresponding to
> total functions is no effectively enumerable. It cannot be.
>
> Well, a language L which describes both total and strict partial
> functions and hereby defines a set of computable functions is not
> refuted by Kleene's diagonal.
OK. I guess that you see now that is by allowing a universal machine to
do infinite task which makes CT consistent (possible). OK?
>
> It is not obvious to me how strong sort of evidence that universal L
> exists, it is to survive Kleene's diagnonal. Droping an apple on the
> floor is in favor of Newton's law but not very convincing :-)
Because the diagonal argument is *the* tool for demolishing the idea
that such or such set is universal or complete, but then it does not
work on language like Lambda, Turing, etc. This entails a strong form
of incompleteness.
Then, Judson Webb, argued that Godel's incompleteness confirmed such
incompleteness, and thus CT, and thus Mechanism, Comp ...
>
> Oh, now I realize that my question is actually weird. Since the set of
> computable functions is defined by L, and L is said to be universal if
> it describes exactly these functions - it is simple to develop a
> trivial
> L -> it defines a set of computable functions ... and of course
> universal L exists.
OK, but this is due to your "definition" above of the set of computable
functions. Recall that we do have some starting intuition of what is an
intuitively computable functions. Church thesis is the assertion that
LAMBDA (or FORTRAN, or whatever programming system you love) does
capture that starting intuition. CT is both philosophical (linking an
epistemic concept with a mathematical class of functions) and
scientific (refutable in Popper sense: CT would be refuted in case we
find a clearly humanly computable function which would be uncomputable
in Lambda (and thus in Turing, Java, or any modern all-purpose
computer, etc.).
>
> In this sence a universal language L always exists. So I write it
> rather
> like this:
>
> If we develop many sufficiently different programming languages and
> they
> turn out to be all equivalent, it mig
