Monomorphic

Computing is very new as a science. Blaise Pascal devised a mechanical calculator in 1645, but Charles Babbage’s analytical engine, widely considered the first programmable computer, was not conceived of until the mid-19th century. However, it was never constructed (unlike Babbage’s simpler “difference engine”), and even at this time there was almost no theory to go with the invention. Today, the fundamental abstractions of computing and programming are Turing machines and Lambda calculus, described in the 1930’s. So essentially, the theory has had less than a century to mature, and is being viewed by many as a branch of mathematics.

The newness of computing means that we don’t know that much about its role or its applicability outside of devices built specifically for computing, nor do we know if today’s fundamental computing abstractions are the best ones.

Languages and automata are two of the most fundamental ideas in computing. In contrast to human languages, which are informal and rather unsystematic, in computing we often speak of formal languages. Something like the following is an example of a formal grammar:

• Sequence-list: Sequence [ Sequence-list ]
• Sequence: Wake up Action-list Have lunch Action-list Go to sleep
• Action-list: Action [ Action-list ]
• Action: Work | Answer the phone | Attend meeting | Relax

Using this grammar we can model the life of an office worker. We can generate an infinite list of potentially infinitely long “sentences”. The following are examples of valid sentences in the grammar:

• Wake up, Work, Have lunch, Attend meeting, Go to sleep
• Wake up, Work, Have lunch, Work, Go to sleep, Wake up, Work, Have lunch, Work, Go to sleep
• Wake up, Answer the phone, Answer the phone, Answer the phone, Have lunch, Work, Go to sleep

A grammar such as this has a 1-1 correspondence with what is known as a deterministic finite automaton (DFA) – a very simple building block of software and hardware models. A formal grammar like the above is in a sense just a more natural way of thinking about a DFA.

What is the applicability of formal languages outside computing hardware and software?

For one thing, we see them in nature, not least in ferns, which on a miniature level appear to have used the same rules as on the macro level. We see them in trees and flowers. In fact, the formal language paradigm appears to be a very good fit for many natural phenomena. One reason for this might be that formal languages allow rich structures to be constructed from a very small description.

One idea I find fascinating is trying to apply these models to human society: people and institutions. Can we describe the interactions in society as automata and formal languages, and if so, what can we learn about them?