Hi,
For those who are interested in the comp hypothesis,
it is hardly a luxury to dig a little bit in computer science.
If only to go toward explicit definition of notion like computations,
computational history, consistent extensions, models, etc.
I open this thread for the very long term.
One of the jewel of computer science is the theory of combinators.
They have been discovered and presented in a talk by Moses
Schoenfinkel (from Moscow) in 1920. And rediscovered
independently by Haskell Curry (USA) in 1930. Church
rediscovered them too under the form of closed lambda expression,
for which he will postulate his famous "Church thesis": the closed lambda
expression are enough to define all computable functions (from N to N, where
N = the set of positive integers).
There is no "Schoenfinkel thesis" nor any "Curry thesis", as
opposed to "Church thesis". Indeed the goal of both Schoenfinkel
and Curry was to "rebuild" an alternative to the whole of mathematics.
One of Schoenfinkel's motivation was to eliminate all variables.
Curry's motivation was to find the most elementary finitary operations
rich enough to (re)build mathematics, and this preferably without formal
sets, but only a finite set of primitive operations.
Actually Combinatory Logic can "easily" be shown
rich enough to represent the partial recursive function, so that
the combinators gives a nice and pleasant computer programming
language. (And indeed LISP and functionnal programming languages
are all descendants or cousins of the combinators/lambda calculus).
But at some fundamental level combinatory logic is much more than
a programming language: it is really a possible road to tackle the problem
of the nature of mathematics, and with comp: the nature of reality.
Also, combinatory logic is very fine grained, and this will enable us to
introduce at a very cheap price important nuances.
Here is a short descrition of combinatory logic (beware: in the preceding post
I made a typo error):
STATIC:
1) K is a molecule (called the "kestrel" is Smullyan's terminology)
2) S is a molecule (the "Starling")
3) if x and y are molecules then (x y) is a molecule. From this you can
easily enumerate all possible molecules: K, S, (K K), (K S), (S K), (S S),
((K K) K), ((K S) K) ...
DYNAMICS: (X and Y are put for any molecules)
1) ((K X) Y) = X (Law of the Kestrel)
2) (((S X) Y) Z) = ((X Z) (Y Z)) (Law of the Starling)
1) means that on any molecules X the molecules (K X) is stable and does not
evolves (except by the evolution of X perhaps). I will say that a molecules
of the shape (K X) is a charged Kestrel.
Now if (K X) comes to interact with some other molecules Y giving ((K X) Y)
you get an explosion leaving as result of the reaction just the molecule X.
So for example
K is stable
(K K) is stable
(K (K K)) is stable
((K K) K) is unstable, indeed it matches the law "1)", with X = K, and Y =
K, so the reaction
is trigged giving K.
((K (K K)) (K K)) gives (K K), ok?
Well the price of having a conceptually very simple syntax (static) is that
the notation can be very quickly a little bit cumbersome. The tradition is
to neglect the left parenthesis abbreviating
(((a b) c) d) by abcd. The laws becomes:
KXY = X
SXYZ = XZ(YZ)
The examples becomes
K is stable
KK is stable
K(KK) is stable
KKK is unstable and "decays" into K, and finally
K(KK)(KK) gives (KK) ok?
What gives S(KK)(KK) ? Solution: it remains S(KK)(KK). It is stable because
S needs "three" molecules to trigger its dynamic. So S(KK)(KK)(KK) gives
KK(KK)(KK(KK)), as
SKKK gives KK(KK) which is still unstable and gives K.
Exercices (Taken from the course "My First Everything Theory" Primary
school Year 2127 :)
Evaluate:
(SS)KKK = ?
KKK(SS) = ?
(KK)(KK)(KK) = ?
(KKK)(KKK)(KKK) = ?
Evaluate:
K
KK
KKK
KKKK
KKKKK
KKKKKK
KKKKKKK
KKKKKKKK
KKKKKKKKK
KKKKKKKKKK
A little more advanced exercices: is there a molecule, let us called it I,
having
the following dynamic: (X refers to any molecule).
IX = X
So a solution is some molecule made up from K and S which applied on any
molecule give as result of the reaction that very molecule unchanged.
For example KXS is not a solution, although it gives X, it is not of the
shape (molecule X).
Of course you can learn a lot by searching "combinators" or "lambda calcul"
on the net. Two samples:
For those "who knows", here is a paper on
Kolmogorov Complexity viewed through the
combinators. It can be used as a quick introduction to combinators.
Kolmogorov Complexity in Combinatory Logic
John Tromp
http://homepages.cwi.nl/~tromp/cl/CL.pdf
And here is a much more technical paper on some advanced stuff translating
an amazing idea of Girard, the geometry of interaction (GOI) in terms
of combinator.
http://www.mathnet.or.kr/papers/Pennsy/Haghverdi/main7.pdf
(Need Category Theory).
Soon I will give the solution of the exercices. I will give you "my second
everything
theory (Year 2127)". Then a third ... I let you meditate on the following
"philosophical"
question "does Kestrel really exist?", doesn't Classical General Relativity
entails the
existence of Kestrels? Does not a "physical" time arrow need kestrels?
Look closely: KXY = X, kestrels eliminate information, Y has been erased).
To doubt on the physical existence of kestrels leads to quasi-physicalist
view of logic
(not unlike the one by *the other Schmidhuber*Strings from Logic:
http://arxiv.org/abs/hep-th/0011065 I tend to think for
now that Newton's lesson can (admittedly roughly) be sum up by saying there
are no
Kestrels. And perhaps the no-cloning theorem gives us empirical reason to doubt
about the Starling too, because they clone (duplicate)
one of their argument (Einstein Podolski Rosen Bell ... Diecks Zurek
Wootters lesson).
In fine combinators provide tools for building models of weak logics.
Strictly speaking
abandoning the kestrel is abandoning the a priori axiom: p->(q->p). This is
a step toward
quantum or toward relevance logics. But I guess I anticipate too much.
I am not hiding you that one of my motivation is to make my thesis easier.
Until now
I have attempt to describe the SHORT path (the interview of the lobian
machine). Now I
will give you the LONG path, including a precise sequences of formal theories.
The result is that Lobian machine should prove that if Kestrels and
Starling exist then
they cannot be *observed* by Lobian machine. Feel free to make comments or
metacomments. I see this thread as an aside thread which I hope will not
perturbate
more general discussions, only that with comp some computer science could
be helpful.
Bruno
http://iridia.ulb.ac.be/~marchal/
Received on Thu Jan 27 2005 - 10:38:42 PST