Combinator space

From AEGWiki
Jump to navigation Jump to search

Combinator space are terms of combinators which formed a topology space, it is one kind of program space.

Plain examples

With examples of arithmetic expression space and Church encoding of rational numbers, we can translate arithmetical expression space into a space of terms very intuitively (technically we need handle constructions like Dedekind cut).

One step further

In SKI system,

[math]\displaystyle{ I^n x = x }[/math]


So we can easily add a tail on each point of any arithmetical expression space, each tail is a line of discrete points. So the tail bundle of arithmetical expression space is another geometry construction.

Even further, we notice [math]\displaystyle{ I^n }[/math] here is a group, we can introduce other simple terms groups, to make more examples.

Here we have a program [math]\displaystyle{ \mathbb{D} }[/math] can calculate distance of two terms in corresponding arithmetical expression space, we call it distance-inquiry program [math]\displaystyle{ \mathbb{D} }[/math], this program can introduce a proper topology on a bigger domain of terms than only the Church numerals.

Xi Li pointed out that, the above idea of a distance-inquiry program [math]\displaystyle{ \mathbb{D} }[/math] can only works syntactically, because Rice theorem is the final obstacle. If any extension of the term domain involved semantic properties, it leads to halting problem.

Distance-inquiry program [math]\displaystyle{ \mathbb{D} }[/math] can introduce various fibers on the base of arithmetical expression space.


We need to distinguish the two concepts: geometrical computing system and program space. For example, the billiard system can implement a torfilli gate, so it is a geometrical computing system. Even Babbage's unimplemented design is also a geometrical computing system based on mechanics. But combinator space belongs to the second concept, it is a collection of program which have a non-trivial geometry structure.

If we combine geometrical computing system and program space, can they form a new unified geometry space? are they compatible with each other? what operations are available on the space?