Models of Computation
There are two parts to this practical, which you can approach in any order.
- Rewriting Systems
- Finite State Machines
The goal at the end of each section is to create your own system to solve a task or problem of your choice. The questions in each section are to help you work towards this goal.
You can work alone or in groups, but I recommend working with others and discussing the answers as you go along.
String Rewriting
Your goal in this section is to create a string rewriting system. The questions will lead you through exploring rewriting systems that I have created and considering how they function. At the end of the section, some directions are suggested for you to create your own rewriting systems.
The Miniputer
Let's play with a simple string-rewriting formal system. This simple example will introduce ideas reused in a more complex example below. There are only two rules:
If we start with the initial word "cat", there are two possible paths its computation can follow. It can either transition to "bat" and stop, or transition to "rat" and stop. That's it.
We are not going to say how it chooses between applying the rule $ c \curvearrowright b $ or applying the rule $ c \curvearrowright r $. Both are possible ways the computation can go.
Starting questions
- The miniputer starts in the state "bat". Can the computation continue or is this a terminal state?
- What is the alphabet of this rewriting system?
- Select a different initial word. What words can the system generate from it?
The Spamputer
Now let's play with a more complex string rewriting system, which I call the SPAMputer. The alphabet of the SPAMputer is the following:
To use this computer, you must start with a string of these characters, the "initial word'. You must then write our another string of characters just below it, the "output word". The output word is the same as the input word, with a single change, determined by a rule, such as:
Read this rule as follows: "Replace any single instance of the substring $s *$ in the input word with $* *$." Read $\curvearrowright$ as "is rewritten as".
The computer has several rules. Each of the rules shown below identify and replace a substring. Only one rule applies at a time. Only one occurrence of the substring is replaced at a time, and this can be any substring. There is no priority among the rules.
| \( s * \curvearrowright * * \) |
| \( s p \curvearrowright * p \) |
| \( * p \curvearrowright p s \) |
| \( p p \curvearrowright p \) |
| \( a p \curvearrowright a \) |
| \( m p \curvearrowright m \) |
| \( m * * * * * * * * * * * * * \curvearrowright a * \) |
| \( a * * * * * * * * * * * * * \curvearrowright m * \) |
SPAMputer example computations
Let us start with the initial word $ a * * p s * $ and continue applying rules until with get a terminal word. One possible computation is shown below:
| Line | String | Rule |
|---|---|---|
| 1 | \( a * * p s * \) | \( s * \curvearrowright * * \) |
| 2 | \( a * * p * * \) | \( * p \curvearrowright p s \) |
| 3 | \( a * p s * * \) | \( s * \curvearrowright * * \) |
| 4 | \( a * p * * * \) | \( * p \curvearrowright p s \) |
| 5 | \( a p s * * * \) | \( a p \curvearrowright a \) |
| 6 | \( a s * * * \) | \( s * \curvearrowright * * \) |
| 7 | \( a * * * * \) |
Try the same computation yourself. Start with $ a * * p s * $ and apply the rules (remember each rule lets you replace a single substring). You might find that you take the same steps as I did or the steps you take might be different but you will always end up with the same terminal word. If you think you've got caught in an infinite loop, start again.
Let us start with the initial word $ m s * p * $ and continue applying rules until with get a terminal word. One possible computation is shown below:
| Line | String | Rule |
|---|---|---|
| 1 | \( m s * p * \) | \( s * \curvearrowright * * \) |
| 2 | \( m * * p * \) | \( * p \curvearrowright p s \) |
| 3 | \( m * p s * \) | \( * p \curvearrowright p s \) |
| 4 | \( m p s s * \) | \( s * \curvearrowright * * \) |
| 5 | \( m p s * * \) | \( s * \curvearrowright * * \) |
| 6 | \( m p * * * \) | \( m p \curvearrowright m \) |
| 7 | \( m * * * \) |
This is not the only path of computation. This tree shows all possible paths that the SPAMputer could follow starting from $ ms*p* $:
Using the SPAMputer
Find the terminal word for the following input words. When doing so, watch the patterns that appear. The rules are not accidental -- they were carefully designed for some purpose. But what?
- $ a s * p s s * $
- $ m * * * * p * * p * $
- $ a * * p * * * * * * * * * * * * $
SPAMputer questions
As you might have guessed, the SPAMputer is a model. Before you go any further through these questions, try and identify what the SPAMputer is modelling. Ask yourself the following questions:
- Are there any patterns that keep appearing?
- What might each word or symbol might represent?
- Look at the initial and terminal words. Are there any mathematical relationships between them?
- Might any of the rules represent anything in particular?
You may not come up with the correct answer -- and that is fine -- but do try and come up with *an* answer, however unlikely. Getting into the practice of this sort of thinking will be very helpful.
Translating the SPAMputer
Let me explain how to translate questions for the SPAMputer. We start with a question like "What is two hours after four am". We follow the rules shown below to get our initial word, in this case $m * * p * * * *$. Once we have run the SPAMputer and got our terminal word, we translate this back into natural language again by using the reverse rules shown below. The terminal string is $m * * * * * *$, which we could translate as "six am".
Rules of Translation
Start with a question of the form "What is [number] hours after [number] [am|pm]" Apply the following rules as we did in the SPAMputer. Finally, move the last character to the beginning of the string. Note that some of these rules replace a substring with nothing (i.e. they delete it).
| English to SPAMputer | SPAMputer to English |
|---|---|
| \( \text{one} \curvearrowright * \) | \( * \curvearrowright \text{one} \) |
| \( \text{two} \curvearrowright * * \) | \( * * \curvearrowright \text{two} \) |
| \( \text{three} \curvearrowright * * * \) | \( * * * \curvearrowright \text{three} \) |
| ... etc. | ... etc |
| \( \text{am} \curvearrowright m \) | \( m \curvearrowright \text{am} \) |
| \( \text{pm} \curvearrowright a \) | \( a \curvearrowright \text{pm} \) |
| \( \text{hours after} \curvearrowright p \) | |
| \( \text{what is} \curvearrowright \) | |
| \( \text{?} \curvearrowright \) |
Reverse this process to translate from the SPAMputer back into natural language. First move the first character to the end of the string, then apply the rules in the figure below.
Translation example
Imagine you wanted to answer the question "What is two hours after one pm?". We would translate this into $ a**p* $. In this form we can apply the rules of the SPAMputer until we get a terminal word. This terminal word is $m***$. We can then interpret this as meaning "three am".
Clock arithmetic with the SPAMputer
Use the SPAMputer to answer the following questions:
- What is ten hours after three am?
- What is one hours after two hours after three hours after four pm?
I have found bugs the SPAMputer before, so don't just guess - do the computation.
SPAMputer calculator
Here is an interactive tool for computing the spamputer. You can adjust any of the rules or add and remove rules. This may help you to answer the questions that follow.
Reasoning about the SPAMputer
Hopefully by now you will have a feel for this strange computer. Answer the following (again the most important thing is that you come up with an answer).
- What computation is the SPAMputer doing?
- Are there any numbers we can't represent in the SPAMputer? Which ones?
- Is there a more familiar way of representing the same computation?
- Can we ask other questions like "what is x hours before y?" or "what is x lots of y hours?"
- Can the SPAMputer be extended to make these work?
There are lots of things the SPAMputer can't do, for instance:
- "what is x hours before y [am |pm ]?"
- "what is x plus y?"
- "is x bigger than y?"
- "is x an even number?"
Pick one of these questions - the hardest you think you can solve - and try and redesign the SPAMputer (and the rules of translation) to be able to answer it.
Finite State Machines
Your goal in this section is to design a finite state machine to solve a problem of your choice. The finite state machine might model a situation, or the finite state machine might generate an output string or transform an input string.
For example,
- Video game AI behaviour
- Lights in a building
- Elevator system
- Parser for a simple language
- Procedural content generation e.g. output a string encoding a map for a game
What limitations with using FSMs do you encounter?
Simple Examples
Imagine a train moves between three stations, A, B, and C. We can express the rules which define how the train can move in the following set of rules:
If the train starts at A, is there ever a state where the train cannot continue? In other words, does it ever reach a terminal state?
Imagine we have a bread maker. Our machine can be in one of four states, Prove, Mix, Cook, and Rest. Mixing is optional (it depends on the type of bread being made), otherwise the steps must proceed in order. When the bread maker starts it is in the Prove state. What state is it in when it stops?
We could plot possible paths through this machine:
Finite State Transducer
Finite State Machines (also called Finite State Automata) can be used to recognise languages. A Finite State Transducer, defines a function from strings to other strings.
For each rule that the finite state machine takes, it outputs a symbol.
| Finite State Transducer Rules | ||||
|---|---|---|---|---|
| Starting state | Input tape: | |||
| State | Input | Go to | Output | |
| Finite State Transducer | ||||||
|---|---|---|---|---|---|---|
| Read head | ||||||
| Input tape | a | a | a | a | a | |
| Output tape | ||||||
| Current state | A | |||||