Combinatorial Logic

0

Perhaps the most important development in mathematics over the last century is the advent of computers. An important topic that, along with perhaps the more famous lambda calculus, laid the foundations for functional programming languages ​​is combinatorial logic, invented by Moses Schönfinkel in 1920.

In combinatorial logic we have combinators that can be combined to simulate any computer program. Theoretically, different instances of the two combinators named S and K are sufficient. However, additional combinators are usually used to simplify and shorten the program. A set of combinators amenable to a simple conversion of any intended behavior into combinatorial logic is the one containing the six combinators S, K, I, B, C and Y, each of which has a very specific but very simple definition Has.

Remarkably, these six combinators can simulate mathematical objects like numbers, as well as operations on numbers like addition and multiplication. In addition to standard Boolean operations such as AND, OR and NOT, they can also simulate the logic constructs TRUE and FALSE. Amazingly, they can also simulate data structures like pairs and lists.

Last summer, Alexander Farrugia and Giorgio Grigolo attended the second edition of the Summer of Math Expo, organized by well-known YouTubers Grant Sanderson (aka 3Blue1Brown) and James Schloss. Farrugia and Grigolo’s contribution was a YouTube video explaining the basics of combinatorial logic. This video can be viewed here.

This is an impressive feat considering that the numbers to be sorted,

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

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

However, the crude language is expressive enough to allow the implementation of algorithms such as quicksort, a sorting method usually first learned in advanced-level computer courses.

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

Although combinatorial logic is primarily of theoretical interest, this work is evidence that mathematics is at the heart of any computation.

soundbites

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

International: The problem of how to minimize the surface area of ​​a cluster of bubbles was posed by John Sullivan in 1999. According to leading mathematicians, it took at least a century to solve this problem. However, in June 2022, Emanuel Milman of the Technion in Haifa, Israel, and Joe Neeman of the University of Texas published a landmark 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 soundbites, listen to Radio Mocha Malta https://www.fb.com/RadioMochaMalta/.

DID YOU KNOW?

• In one month from this year’s deadline Summer of Math Expothe submitted videos together generated more than seven million YouTube views.

• Although functional programming languages ​​are not used as widely as imperative languages ​​like Python, they are still used in industry. In fact, Erlang functional language was used to implement some features of Facebook and WhatsApp.

• Schönfinkel only published two works in his life. This was due to mental health issues he endured for more than 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 showing that combinatorial logic can be used as a basis for mathematics.

For more information, visit: www.um.edu.mt/think.

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

support us

Share.

Comments are closed.