(in this lecture, we will learn the basic maths that is needed for our first model of computation; this material will be examinable in the December exam)
What is most fundamental feature shared by all models of computation?
All models of computation, I would say, must have a set with a binary relation that models one-step computations.
This is sometimes called Abstract Reduction System.[1] Other names that may be used for the same mathematical structure include graph, dynamical system, transition system, automaton, … [2]
Definition: An abstract reduction system (ARS) is a set together with a relation .
This doesnt look very interesting at first sight. Just a relation on a set? What can we do with this? Certainly not all binary relations are models of computation, so we will be interested in the following in properties of binary relations that are interesting for relations that can be thought of as modelling some form of one-step comptuations.
First note that the elements of can be all kind of different things: numbers, lists, multisets, … I am working with a graduate student on an example where is a set of diagrams … but could also contain the memory of a computer or the cells of a cellular automata.
Second, there are a number of important properties that we can express about ARSs in general. We already have seen the notion of a normal form, which is defined purely in terms of . Indeed, is a normal form if there is no . Let us make a list of some interesting questions to ask (precise definitions follow the examples):
Terminology: If in an ARS, we say that reduces to . This is a way of speaking that indicates that we think of as a one-step computation that, as in equational reasoning, simplifies, or reduces, to . But this expectation is not part of the definition of ARSs, which include examples where is "more complicated" than .
The examples below are not necessarily meant to illustrate the idea of an ARS as a model of computation. Rather they serve at illustrating what is captured by the definitions as they are. While it is not too much of an exaggeration to say that all models of computations are ARSs, the notion of an ARS is too abstract to make sure that all ARSs are models of computation. We will later refine ARSs to TRSs and then to lambda-calculus to get to a narrower class of mathematical models which can be considered satisfactory answers to the question "What is computation?".
is the set of integers and is defined to hold if and divides .
A is the set of finite lists (aka words) over ,
A is the set of multisets[3] over , , , ,
Langton's Ant. Exercise: Can you formalise what is?
In the next lecture we will see that even on the abstract level of ARSs, there is a bit of interesting theory that helps to clarify what happens in the examples.
Notation: We write to mean the reflexive and transtitive closure of and (or maybe ) for the symmetric, reflexive and transitive closure, that is the smallest equivalence relation containing .
When we looked at equational reasoning as in high-school algebra, we studied how equational reasoning progresses by term rewriting. This involved pattern matching in order to determine which rule (or equation) can be applied to any given term. An ARS abstracts from this situation by forgetting the term structure and the pattern matching: While we may still think of the elements of as terms and of as a set of rewrite rules, what we need now can be formulated just in terms of an "abstract" set and a relation . ↩︎
Transition systems and automata usually have a set of labels (the alphabet) and a relation for each label in the alphabet. Much of the same mathematics applies to this generalisation and we may see some of it later. ↩︎
Intuitively, multisets are sets in which an element can appear multiple times. So while the sets and are the same (because they contain the same elements), and are different as multisets. Multisets can also be understood as lists where the order of elements does not matter, that is while the lists and are different as lists, they are the same as multisets (because they contain the same elements the number of times). Mathematically, a multiset is a set (of elements) together with a function (determining how often the element is in ). ↩︎