PROGRAMS = DATA = FIRST-CLASS CITIZENS IN A COMPUTATIONAL WORLD

From a programming perspective, Alan Turing’s epochal 1936 paper on computable functions introduced several new concepts, originated a great many now-common programming techniques, including the invention of what are today known as self-interpreters, using programs as data.

We begin by reviewing Turing’s contribution from a programming perspective; and then systematise and mention some of the many ways that later developments in models of computation (MOCs) have interacted with computability theory and programming language research.

Next, we describe our “blob” MOC: a recent biologically motivated stored-program computational model without pointers. Novelties of the blob model: programs are truly first-class citizens, capable of being automatically executed, compiled or interpreted. The model is Turing complete in a strong sense: a universal interpretation algorithm exists, able to run any program in a natural way and without arcane data encodings. The model appears closer to being physically realisable than earlier computation models.  In part this owes to strong finiteness due to early binding; and a strong adjacency property: the active instruction is always adjacent to the piece of data on which it operates.