| |
|
|
|
ThinkArt Lab Animation: A.T. Kelemen© November 12, 1998 Dr. Rudolf Kaehr
Not only in arithmetics with its natural numbers we are involved in the naturality of our basic terms of thinking but also in logic itself. All ways of thinking are founded in a single way of thinking, reducing all possible multitudes to a strict unizity, the famous Ur-Logik. In contrast to arithmetics logic has unfolded itself in a wide range of different logical systems. But there are good reasons to accept the strategy to reduce this plurality back to the singularity of the Ur-Logik.
Combinatory Logic as introduced by Moses Schönfinkel (1924 in Moscow) and independently later by Haskell Curry (1930) was often called Ur-Logik, Schönfinkel's main operator was therefore U. And it was believed that with this Ur-Logik the very fundamental problems of the foundations of logic and mathematics could be solved for ever.
Today combinatory logic plays an important role in the construction of functional programming languages like ML, Haskell, Miranda. Combinatory logic is also crucial for the definition and exploitation of parallelism of functional programs.
As the great logician and magician Raymond Smullyan pointed out in his famous book To Mock a Mocking Bird (1985), combinators are programs and everything a program can do can be done by combinators. This is an enormous statement if we contrast the radical simplicity of combinatory logic with the complexity of programs. Obviously, combinatory logic must have a special power. This power is based in its abstractness which is surpassing our normal attitude to logic and which is not fearing logical paradoxes. Combinatory logic is not founded in ordinary language and perception (Anschauung) but in formal and formalist thinking and scriptural construction.
Philip Wadler. Evans and Sutherland Distinguished Lecture, University of Utah, 20 November 2002.
"Whether a visitor comes from another place, another planet, or another plane of being we can be sure that he, she, or it will count just as we do: though their symbols vary, the numbers are universal. The history of logic and computing suggests a programming language that is equally natural. The language, called lambda calculus, is in exact correspondence with a formulation of the laws of reason, called natural deduction. Lambda calculus and natural deduction were devised, independently of each other, around 1930, just before the development of the first stored program computer. Yet the correspondence between them was not recognized until decades later, and not published until 1980. Today, languages based on lambda calculus have a few thousand users. Tomorrow, reliable use of the Internet may depend on languages with logical foundations. "
http://homepages.inf.ed.ac.uk/wadler/topics/history.html#drdobbs
1 Disseminations of Combinatory Logics
Following E. Engler, (1983) combinatory logic as a proof theoretical system is build by language, axioms and rules. Combinatory logic is a system, or more exactly an algebra A = (A, *, S, K), therefore we can disseminate this algebra in a way we have introduced before by means of the proemial relationship.
The algebra A consists of the formulas A, the application "*", and the combinators "S" and "K". The terms of the language are build by atomic terms, with variables x, y, z...and the constants S and K and the binary application "*" of the combinatory algebra. Formulas are equations between terms. The universe of combinatory logic is single-sorted or untyped. That is, in this term algebra there is no distinction between functions and their arguments-except that * interprets the first expression as a function and the second as the function´s argument (R.W. Stark)
The deduction rules are the rules of equality.
Again, it maybe helpful to put the skeleton of combinatory logic together in a conceptual graph which visualize the conceptual dependencies of the main notions of the system of combinatory logic.
Diagramm 1
Conceptual Graph of CombLogic System
Equality: equations are formulas, Operator: application *, Constants: S and K.
The operational conceptual graph deals with the dependencies of operator and operand of combinatory operations (formulas).
Diagramm 2
Operational Conceptual Graph of CombLogic
Combinators figures always in two different roles, one as operators and the other as operands. The whole term then is therefore the result of the application of an operator to its operands, that is an operation which is an application.
As a meta-theoretical result, the consistency of the combinatory system is provable.
There exists one and only one combinatory logic, thus Combinatory Logic is founded in the unizity of 1. The consisteny of the system gives a strong argument for its unizity.
As an abstract algebra combinatory logic is build up by the well known tectonics of "name(s)", "sorts", "operations", "equations". The basic module of the abstract algebra in a polycontextural setting includes "contexture", "super-operators". Therefore, the combinatory tectonics is reduced to the special type of: contexture is 1, super-operator is ID, and name is Combinatory Logic, sorts are one, the entities E, with constants K, S, I and opn is *, and eqns are "=".
Diagramm 3
Basic Modul
Because combinatory logic is an algebra A = (A, *, S, K), we can disseminate this algebra in a way we have introduced before by means of the proemial relationship.
The new polycontextural algebra of combinatory systems consists of the distributed original algebras and a set of super-operators {ID, PERM, RED, BIF} between these algebras.
By a conservative dissemination of combinatory algebras I understand a dissemination which is preserving the type-structure of the algebras, that is, conservative dissemination produces a strict parallelism of the combinatory systems. A conservative dissemination is a very special case of the general unrestricted dissemination of combinatory algebras including all possible transformations between different types.
Diagramm 4
Conceptual Graph of combined CombLogics
Meta-theoretical considerations about the disseminated combinatory logics like consistency etc. are not touched by the process of cloning. Each cloned or colored system inherits all the meta-theoretical merits of its original system. Even if the original maybe lost, or not easy to distinguish from its clones.
2 Toward combinatory poly-logics
After having convinced myself about the naturality of multiple beginnings I feel free to start our Ur-Logik simultaneously at different ontological places at once.
To give a introductory idea about a possible poly-contextural combinatory logic derived from the proemial distribution of classical combinatory logic I propose some constructions.
Poly-contexturality means that there are entities, atoms, objects belonging to different universes, all mediated together to build a complexity of combinatory logics. Classical combinatory logic which is obviously mono-contextural has only one global domain, its universe, the domain of PC-based combinatory logic is not a uni-verse, but a pluri-verse (or multi-verse).
In the mono-contextural setting we are only considered with elements belonging to their universe. Elements not belonging to U don't exist, therefore they have not to be studied, at least not at the beginning of the construction of the system. All elements which belong to their universe, and only one universe exists anyway, are elements which are identical with themselves, which means they exists, because elements which are not identical with themselves don't exist. This is surely a heavy-weight ontological assumption.
Existence is expressed by identity, or equality. Therefore the rules of equality of elements and combinations of elements has to be considered.
This situation has to be transformed into the poly-contextural constructions.
Because in a poly-contextural situation there are several universes the question arises to which universe an element belongs and to which universes it doesn't belong.
The situation is similar to the question of belonging to a specific type or not. But here we are dealing with the very basic fundaments of the calculus, and not with a meta-level construction.
It is true, or it is the case that x belongs to the universe U1 means x =1 x, to shorten this wording we can write T1x1, short T1x.
If someone has a problem with the numbering of the different Ur-Logics and thinks I am reducing the whole construction back to the linearity of our unique natural numbers, don´t worry. First which number system do you mean. Here we are offering more than a handful of different possibilities to chose one of the many natural number systems.
But equally I would say, yes, you are right! I am using numbers to number these Ur-Logics, but again, if I mention or thematizing these numbers, they are invited to their own contexture and respected as members of their own arithmetic system, different to the counted number systems before. Therefore, there is no privileged number system. What is first and what is second in a temporary hierarchy is based only in its functionality, in its role in the complex game and not by any kind of primordial substantiality may it be as formal as possible.
What is not an atomic element of U1 is as such an atomic element of U2, what is not an atomic element of U2 is also not an atomic element of U3, and what is an atomic element of U1 is also an atomic element of U3. All that at once, not in the sense of set theory but in the sense of mediated atomic elements.
x(3) = (x1, x2, x3), more explicit because it is not a tupel but a mediation and again visualized in the diagram below.
If we want to be interested in the elements which don't belong to the universe2 and the universe3 we simply have to introduce a new universe, say universe4 to positively localize these elements, which are not existent in the former constellation. Non-existence means, existence in another universe.
Therefore, no element is lost, each has a place to be. There is no Heimatlosigkeit in polycontextural systems but also no letztendlicher origin.
Combinatory logic as a calculus has also its linguistic rules. Not every possible combination of the atomic elements are allowed, also there are rules about technical signs like brackets. Therefore a calculus consists of expressions which can be well-formed or ill-formed, but it is dealing only with the well-formed expressions. As usual, from all the possible concatenations the well-formed have to be cut out. And further, not all well-formed expressions are theorems, they have to be cut out by the axioms and rules of the calculus. What we see is the tectonic, a hierarchically ordered system of linguistic levels.
Additionally to the approach of disseminating systems by means of proemiality, distribution and mediation, we can model this procedure in the category framework of logical fibering. This approach is well known by the work of Pfalzgraf (1988 - ). Maybe it is possible and helpful to make the distinction that the disseminatory approach is corresponding more to a proto-theoretical thematization whereas the category theoretical approach reflects more a meta-theoretical point of view.
(BIF, ID, BIF) ((K1, K2, K3) (x1y1, x2y2, x3y3)) ==>
((x1, #, #), (x1, x2, x3), (#, #, x3))
Diagramm 5
Transcontextural transitions of (BIF, ID, BIF)
In logical semantic tranjunctions as we know them togetherness is organized by splitting the function into its partial parts. These parts are (more or less) disjunct resp. to their values. Therefore this type of togetherness is not depending on the metaphor of cloning but on the metaphor of splitting (of total function into its partial functions) too.
But even for logical transjunctions this emphasis of splitting in contrast to cloning and "gluing" is not the whole truth. Also transjunctions are highly over-determined, their truth-values are belonging simultaneously to different logical sub-systems
(T1, F1) trans==> (F2,3, F2,3). In this case F belongs at once to two sub-systems, S2 and S3. A similar over-determination is produced for the values which are involved in the conditions of mediation of the sub-systems.
As we know, combinatory logic is not only consistent but complete, it is a sound system.
To add any new combinators runs-from purely fomalistic point of view-into a dilemma. If the system should keep its consistency, a new combinator would not be of great novelty, because it could be defined with the existing combinators S and K. If this extension would introduce into combinatory logic something irreducible new it would destroy the soundness of the system.
If in parallel programming, operators like par and seq are introduced, they are in the dilemma of being reducible if they don't wont to destroy the system. Are the parallel combinators strict od non-strict?
Parallelism is introduced in GPH by the par combinator, which takes two arguments that are to be evaluated in parallel. The expression p `par` e (here we use Haskell's infix operator notation) has the same value as e, and is not strict in its first argument, i.e. bottom `par` e has the value of e. (bottom denotes a non-terminating or failing computation.)
Its dynamic behaviour is to indicate that p could be evaluated by a new parallel thread, with the parent thread continuing evaluation of e.
We say that p has been sparked, and a thread may subsequently be created to evaluate it if a processor becomes idle. Since the thread is not necessarily created, p is similar to a lazy future [MKH91].
Nevertheless, it is highly reasonable to introduce by definition new combinators especially for economic reasons. It would be nearly impossible, at least for a human logician, to deal with only the minimal set of operators, like K and S.
Proemiality is concerned with the cloning of the natural as it appears in arithmetics or in logics. Therefore, questions of efficiency don't matter on this level of thematization. Thus, it seems that there is no chance of changing or extending fundamental systems then by keeping their soundness and disseminating the system as such. In this sense, cloning or disseminating seems to be the only chance of escaping the narrowness of the pre-given naturality.
Obviously this approach of disseminating the naturality of the classical system is not involved in any manoeuvres of the heterodoxy of deviant or alternative or wild or non-orthodox strategies of what ever color. Again, this doesn't exclude that contextures can be involved in all sorts of non-classical systems and even in the distribution of different non-classical systems in the polycontextural framework. Combining different classical and non-classical systems are a new possiblity of PCL-systems.
2.1 Disseminating the successor function
As an example we are disseminating the graph of the successor function SUCC as defined by succ n = n + 1 over two loci. The function SUCC is defined by add and the tags @ are representing the application.
Diagramm 6
Graph der Funktion succ
Because the distribution is monoform, that is type-preserving, this distribution is conservative and shows a certain parallelism of the involved terms.
SUCC(2) with succ1 n = n + 1 .simul. succ2 n = n + 1
Diagramm 7
Graph of two distributed SUCC-Functions
(BIF, ID, BIF) (succ, succ, succ) (n, n, n) ==>
(succ n, #, #) § (succ n, succ n, succ n) § (#, #, succ n)
2.2 Two faces of the self-applicability of Y
A polycontextural explication of the self-application of the Y-operators has to distribute its application over two places, where the exchange between operator and operand is realized. With a cut in the very concept of identity the Y-operator is simply dealing with its two possible states as an operator and as a operand. These two states have to be realized simultaneously and this can be done by a dissemination over the two simultaneously existing systems.
A strict formalist point of view would exclude the distinction of Y as an operator and as an operand and argue that Y is a combinator and is applied on itself and nothing else.This PCL-construction doesn't exclude self-application in the mode of identity. This can happen freely in each contextural system locally.
If chiasm is a primary structure of pcl-systems, and the Y combinator can be understood in PCL as a chiastic operator, why shouldn't we take Y as a primary, not derived operator?
Self-referentiality in combinatory logic is secondary, in the theory of living systems self-referentiality is of primary character. This insight was the reason for the different formal approaches to self-refernetiality and circularity, especially by Francisco Varela to formalize the autopoietic and autonomous structure of living systems byond the classical cybernetic approaches of feedback loops and self-organiszation..
In PCL, circularity is interpreted as a chiasm. The slogan I introduced at this time of "Circulus Creativus" (v. Foerster) was "Not all circles goes round." ("Nicht alle Kreise gehen rund.")
Operators like S, K, I are not self-referential, but hetero-referential. They refer to there terms and not to themselves even if the terms consists of themselves. They will occur in a finite chain of superpositions referring to there operands. Self-applicability and superposition of operators is not the same as self-referentiality of operators.
The SKI-system is not only complete it also allows to define operators like Y without producing any inconsistencies inside the combinatory system.
On this probably most formal level we can study the underlying identitive formalist ontology of combinatory logic, Curry´s general theory of OBS.
Also there is a strict hierarchy between the notion of operator and operand for the formulas and applications of SKI, the Y operators forces to abstract from this distinction, because Y is at once considered as operator and as operand. But from a graphemic point of view this is an abstraction, denying the actual inscriptions of the calculus. Again, it is said that Y applies to itself. The presupposition is that Y is as an operator identical to itself. This may be true in a purely formalistic context which denies the behavioral aspect of the construction: Y as an operator and Y as an operand, roles be played by Y in the game of self-application.
To deny this difference means to realize an abstraction from it and this is a mental procedure. That is, the abstraction is not inscribed but thought by the logician. Maybe here is one of the reasons why combinatory logic was called idealistic by the materialist dialecticians of the former Soviet Union.
Finally, a PCL understanding of the mechanism of the Y operator can offer two graphematical realizations of it. One is the chiastic modelling of the functional change between Y as an operator and Y as an operand distributed over two logical loci, that is over two contextures. And second, the inscription of the abstraction from this chiastic mechanism in a third contexture mediated by the two first contextures which corresponds the purely formalist approach of Haskell Curry.
The PCL understanding of the Y operator doesn't deny the typefree construction of combinatory logic.
For historical reasons I mention this:
"We can no longer "explain" a paradox by running away from it; we must stand and look it in the eye. Something is gained by the mere bringing about of this state of affairs. The paradoxes are forced, so to speak, into the open, where we can subject them to analysis. This analysis must explain the fact that F(F) does not belong to the category of propositions, an explanation which comes within the province of combinatory logic as here conceived." Curry, Feys, 1956/67
(Similar wording by Heinz von Foerster and Varela)
The new turn would be to define the hetero-referential combinatory S, K, I by means of chiastic self-referential operators, like "Why". It would be possible to distinguish between derived self-referentiality, Y defined by combinators, and fundamental or architectonic self-referentiality, not reducible to hetero-referential combinators.
In other words, the super-operator (ID, PERM, RED, BIF) which are applied on the combinatory operators S, K, I for reasons of dissemination, have to be involved into the construction of a PCL-based combinatory logic.
http://www-fp.dcs.st-and.ac.uk/~kh/papers/pasco94/pasco94.html
http://burks.brighton.ac.uk/burks/pcinfo/progdocs/plbook/function.htm
http://www.di.unipi.it/ricerca/Report2002/node64.html
http://nfocentrale.net/miser/readings/
http://www.andrew.cmu.edu/~cebrown/notes/barendregt.html
http://www.haskell.org/humor/
http://www.angelfire.com/tx4/cus/combinator/birds.html
|
ThinkArt Lab http://www.ThinkArtLab.com sales@ThinkArtLab.com |
| |
|
|
|
