NASA Langley was the birthplace of the U.S. space program where astronauts like Neil Armstrong learned to land on the moon. Everyone knows the names of astronauts, but behind the scenes a group of African-American women were vital to the space program: Katherine Johnson, Mary Jackson and Dorothy Vaughan. Before electronic computers were invented ‘computers’ were just people who did calculations and that’s where they started out, as part of a segregated team of mathematicians. Dorothy Vaughan became the first African-American woman to supervise staff there and helped make the transition from human to electronic computers by teaching herself and her staff how to program in the early programming language, FORTRAN.
The women switched from being the computers to programming them. These hidden women helped put the first American, John Glenn, in orbit, and over many years worked on calculations like the trajectories of spacecraft and their launch windows (the small period of time when a rocket must be launched if it is to get to its target). These complex calculations had to be correct. If they got them wrong, the mistakes could ruin a mission, putting the lives of the astronauts at risk. Get them right, as they did, and the result was a giant leap for humankind.
See the film ‘Hidden Figures’ for more of their story (trailer below).
Continuing a series of blogs on what to do with all that lego scattered over the floor: learn some computer science…what is computation? Using binary.
We’ve been focussing on representing data so far but data on its own doesn’t do a lot. It is when you combine it with computation that things get exciting and suddenly you have something that can change the world. But what is computation? We will start to explore computation using something called cellular automata. They are just one simple way to do computation (of many).
We have seen that a data representation is just a way of storing information using symbols. It just gives meaning to otherwise arbitrary symbols. Those 1s and 0s, red blocks and blue blocks, Xs, Vs and Is could mean anything. Indeed at different times they mean different things: sometimes a particular group of 1s and 0s stand for a number, sometimes the colour of a pixel, sometimes a letter. So symbols become interesting when we give them meanings (and that is an important point to remember).
Computation is also about symbols, but about manipulating them using sets of rules. What do the rules do? Given one or more symbols they tell you to swap those symbols for new symbols. To do computation you just repeatedly apply a given set of rules, starting with some starting symbols and the symbols change and then change again and then change again …
Elementary Cellular Automata
Cellular automata are just a particular kind of rules that apply to grids of symbols (called cells). They were invented by one of the great original computer scientists, John von Neumann along with Stanislaw Ulam in the 1940s.
Elementary cellular automata, which we will look at here, are a simple version where you just have a row of cells (so a row of symbols). There are only two symbols allowed, usually 1 and 0. We will of course use lego blocks as our two symbols instead: a red brick for 1 and a blue brick for 0. A particular row of red and blue bricks is called the state. The rules change the colour of the bricks in the row and so change the state of the cellular automata. Here is an example state of such a ‘machine’ where the rows are 16 bricks (symbols) long (essentially the memory of the machine will be 16 bits long):
An example cellular automaton state consisting of 16 symbols. Traditionally cellular automata have symbols 0 and 1. We use a red block to mean a 1 and a blue block to mean a 0.
Rules
A rule that says if we have RED-BLUE-BLUE then change the middle cell to a RED block.
Now if we are going to do computation, we need rules (essentially a program) to apply that changes the state. The rules of an elementary cellular automaton like this are applied to each lego brick, changing it to a new lego brick. To do so they take the brick on either side into account though. Each rule therefore looks at three bricks at a time and changes (or not) the middle brick.
We can write out the rules using lego bricks too – saying what to do for each pattern of three lego blocks. So we could have a rule that if we have a triple RED-BLUE-BLUE then we change the middle of that triple to RED so that the triple becomes RED-RED-BLUE instead. In lego we could represent this rule as shown right, where we show the new value for the middle cell that changes. (Notice we are now using lego bricks, so symbols, to represent rules: a rule is just data too!)
Now a vital thing about rules for computation is that you MUST give a rule for every possibility. Our above rule only tells us what to do for one of the eight possibilities of those triples of bricks that might occur in each position. We must give 8 different rules, so that whatever pattern we come across we have a rule that says what to do.
Here is one possible set of 8 rules we could use:
A set of rules to define how a cellular automaton will behave.
Altogether, there are 256 different possible sets of rules like this.
Notice that we have ordered our rules using a binary pattern of the triples counting from 0 to 7 as a way to make sure we have covered every possible pattern exactly once and to make it easier to find the right rule. We could write then in any order of course. It would make no difference to what the rules do.
Doing Computation
Now to do computation we just apply the rules we have chosen to every position in an initial state – an initial pattern of red and blue blocks. We start at one end of the row and apply the set of rules in each position finding the one that matches the pattern at that position. Once we find the rule that matches that position, we note the new middle block accordingly, then move on to the next position. Once we get to the end of the row, we know what the whole new state for the automaton will be: we have done one step of computation. For the cell at either end of the row, assume its adjacent value off the end is 0 (so blue for us). At every position the rule applies to the original triple of bricks in the current state, not ones changed by rules applied to other positions: the rules are applied to every position at the same time.
The easiest way to do this with lego is to line up a row of red and blue lego blocks as the initial state and apply our rules as above to get a new pattern of red and blue lego blocks placed below it. That new pattern is the new state of the machine, Here is a step as applied to our random state we gave above.
Calculating Number Sequences
We seem to be just replacing patterns by new patterns. Are we doing anything useful? Of course we could give some simple meaning to these patterns. Interpret the pattern as a binary number and what is happening? We are generating a number sequence. To see this use the above rules on a shorter pattern, starting with a single red lego block at the left hand end, with the rest blue. This is the binary for the number 1 (00001). Apply the rules and we get the number 2 (00010). Apply the rules again and the pattern of lego turns into the binary for 5 (00101), then 8 (01000) and then 20 (10100) and so on…
We have created a machine that does a calculation on a number to create a new number. Let it run and it calculates the whole number sequence. Different rules will compute different number sequences: some perhaps more interesting than others.
Images from numbers
If you think numbers are a bit boring, then instead just give a different meaning to the patterns – as giving the colour of pixels, with each new state giving the next row of an infinite lego pixel picture. Now our rules are generating art. Each rule set will compute a different image as will different starting states (again some images generated will be more interesting than others). Here is what our above rules generate if we start with a single red brick in the centre:
The image generated by our rule if we see it as rules to generate the next line of a lego art image.
This is actually a fractal pattern called the Sierpiński triangle. It contains the same triangular pattern over and over again, and If you create a massive version of it on a large lego board you will see that each triangle has the same pattern within it. It is a beautiful recursive pattern.
Sierpiński triangle Image from Wikimedia by Beojan Stanislaus CC BY-SA 3.0
Apply the rules and create a Lego pixel version yourself.
Explore the different rules
Stephen Wolfram has exhaustively explored all the elementary cellular automata, categorising them and describing their properties. However, that is no reason not to explore them yourself, whether with lego, on graph paper or by writing a program to apply the rules for you.
Of course you do not have to stick to only automata with 2 symbols. Add more symbols / colours of lego blocks (so you will need lots more rules in each set) and explore some more.
There is one cellular automaton, so one rule set (with only two symbols) that is very intriguing. It turns out that, rather than just generate a particular number sequences or pattern as the one above does, it can do absolutely any computation – it is a general purpose machine that can do anything that a modern computer can do…but that is another story.
This post was funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.
Can a robot get cancer? Silly question. Our bodies are made of cells. Robots aren’t. Cells are the basic building blocks of life and come in lots of different forms from long thin nerve cells that allow us to sense the world, to round blood cells that carry oxygen around our bodies. Cancer occurs when cells go rogue and start reproducing in an uncontrolled way. A computer can’t get cancer, but you can allow virtual diseases to attack virtual cells inside a computer. Doing that may just help find cures. That is what Jasmin Fisher, who leads a research group at Microsoft Research in Cambridge, has devoted her career to.
Becoming a medic isn’t the only way to help save lives!
Computational Modelling is changing the way the sciences are done. It is the idea that you can run experiments on virtual versions of things you are investigating. A computer model is essentially just a program that simulates the phenomena of interest. For example, by writing a program that simulates the laws of Physics, you can use it to run virtual Physics experiments about the motion of the planets, say. If your virtual planets do follow the paths real planets do, then you have evidence the laws are right. If they don’t your laws (or the models) need to change. You can also make predictions such as when an eclipse will happen. If you are right it suggests the laws you coded are good descriptions of reality. If wrong, back to the drawing board.
Jasmin has been pioneering this idea with the stuff of life and death. She focusses on modelling cells and the specific ways that we think cancer attacks them. It gives a way of exploring what is going on at the level of the molecules inside cells, and so how well new medicines might, or might not, work. Experiments can be done quickly and easily on the programmed models by running simulations. That means the real experiments, taking up expensive lab time, can focus on things that are most likely to be successful. Jasmin’s work has helped researchers design more effective actual experiments because they start with a better understanding of what is going on. One of the most important questions she is studying is how cells end up becoming what they are, and how this differs between normal cells and cancer cells. Understand this and we will be much closer to understanding how to stop cancer.
This story was originally published here and is an article from CS4FN, a free computer science magazine from Queen Mary University of London which is sent to subscribing UK schools. To find out more please visit our About page. The article was also published in issue 23, The Women Are (Still) Here, on p3.
You can find computer science everywhere – even in popular Solitaire games and puzzles. Most people have played games like Tetris, Battleships, Mastermind, Tantrix and Minesweeper at some point. In fact, all these games have a link to one of the deepest, fundamental problems remaining in Computer Science. They are all linked to a famous equation that is to do with the ultimate limitations of computers.
The sciences have many iconic equations that represent something fundamental about the world. The most famous is of course Einstein’s E=mc², which even non-scientists have heard of. The most famous equation in computer science is ‘P=NP’. The only trouble is no one has yet proved whether it is true or not! There is even a million dollar prize up for grabs for anyone who does, not to mention great fame!
P=NP boils down to the difference between checking if someone’s answer to a puzzle is correct, as against having to come up with the answer in the first place.
You are so NP!
Computer Scientists call problems where it is easy to check answers ‘NP problems’. Ones where it’s also easy to come up with solutions are ‘P problems’. So P=NP, if it were true, would just mean that all problems that are easy to check are also easy to solve.
Let’s take Tantrix rotation puzzles to see what it is all about. Tantrix is a popular domino-type game using coloured hexagonal pieces like the ones in the image. The idea of a Tantrix rotation puzzle is that you place some tiles randomly on the table in a connected pattern. You are then not allowed to move the position of any piece. All you can do is rotate them on the spot. The problem is to rotate the pieces so that all the coloured lines match where tiles meet – red to red lines, blue to blue lines and so on.
Have a go at the Tantrix rotation puzzle above before you read on.
Easy to check?
A solution is here if you want to check it. In fact you can quickly check any claimed rotation puzzle ‘solution’. All you do (the checking ‘algorithm’) is look at each tile in turn and check each of its edges does match the edge of the tile it touches, if any. If you find a tile edge that doesn’t match then the ‘solution’ isn’t a solution after all. How long would that take to check? With say a 10 piece puzzle there are 10 pieces to check each with 6 edges so in total that is 10×6 = 60 things to check. That wouldn’t take too long. Even with 100 pieces it would be only 600 things to check – 10 minutes if you could check an edge a second. So Tantrix rotation puzzles are NP puzzles – they can be checked quickly.
But can you solve it?
The question is: “Are rotation puzzles P puzzles too?” Can they always be solved quickly if you or a computer were clever enough? You may have found that puzzle easy to solve. It is much harder to come up with a quick way that is guaranteed to solve any rotation puzzle I give you. One way would be to methodically work through every combination of tile rotations to see if it worked. That would take a long time though.
There are 6 positions for the first piece (ways to rotate it), but for each of those 6 positions the second piece could be in 6 positions too … and so on for each other piece. Altogether for a 10-tile puzzle there are 6x6x6x6x6x6x6x6x6x6 (i.e., over 60 million) positions to check looking for a solution (and we might have to check them all). If you could check one position a second, it would take you around 700 days non-stop (no eating or sleeping). That is just for a 10-tile puzzle…now for a 100-tile puzzle – I’ll leave you to work out how long that would take.
It is not what computer scientists call “quick”.
How clever do you have to be?
If P=NP is true it would mean there is a quick way of solving all Tantrix rotation puzzles out there, if only someone were clever enough to think of it. If P=NP is not true then it might just not be possible however clever you are. Trouble is no-one knows if it’s true or not…
Tantrix: Solve one, solve them all
We’ve seen how Tantrix rotation puzzles can show what we mean by the question “Is P=NP?” It turns out Tantrix rotation puzzles are also something called ‘NP-complete’. That means it is one of a special kind of problem.
NP-complete problems are the really hard ones. Some are also really important to be able to solve quickly. For example, suppose you are a taxi driver and wanted your SatNav to be able to quickly work out the fastest circular route that went via a whole series of places you wanted to visit (in any order), getting you back home. Simple as it sounds, it is an NP-complete problem. It can’t be done quickly even by a fast computer. The best that can be done is to come up with a good answer not a perfect one – using what’s known as a ‘heuristic’. There are lots of ways of coming up with such good answers – using Swarm Intelligence is one way, for example. The point is none can guarantee the best answer every time.
NP-completeness is important because if you could come up with a quick algorithm for solving one NP-complete problem, computer scientists know how to convert such an algorithm into one that solves all the other NP problems…P would equal NP…Trouble is no one has so far done it…
– Paul Curzon, Queen Mary University of London, 2007
People often say that computers are all around us, but you could still escape your phone and iPod and go out to the park, far away from the nearest circuit board if you wanted to. It’s a lot more difficult to get away from the clutches of computation itself though. For one thing, you’d have to leave your clothes at home. Queen Mary Electronic Engineer Karen Shoop tells us about the code hidden in knitting, and what might happen when computers learn to read it.
If you’re wearing something knitted look closely at it (if it’s a sunny day then put this article away till it gets colder). Notice how the two sides don’t look the same: some parts look like a raised ‘v’ and others like a wave pattern. These are made by the two knitting stitches: knit and purl. With knit you stick the needle through and then behind the knitting; with purl you stick the needle in the other direction, starting behind the knitting and then pointing at the knitter. Expert knitters know that there’s more to knitting than just these two stitches, but we’ll stick to knit and purl. As these stitches are combined, the wool is transformed from a series of waves or ‘v’s into a range of patterns: stretchy stripes (ribs), raised speckles (moss), knots and ropes (cable). It all depends on the number of purls and knits, how they are placed next to each other and how often things are repeated.
Knitters get very proficient at reading knitting patterns, which are just varying combinations of k (knits) and p (purls). So the simplest pattern of all, knitting a square, would look something like:
’30k (30 knit stitches), finish the line, then repeat this 20 times’.
A rib would look like: ‘5k, 5p, then repeat this [a certain number of times], then repeat the line [another number of times]’
To a computer scientist or electronic engineer all this looks rather like computer code or, to be precise, like the way of describing a pattern as a computer program.
How your jumper is like coding
So look again at your knitted hat/jumper/cardi and follow the pattern, seeing how it changes horizontally and vertically. Just as knitters give instructions for this in their knitting pattern, coders do the same when writing computer programs. Specifically programmers use things called regular expressions. They are just a standard way to describe patterns. For example a regular expression might be used to describe what an email address should look like (specifying rules such as that it has one ‘@’ character in the middle of other characters, no full-stops/periods immediately before the @ and so on), what a phone number looks like (digits/numbers, no letters, possibly brackets or hyphens) and now what a knitting pattern looks like (lots of ks and ps). Regular expressions use a special notation to precisely describe what must be included, what might possibly be included, what cannot be, and how many times things should be repeated. If you were going to teach a computer how to read knitting patterns, a regular expression would be just what you need.
Knitting a regular expression
Let’s look at how to write a knitting pattern as a regular expression. Let’s take moss or seed stitch as our example. It repeats a “knit one purl one” pattern for one line. The next line then repeats a “purl one knit one” pattern, so that every knit stitch has a purl beneath it and vice versa. These two lines are repeated for as long as is necessary. How might we write that both concisely and precisely so there is no room for doubt?
In knitting notation (assuming an even number of stitches) it looks like: Row 1: *k1, p1; rep from * Rows 2: *p1, k1; rep from * or Row 1: (K1, P1) rep to end Row 2: (P1, K1) rep to end Repeat these 2 rows for length desired.
All this is fine … if it’s being read by a human, but to write experimental knitting software the knitting notation we have to use a notation a computer can easily follow: regular expressions fit the bill. Computers do not understand the words we used in our explanation above: words like ‘row’, ‘repeat’, ‘rep’, ‘to’, ‘from’, ‘end’, ‘length’ and ‘desired’, for example. We could either write a program that makes sense of what it all means for the computer, or we could just write knitting patterns for computers in a language they can already do something with: regular expressions. If we wanted to convert from human knitting patterns to regular expressions we would then write a program called a compiler (see Smart translation) that just did the translation.
In a regular expression to give a series of actions we just name them. So kp is the regular expression for one knit stitch followed immediately by one purl. The knitting pattern would then say repeat or rep. In a regular expression we group actions that need to be repeated inside curved brackets, resulting in (kp). To say how many times we need to repeat, curly brackets are used, so kp repeated 10 times looks like this: (kp){10}.
Since the word ‘row’ is not a standard coding word we then use a special character, written, \n, to indicate that a new line (=row) has to start. The full regular expression for the row is then (kp){10}\n. Since the first line was made of kps the following line must be pks, or (pk){10}\n
These two lines have to be repeated a certain number of times themselves, say 20, so they are in turn wrapped up in yet more brackets, producing: ((kp){10}\n(pk){10}\n){20}.
If we want to provide a more general pattern, not fixing the number of kps in a row or the number of rows, the 10 and 20 can be replaced with what are called variables – x and y. They can each stand for any number, so the final regular expression is:
((kp){x}\n(pk){x}\n){y}
How would you describe a rib as a regular expression (remember, that’s the pattern that looks like stretchy stripes)? The regular expression would be ((kp){x}\n){y}.
Regular expressions end up saying exactly the same thing as the standard knitting patterns, but more precisely so that they cannot be misunderstood. Describing knitting patterns in computer code is only the start, though. We can use this to write code that makes new patterns, to find established ones or to alter patterns, like you’d need to do if you were using thicker wool, for example. An undergraduate student at Queen Mary, Hailun Li, who likes knitting, used her knowledge to write an experimental knitting application that lets users enter their own combination of ps and ks and find out what their pattern looks like. She took her hobby and saw how it related to computing.
Look at your woolly jumper again…it’s full of computation!
– Karen Shoop, Queen Mary University of London, Summer 2014
cs4fn 
