March 7, 2012
Neil Jones
From a programming perspective, Alan Turing’s epochal 1936 paper on computable functions introduced several new concepts and originated a great many now-common programming techniques. In particular, by treating programs as data, he invented the “universal machine”, nowadays known as a self-interpreter.
We begin by reviewing Turing’s contribution from a programming perspective; and 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 fi niteness due to early binding; and a strong adjacency property: the active instruction is always adjacent to the piece of data on which it operates.