Neil Jones (Copenhagen), Alan Turing and 75 years of research in models of computation
Schedule
- Feb. 1, 2012, 11:00 - 12:30
Abstract
From a programming perspective, Alan Turing’s epochal 1936 paper on computable
functions introduced several new concepts, including what is today known as self-interpreters and programs as data, and originated a great many now-common programming techniques.
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 the “blob” MOC: a recent 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.
Next, some of the best-known among the numerous existing MOCs are overviewed
and classified by qualitative rather than quantitative features, paying attention to
two factors of prime importance to programmability and physical realizability:
finiteness (and with respect to what); binding times (of what to what at which
point in a computation’s time). We attempt to establish a list of traits an “ideal”
MOC should process.
Finally, we describe how the blob model differs from an “ideal” MOC, and identify
some natural next steps to achieve such a model.
Keywords : programming, recursion theory, models of computation
Attachments
From a programming perspective, Alan Turing’s epochal 1936 paper on computable functions introduced several new concepts, including what is today known as self-interpreters and programs as data, and originated a great many now-common programming techniques.
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 the “blob” MOC: a recent 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. Next, some of the best-known among the numerous existing MOCs are overviewed and classified by qualitative rather than quantitative features, paying attention to two factors of prime importance to programmability and physical realizability: finiteness (and with respect to what); binding times (of what to what at which point in a computation’s time). We attempt to establish a list of traits an “ideal” MOC should process. Finally, we describe how the blob model differs from an “ideal” MOC, and identify some natural next steps to achieve such a model.
Keywords : programming, recursion theory, models of computation