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 :-)
---------------
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 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. And it is clear
that I cannot know whether E_i corresponds to a total function or a
strict partial function. 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.
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 :-)
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.
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 might convince me that the set of
'computable functions' is fixed. Although, written like this I can think
of educated (math) people who will tell me: This is all you have????
So, what are like 2-3 most direct consequences of CT which make CT to
seem rock-solid? Here I assume that CT basically says that the set of
functions descriable by the lambda calculus is all what I can ever compute.
-------------
Regarding points 3)-5) of your summary, I am lost on terms such as
Absolute ontic TOE, Observer Moments, Aristotelian principles, Machine
theology, ...
-------------
I wrote down a list of short-term goals on what I would like to have
some background/knowledge with a help from this list:
1\ I saw somewhere a sentence saying approximately this:
".... so universe is performing a computation. Is then universe a big
computer? No."
I would like to know in a broad sense what it tries to say a why one
shoud rather accept it or reject.
2\ Bruno, you recently wrote that you do not agree with Wolfram's
Principle of Computational Equivalence. As I understand to that
principle, Wolfram says that universe is a big cellular automata. What
is the evidence that it is unlikely this way?
Sincerely,
Mirek
--~--~---------~--~----~------------~-------~--~----~
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 Wed Jan 30 2008 - 07:41:49 PST