- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bruno Marchal <marchal.domain.name.hidden>

Date: Thu, 27 Jan 2005 16:35:42 +0100

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

Date: Thu, 27 Jan 2005 16:35:42 +0100

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:10 PST
*