Combinatorial logic

The advent of computers is perhaps the most significant development in mathematics over the past century. An important topic that laid the foundation for functional programming languages, as well as perhaps more famous lambda calculus, is combinatorial logic, invented by Moses Schönfinkel in 1920.

In combinatorial logic we have combinators, which can be combined to simulate any computer program. Theoretically, various instances of the two combinators called S and K suffice for this. However, additional combinators are usually used to simplify and shorten the program. A set of combinators that lends itself to a simple conversion of any intended behavior into combinatorial logic is one containing the six combinators S, K, I, B, C, and Y, each with a very specific, but very simple definition.

Remarkably, these six combiners can simulate mathematical objects like numbers, as well as number operations like addition and multiplication. They can also simulate TRUE and FALSE logical constructs, in addition to standard Boolean operations such as AND, OR, and NOT. Incredibly, they can additionally simulate data structures such as pairs and lists.

Last summer, Alexander Farrugia and Giorgio Grigolo took part in the second edition of the Mathematics Summer Exhibition, hosted by famed YouTuber Grant Sanderson (aka 3Blue1Brown) and James Schloss. Farrugia and Grigolo’s submission was a YouTube video explaining the basics of combinatorial logic. This video can be viewed here.

This is an impressive feat, given that the numbers to sort,

Subsequently, Farrugia used the Haskell functional programming language to write software that converts a program, written in a very rudimentary language, into combinatorial logic, and then the resulting combinatorial logic expression is evaluated to obtain the required output.

The techniques used to successfully create this software are explained in the previously mentioned YouTube video. Rudimentary constructs such as truth values, numbers, pairs, and lists were also programmed using combinatorial logic, so execution time is slow.

However, the plain language is expressive enough to allow the implementation of algorithms like Quicksort, a sorting method that is usually first learned in advanced-level computer science courses.

This is an impressive feat, given that the numbers to be sorted, the natural order of the numbers, and the list they were in had to be simulated using combinatorial logic before even implementing the algorithm.

Although combinatorial logic is mainly of theoretical interest, this work is proof that mathematics is at the heart of all calculation.

sound clips

Locally: The polynomial reconstruction problem asks whether the eigenvalues ​​of a graph – important in theoretical chemistry – can be reconstructed from those of its vertexless subgraphs. In a 2021 paper, Alexander Farrugia of Junior College, University of Malta showed that this problem is solved for graphs that have more than half of their eigenvalues ​​shared by only one of their vertex-deleted subgraphs.

Internationally: The problem of minimizing the area of ​​a cluster of bubbles was posed by John Sullivan in 1999. According to eminent mathematicians, this problem took at least a century to solve. However, in June 2022, Emanuel Milman of the Technion in Haifa, Israel, and Joe Neeman of the University of Texas published a groundbreaking paper in which they solved Sullivan’s problem for three bubbles in at least three dimensions, and for four bubbles in at least four dimensions.

For more sound clips, listen to Radio Mocha Malta


• Within a month since this year’s deadline Mathematics Summer Exhibitionthe submitted videos have collectively generated over seven million views on YouTube.

• Although functional programming languages ​​are not as widely used as imperative languages ​​like Python, they are still used in industry. Indeed, the functional language Erlang has been used to implement certain functionalities of Facebook and WhatsApp.

• Schönfinkel only published two articles in his lifetime. This was due to mental health issues, which he endured for over 15 years until his untimely death in 1942.

• Haskell Curry rediscovered combinatorial logic a few years after Schönfinkel and continued Schönfinkel’s work. Curry initially focused on demonstrating that combinatorial logic could be used as the foundation of mathematics.

For more information, see:

Independent journalism costs money. Support Times of Malta for the price of a coffee.

Support us

Comments are closed.