Cyber Security at the movies: Catwoman

SPOILER ALERT

A cat sat on a branch silhouetted by an orange moon — Image by bess.hamiti@gmail.com from Pixabay

The 2004 film Catwoman, starring Halle Berry as Patience Phillips (and Catwoman), has been voted as one of the worst films of all time, and has won multiple Razzies (Golden Raspberry Awards) – Halle Berry accepted hers while holding her Best Actress Academy Award. Now, however, it has a bit of a cult following. It did at least feature an African American woman as the lead, in a superhero film, possibly for the first time, and came long before Black Panther. Whether it deserves either accolades or condemnation, it certainly features some of the worst cyber-physical security seen in a film by a corporate giant. So what can we learn about cyber-physical security from the film?

The weakest link

The plot is based around the cosmetics firm Hedare Beauty and its development and product launch of a new face cream that reverses the affects of aging. Clearly, a big corporate player, the firm has a massive team at their headquarters that includes artist Patience working on PR, but also a massive research and industrial complex, developing testing and manufacturing its products. Now, cyber-criminals do not just include hackers out to cause anarchy or extort money from people, they also include people working for companies, sometimes supported by their countries, doing industrial espionage: trying to steal research and development secrets. By stealing the designs or product formulae of their competitors, such companies aim to save the massive time and development costs of doing it themselves. They then quickly produce rip-off products to steal the market. Gaining secrets can also gain criminals advantage through insider trading, buying and selling shares, so making money on the back of secret information about what is about to happen. Companies, therefore, have to take industrial espionage seriously, and that means taking cyber-security seriously too.

In Catwoman, the company, Hedare Beauty, have the normal kinds of industrial secret but also a big nasty one too, so their bosses have even more reason to put a lot of effort into security. They certainly have lots of heavies with guns looking to shoot people. However, their physical security is actually totally lax.

This is first seen when Patience’s love interest, Detective Tom Lone, merrily walks into the corporate headquarters and up to her open plan desk where she is working on the product launch to ask her for a date. How did he get in? Why isn’t anyone accompanying him in such a sensitive area especially days before a crucial launch? Where is his visitor’s pass and why isn’t he being challenged. Perhaps this can be put down to being a cop (perhaps he waived his badge about) but still someone senior should have accompanied him surely (and is returning Patience’s purse (his excuse) really a good enough reason to bypass security whoever you are?)

However, even if we let that go, later Patience has to deliver some artwork by midnight to the boss out at the industrial complex. That is where the real secrets, good and bad, are. When she gets there the foyer is locked and dark with no one on duty. In many thrillers, the heroes have to use sophisticated gadgets, amazing technical or physical skill, or subterfuge to overcome the massively sophisticated hi-tech security. Patience, by contrast, just wanders round the back looking for another way in and finds a fire door ajar. This allows her to both enter and ultimately make it to the heart of the building where secrets are being discussed. As a result she overhears (if accidentally) something she should not hear…

Perhaps the most important principle of cyber-security is that it is as weak as its weakest link. You can have all the high tech multi-factor biometric authentication systems, impossible to crack encryption, experienced and well-trained former SAS guards patrolling the foyer, and so on, but if you leave a back door open then the criminals will just ignore all your high tech security and walk in through that one back door. That is exactly what Patience does. There is no point as, for example, I have seen in real life, checking everyones access cards on a main gate, when there is an un-manned side gate. The criminals aren’t going to even try to enter through the front gate. Likewise, if you have a weak point in your cyber-security system, it does not matter how massively strong the rest is.

It is also better to think not of just cyber-security, anyway, but of cyber-physical security. The weakest links can just as easily be to do with physical security as with the computerised part – like the open door Patience found, or letting someone claiming to be a Detective to walk around anywhere in the building. Once the “Detective” is in, they can gather information to launch other attacks from other weak points they now have access to (like passwords written on post-it notes, an access card left on someone’s desk, or computers left unlocked, for example). So poor physical security can be the weak link allowing a backdoor into the computer system.

Another point from the film is that, whether cyber security or physical security, just being “inside” (a computer or a building) should not give access to everything. As you move through a building or through a computer system, there should be more locks to get through, more authentication tests to pass, with different levels of access for different people

Patience should never have got into the building, but even if she had, she shouldn’t have got further than the corridor. Luckily (!) for her, she did with the ultimate result that she gained superhuman powers and became Catwoman, so perhaps sometimes bad security is not all bad (if only in a world where people can gain superpowers from cats).

Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

Pseudocode Poems

A purple flower with dew drops — Image by AdelinaZw from Pixabay

Pseudocode poems are poems that work both as a poem and as an algorithm so can be read or executed. They incorporate sequencing, selection or repetition constructs and other kinds of statements to take actions. You can implement them as an actual program. Below are our attempts. Can you write better ones?

Poems often use the ambiguity in language and aim to affect emotions. Pseudocode is intended to be precise. Programs certainly are. They do something specific and have a single precise meaning. Writing pseudocode poems that do both can be a lot of fun: just like writing normal programs is. The idea was inspired by Bryan Bilston’s poem ‘Two Paths Diverged’. Read it here or buy his wonderful book of poems, ‘ You took the last bus home’.

I am not a great poet, but here are some of my attempts at pseudocode poems to at least give you the idea. They are, in turn, based on the core control structures of Sequencing, Selection and Repetition. They also use print statements and assignments to get things done,

Sequencing

This pseudocode poem is based on sequencing: doing things one after the other.

What am I when it’s all over?

I am dire.
I am fire.

I am alone.
I am stone.

I am old.
I am cold.

We use the verb TO BE to be the equivalent of assignment: setting the value of a variable. Here it is implemented as a Python program.

def whatamI():
	"""What am I when it's all over?"""

	I = 'dire'
	I = 'fire'
	
	I = 'alone'
	I = 'stone'
	
	I = 'old'
	I = 'cold'
	
	print(I)

Selection

Here is a pseudocode poem based on selection, which is the second core control structure. It chooses between two option based on a boolean test: a true / false question. The question here is: do I love you? Dry run the algorithm or run program to find out.

Violets are violet
if roses are red and violets are blue
then
    Life is sweet
else
    I love you

Here it is implemented as a Python program (with appropriate initialisation).

def violetsareviolet():
	"""Violets are violet"""
	roses = 'red'
	violets = 'violet'
	
	if roses == 'red' and violets == 'blue':
		print('Life is sweet')
	else:
		print('I love you')

violetsareviolet()

Find out more about Selection based pseudocode programs via our computational literary criticism of Rudyard Kipling’s poem “If”.

Iteration or Repetition

The final kind of control structure is iteration (i.e., repetition). It is used to repeat the same lines over and over again.

Is this poem really long?

it is true
while it is true
    this is short
it is endless

Here it is implemented as a Python program.

def isthispoemreallylong():
    """Is this poem really long?"""
    it = True
    while (it == True) :
        this = 'short'
    it = 'endless'

isthispoemreallylong()

Can you work out what it does as an algorithm/program, rather than as just a normal poem? You may need a version with print statements to understand its beauty.

def isthispoemreallylong2():
    """Is this poem really long?"""
    it = True
    while (it == True) :
        this = 'short'
        print("this is " + this)
    it = 'endless'
    print("it is " + it)

isthispoemreallylong2()

The word while indicates the start of a while loop. In the pseudocode, it is a command to repeat the following statement(s). It checks the boolean expression after the body each time. Only if that boolean expression is false does it stop. In this case the body sets the variable named this to string value ‘short’. The test is about a different variable though which is not changed inside the loop, so once in the loop there is nothing that will ever change the variable it so the value of the test will always be the same. Variable it will always be True and the loop will keep setting variable this to value ‘short’, over and over again. This means the loop is a non-terminating loop. It never exits so the lines of code after it are never executed. As a program they are never followed by the computer. The variable it is never set to the value ‘endless’.

Overall the poem is short in number of lines but it is actually endless if executed. It is the equivalent of a poem that once you start reading it you never get to the end:

it is true 
check it is true 
this is short
check it is true 
this is short
check it is true 
this is short
...

Here is a more romantically inclined poem for Valentine’s day (since at the time of writing, it is coming up) again using repetition

My love for you is endless

my love is true
while my love is true
    I love you

Here it is implemented as a Python program.

def myloveforyouisendless():
"""My love for you is endless"""
my_love = True
while my_love == True:
    print('I love you')

myloveforyouisendless()

In the pseudocode of this poem the verb “to be” is used for two different purposes: as an assignment statement (it is true is used as a statement to mean it = True) and as a boolean expression (it is true is used as a boolean expression to mean it == True). As an assignment it is used as a command to do something. As an expression it is something representing a value: it evaluates to either true or false. Confusing these two English uses is a common mistake novices make programming, and shows one of the ways why programming languages are used with different symbols for different meanings, rather than natural languages.

Now it is your turn. Can you write a great poem that can also be executed?

Paul Curzon, Queen Mary University of London

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

Answers

The selection poem is about a volcano, but the answer to the question in the title is ‘cold’.
Assuming you agree with me that violet flowers are violet (or at least not blue) then clearly we are compatible at least in being pedantic and you will find I love you.

If: a computational literary criticism

If, by Rudyard Kipling is an inspirational poem that was voted the UKs favourite poem in the 1990s. It consists of a series of lines that start with If. What If, by Benjamin Zephaniah is a more subversive poem modelled on the original.

If statements, of course, are a really core part of programs so are these poems, given they are all about IF, algorithms? The use of If here isn’t quite the same as a pure computational one as seen in programs. For a start, it doesn’t follow the structure of a computer science IF statement. Here are a few lines:

If you can keep your head when all about you
  Are losing theirs and blaming it on you,
If you can trust yourself when all men doubt you,
  But make allowance for their doubting too;
...

In programs, an IF statement has a specific structure. It consists of a test of something that is true or false but then gives a specific action to take when the statement is true. The lines

you can keep your head when all about you are losing theirs AND blaming it on you,

is more or less such a true or false statement. Either you can keep your head or you can’t. This though ignores the possibility of you sometimes losing your head and sometimes not. The poem presumably means to say that you must ALWAYS keep your head. What exactly does “when” here mean too? The reason we do not use English when writing programs is the lack of clarity of what is actually meant. Programs are mathematically precise in their meaning. They do only have one possible meaning (and that is the point). this is also a potential issue of writing programs by instructing AIs over what you want in English!

This boolean expression (something that evaluates to true or false) also uses a logical connective AND just like in a program – you must both be keeping your head AND people must be blaming it on you for the whole to be true. If they are both true then the action that follows is taken, but if they aren’t both true the poem says nothing about you!

Another issue in If, is that this test / boolean expression is not immediately followed by an action to do when it is true. The action comes right at the very end of the poem

...
Yours is the Earth and everything that's in it,
And - which is more - you'll be a Man, my son!

This comes after a whole series of these partial IF statements. To make it more clearly like a program you would add a more explicitly IF-THEN structure, which is the equivalent of putting ANDs between all the tests. In a program that would be written more like the following:

IF you can keep your head when all about you
  Are losing theirs and blaming it on you,
   THEN IF you can trust yourself when all men doubt you,
              But make allowance for their doubting too;
...
...
                             THEN Yours is the Earth and everything that's in it,
                                        And - which is more - you'll be a Man, my son!

Only if all the tests are true does the final action get taken. Though it isn’t really an action, it is more an assertion that something else is true – “the Earth is yours”, rather than “we give you the Earth”. (Also that final And is no longer a logical connective!)

Poems like this could be made more explicitly computational though. For example, a slightly more computational version might be:

IF you can keep your head when all about you
   Are losing theirs AND blaming it on you
THEN I will thank you, giving you a pay rise too
...

A love poem in this vein might start

IF you are a snail 
    THEN I will become your shell.
IF you are a ...

This leads on to the idea of pseudocode poems, that use other computational constructs. More of that to come.

To do …

Write your own poem in this style with true/false questions followed by specific actions, modelled on the computational version of IF. It could be a reworking of If itself or a completely different poem.

Great Fleas… a poem about recursion

A flea — Image by Doğan Alpaslan Demir from Pixabay

Computer scientists and mathematicians can be poets too, even writing poems about computation. One of my favourite poems is about recursion and was written by the Victorian logician Augustus De Morgan who is famous for his laws of boolean logic that are a mainstay of reasoning about boolean tests in programs.

Great fleas Have Lesser Fleas,
upon Their backs To Bite’em,
And Lesser Fleas Have Lesser fleas,
And So, Ad infinitum.

and Those great Fleas, Themselves, In turn
Have Greater Fleas To go On;
while Those Again have Greater still,
And greater Still, And So on.

– Augustus De Morgan

Recursion, solving problems by breaking them into smaller versions of the same problem, is a way of writing programs that repeat just using function call (no while loops or for loops needed). It is a core concept of the programming paradigm, functional programming. Using recursion in a way that goes on forever as in the poem leads to non-terminating programs.

De Morgan was also Maths tutor of Victorian mathematician and computer scientist, Ada Lovelace. Her father was the great poet Lord Byron though (philistine that I presumably am) I like De Morgan’s poem better than Byron’s.

De Morgan made the idea of mathematical induction rigorous. It is the basis of how you prove recursive programs (and iterative ones) are correct.

Paul Curzon, Queen Mary University of London

Lego Computer Science: Programming Creativity

White lego buildings rising from rubble — Image by Paul Curzon taken at Tate Modern London at Olafur Eliasson’s “The cubic structural evolution project” exhibition, 2019.

My absolute favourite example of interactive art is Olafur Eliasson‘s “The cubic structural evolution project” back in 2019 at Tate Modern. It was “just” two piles of standard white Lego bricks piled on two tables (but a tonne of Lego between the two …so a LOT of Lego). Anyone visiting the exhibit was invited to sit down and help create a city by building a building … and it was joyfully creative. Kids and adults mixed together building great architectural wonders, big and small, out of the bricks. Sometimes intentionally, but often accidentally, an existing building was demolished, but that was just an opportunity for new amazing buildings to emerge from the rubble. We visited twice that summer, and each time a totally different city was there that had emerged from this constant evolution of building. On each visit we built something new ourselves to add to the ever changing city.

The exhibit took Lego back to its roots – no instructions, no specific creation to reproduce, just the bare building blocks of creativity. You can still buy generic lego sets of course (if not with the same scope as a tonne of bricks). However, the high profile modern Lego sets are now used to build a specific thing designed by someone else, like a Star Wars Tie fighter, a Death Star, a Ferrari, a parrot or perhaps Notre Dame. This is one form of creativity – you are definitely creating something, and doing so gives you an amazing feeling of accomplishment and well-being. I strongly recommend it and of doing similar activities whether doing a tapestry, or building a jigsaw, or … It is good for your happiness and mental health more generally. But you are creating just by following instructions. In computer science terms, you are acting as a computational agent, following an algorithm that if followed precisely guarantees the same result every time (an exact copy of the lighthouse on the box perhaps…). A computer (with a suitably good robotic arm and vision system) could do it. That is the point of algorithms! They take no thought just an ability to follow instructions precisely: the thing computers are good at.

There is another sense we mean when we talk about creativity though and that was the original Lego idea. You have the bricks. You can build anything. It is down to you. Create something new! According to an exhibition on the history of play I went to early construction kits like the original Lego inspired a whole generation of architects to do completely new things with buildings (if you know your architecture think especially Frank Lloyd Wright whose mother bought him educational blocks called the Froebel Gifts, or perhaps Denys Lasdun – I lived in one of his “Lasdun building” block like buildings for a year in my younger days).

This kind of pure creativity is what being a programmer is about. Not just following instructions to create someone else’s creation, but creating your own totally novel, wondrous things from simple building blocks (and you don’t have to be part of the Lego design team to do it either). That is the lesson that collaboratively emerged in Olafur Eliasson’s exhibit over and over again. Just as the inventor of Lego, Ole Kirk Christiansen, in creating the toy went to yet another level of creativity in doing so, Olafur Eliasson did so to in creating the exhibition. They both created the opportunities for others to be creative.

Programming languages are very much like Lego in this sense. They just provide the building blocks to create any program you want. Learn how to use them and you you can do anything if you have the imagination as well as having built the skill. The different constructs are like different kinds of Lego bricks. Put them together in different ways and you create different things. You can stick with the basics and still build amazing creations even without learning about all the libraries methods that act like specialist bricks designed for specialist purposes. And of course the early Computer Scientists who invented the idea of programming languages were being creative in the way Ole Kirk Christiansen and Olafur Eliasson were, creating the possibility for others. Creating possibilities for you.

The Arts are about pure creativity but so is Computer Science…(and when they are brought together by creative people even more amazing things can be created (by everyone).

Paul Curzon, Queen Mary University of London

The Knights Templar Cipher

The Knights Templar flag. A red cross on a black (above) and white (below (background) — The flag of the Knight’s Templar. Image by CS4FN

The Knights Templar were a 12th century order of catholic warrior monks, more accurately if convolutedly called “The Poor Fellow-Soldiers of Christ and of the Temple of Solomon” though they weren’t exactly poor. In addition to their original role of protecting catholic pilgrims heading to Jerusalem from robbery and murder, they also acted as a kind of international banker to support their main role. They laid some important foundations of modern international banking in the process. In particular, they invented a way to move money (or gold) around safely, without ever actually moving it anywhere. That sounds like a magic trick! Did they use some supposed mystical magic powers to do this? No, they kept the actual money given to them in the nearest of their large network of 1000 or so headquarters and forts around the continent. The money didn’t have to move anywhere. They then gave the person a note to hand in at their headquarters in another country. It promised that the Knights there would give them the equivalent amount from their money store when asked and given the note. The Knights there just swapped them the money for that note. This worked as long as they had a suitable store of money in each location, which of course would be topped up each time someone wanted to move money from that point. This is a simple version of how international banking works now. A British 20 pound note just promises to pay the bearer an equivalent amount, and without that promise (and people’s belief in it) it is just a piece of paper. It is just a similar promissory note, except people now just swap notes, treating it as money in its own right. Similarly, the banks don’t actually move any gold or other physical form of money about when you pay a shop with your debit card or banking app. They just move information equivalent to those promissory notes embodied in the transaction, around a network (though a computer one rather than a network of forts connected by roads).

There is a problem though with moving money from one person to another in this way using notes. If someone steals the note then it is potentially as valuable to them as actually stealing the chest of gold left in the original fort (just as stealing a 20 pound note is). In the Templar’s time the thief would just need to take it to a Templar headquarters and swap it for money just as the original owner would have done (a bit risky perhaps, given how fearsome the Templars were, but potentially possible!). Worse though, without a system to protect from this kind of attack, a thief could copy the note and then ask for the money repeatedly!

However, the Templars are know to have used encryption in their communications. The notes may therefore have been encrypted too and if so that would have made them useless if stolen. Banks now encrypt all those messages that move money about computer networks for the same reason. If only the Templar’s could read their notes (as only the Templar’s knew the key to their code), then only they could know it even was promising money. That doesn’t fully make it secure though, perhaps a thief could guess it was such a note, and if so what is to stop them then trying to cash it in (apart from the risk of being wrong). You would need something more. A simple possibility is the person with the note would need to know the encrypted amount that was contained somewhere within it. If they didn’t ask for the right amount then they couldn’t have handed over the money in the first place. They would reveal themselves as a thief!

Modern banks have to deal with similar problems even though modern financial transactions are all encrypted. Simple encryption alone is still not enough, protocols (special algorithms) are needed to prevent wide ranging kinds of attack being possible. Banks also need to use better ciphers than those from the Middle Ages, as today we can quickly crack ciphers as simple as the Templar Cipher. Banking is all done differently in detail today, but the ideas behind what is done and why are the same.

Can you crack the Templars’ cipher and decrypt the message below? One way might be using frequency analysis. The most common letters in English are likely (if not definitely) the most common in the message. E is most frequent in English, so which symbol might stand for E? Frequency analysis had been known for several hundred years before the Templars used ciphers (at least by the Arabs, though the Templars weren’t exactly their friends!), so it is actually possible even then that the Templars’ messages might be cracked, unknown to them. It was an Arabian scholar called Al Kindi, who actually invented frequency analysis (or at least was the earliest known person to write about it in his manuscript “On Deciphering Cryptographic Messages”.) Another way to crack the code might be to look for cribs – what words might be included in the message if it is a promissory note? Using both together may give you a good chance of decrypting the message. If you can’t crack their code (there is a big clue in this article), the key is given at the end if you scroll down. Use it to then decrypt the message.

Templar Cipher Puzzle using triangles, diamonds and other symbols.

Magazines …

Issue 24 – Keep Out!

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

Scroll down for the solutions

Solutions: The Key

The Templar’s cipher uses symbols based on their flag’s triangles. To encrypt a message swap letters for symbols. (They had no J).

Can you decrypt the message given the above key? Here is an example – the message HELLO as encrypted in this cipher.

Scroll down further for what the message says…

Solutions: The Message

The message reads …

GIVE KING PHILIP OF FRANCE ONE HUNDRED GOLD PIECES

DoodleDraw a snowflake

A single snowflake — Image by Cheryl Johnson from Pixabay

Following algorithms to draw nature can lead to natural looking pictures of all all sorts of things: from trees to snowflakes. It is one way computer generated imagery (CGI) scenery is created for films and games. You can write computer programs to do it if you have programming skill, but it can be just as fun (and more stress-relieving) to just doodle algorithmic pictures by hand – you act as what computer scientists call a ‘computational agent’ just following the algorithm. Here is an example Doodle Algorithm to draw a snowflake.

The DoodleDraw Algorithm

1. Draw a Black rectangle
2. Draw a SnowflakeHex in the middle of the black rectangle.
3. DoodleDraw a.Hexagon Snowflake

To Draw a SnowflakeHex:
    1. Draw a white hexagon with white lines sticking out from each corner (as shown).

To DoodleDraw a Hexagon Snowflake:
    1. IF happy with the picture THEN STOP
        ELSE
            1. Pick an existing SnowflakeHex and pick a line on it.
            2. Draw a new smaller SnowflakeHex on that line.
            3. DoodleDraw a Hexagon Snowflake.

A hexagon with lines from each corner — Image by CS4FN

The doodle this led to for me is given below… does it look snowflake-ish? Now follow the algorithm and draw your own, just like snowflakes every drawing should be different even if following the same algorithm as we include random steps in the algorithm.

A snowflake drawn from hexagons with lines from each corner — Image by CS4FN

Different algorithms with different starting shapes give different looking trees, grasses, ferns, snowflakes, crystals,… Often nature is following a very similar recursive creation process, which is why the results can be realistic.

Try inventing your own doodle art algorithm and see how realistic the drawings you end up with are. First try using a slightly different starting picture to ours above (eg a hollow hexagon instead of a filled in one, or skip the lines, or have more lines, or have a different central image to the one that is then replicated…and see what you end up with. Find lots more ideas for doodle draw algorithms on our DoodleDraw page.

Next time you find yourself doodling in a meeting or lecture, invent your own doodle draw algorithm, draw an algorithmic doodle, develop your algorithmic thinking skills and at the same time explore algorithms for drawing nature.

Lego Computer Science: sequence, selection and iteration

Children following a lego instruction booklet — *Image by* Thomas G. from Pixabay

Programming languages have lots of control structures, like if-statements and while loops, case-statements and for loops, method call and return, … but a famous research result in theoretical computer science (now called the structured program theorem) says you can do everything that it is possible to do with only three. All those alternatives are just for convenience. All you need is one way each to do sequence; one way to do selection, and one way to do iteration. If you have those you can build the structure needed to do any computation. In particular, you do not need a goto statement! We can explore what that means by just thinking about instructions to build Lego.

We have seen that you can think of a set of instructions to build Lego an algorithm. So do those instructions have everything needed to describe the structure of any computation?

What do we mean by a control structure? Just some mechanism to decide the order that instructions must be done for an algorithm to work. Part of what makes a set of instructions an algorithm is that the order of instructions are precisely specified. Follow the instructions in the right order and the algorithm is guaranteed to work.

Goto

First of all, Lego instructions are designed to be really clear and easy to follow. The nice folk at Lego want anyone to be able to follow them, even a small child and manage to accurately build exactly the model shown on the box.

What they do not make use of is a Goto instruction, an arbitrary jump to another place, where you are told, for example, to move to Page 14 for the next instruction. That kind of jump from place to place is reserved for Fighting Fantasy Adventure Books, where you choose the path through the story. They jump you about precisely because the aim is for you to be lost in the myriad of potential stories that are possible. You just don’t do that if you want instructions to be easy to follow.

The structured program theorem provided the ammunition for arguing that goto should not be used in programming and instead structured programming (hence the theorem’s name) should be used instead. All it actually does is show it is not needed though, not that its use is worse, though the argument was eventually won, with some exceptions. For programs to be human-readable and maintainable it is best that they use forms of structured programming, and avoid the spaghetti programming structures that goto leads to..

Sequencing

The main kind of control structure in a booklet of Lego instructions is instead sequencing. Instructions follow one after the other. This is indicated by the pages of the booklet. On each page though the instructions are split into boxes that are numbered. The boxes and numbers are the essential part of the control structure. You build the Lego model in the order of the numbered boxes. The numbering provides a sequencing control structure. Programming languages usually just use the order of instructions down a page to indicate sequencing, sometimes separated by punctuation (like a semi-colon), though early languages used this kind of numbering. The point is the same, however it is done, it is just a mechanism to make clear the order that the instructions are followed one after another, i.e., sequencing.

Parallelism and time-slicing

However, with lego there is another control structure within those boxes that is not quite sequencing. Each box normally has multiple pieces to place with the position of each shown. The lego algorithm isn’t specifying the order those pieces are placed (any order will do). This is a kind of non-deterministic sequencing control structure. It is similar to a parallelism control structure in programming languages, as if you like building your Lego model together with others, then a different person could choose each piece and all place the piece together (parallelism). Alternatively, they could place the pieces one after the other in some random order (time-slicing) and always end up with the same final result once the box is completed.

Is this necessary though? The structured program theorem says not, and in this case it is relatively easy to see that it isn’t. The people writing the instruction booklet could have decided an order themselves and enforced it. Which order they chose wouldn’t matter. Any Lego instruction booklet could be converted to one using only sequencing without parallelism or time-slicing.

Iteration

A Lego 2x instruction showing to put three tower bricks on top of one another, but to do this twice — Image by CS4FN after Lego instruction iteration

Iteration is just a way to repeat instructions or sub-programs. Lego instructions have a simplified form of repetition which is the equivalent of a simple for loop in programming. It just says that a particular box of instructions should be followed a fixed number of times (like 3 x meaning make this lego sub-build three times). With only this way of doing iteration lego instructions are not a totally general form of computation. There are algorithms that can’t be specified in Lego instructions. To be good enough to play the full role in the theorem, the iteration control structure has to have the capability to be unbounded. The decision to continue or not is made at the end of each iteration, You follow the instructions once, then decide if they should be followed again (and keep doing that). Having such a control structure would mean that at the point when you started to build the lego construct to be repeated, you would not necessarily know how many times that Lego construct was to be built. It’s possible to imagine Lego builds like this. For example, you might be building a fairytale castle made of modular turreted towers, where you can keep deciding whether to build another tower after each new tower is completed. until the castle is big enough. That would be an unbounded loop. An issue with unbounded loops is they could never terminate…you could be eternally damned to build Lego towers to eternity!

Selection

The final kind of control structure needed is selection. Selection involves having a choice of what instruction or subprogram to do next. This allows an algorithm to do different things depending on data input or the results of computation. As most lego sets involve building one specific thing, there isn’t much use of selection in Lego booklets.

However, some lego sets do have a simple form of selection. There are “3 in 1” sets where you can, for example, choose to make one of three animals by choosing one of three instruction booklets to follow at the start.

To be fully computationally general there would need to be choice possible at any point, in the way repetition can appear at any point in the booklet. It would need to be possible for any instruction or block of instructions to be prefigured by a test of whether they should be followed or not, with that test and arbitrary true/false question.

Again, such a thing is conceivable if more complex Lego builds were wanted. Building a fairytale castle you might include options to choose to build different kinds of turret on top of the towers, or choose different colours of bricks to make rainbow towers, or… If this kind of totally general choice was provided then no other kind of selection control structure would be needed. Having such instructions would provide a level of creativity between those of fixed sets to build one thing and the origianl idea of Lego as just blocks you could build anything from (the sets would need more bricks though!)

Sequence, Selection and Iteration is enough (but only if powerful enough)

So Lego instruction booklets do include the three kinds of control structure needed of sequence, selection and iteration. However, the versions used are not actually general enough for the structured control theorem to apply. Lego instructions with the control structures discussed are not powerful enough to be computationally complete, and describe all possible algorithms. More general forms are needed than found in normal Lego instructions to do that. In particular, a more general version of iteration is needed, as well as a verion of selection that can be used anywhere, and that includes a general purpose test. All programming languages have some powerful version of all three control structures. If they did not they could not be used as general purpose languages. There would be algorithms that could not be implemented in the language.

Just like programming languages, Lego instructions also use an extra kind of control structures that is not actually needed, It is there just for convenience, just like programming languages have lots of extra control structures just for convenience too.

Sadly then, Lego instructions, as found in the normal instruction booklets are not as general as a programming language. They do still provide a similar amount of fun though. Now, I must get back to building Notre Dame.

Paul Curzon, Queen Mary University of London

Unicode Poo

Lots of poo and toilet roll holding hands in a circle celebrating — Image by Gordon Johnson from Pixabay

Fact for the day: There is poo in unicode

Unicode is the way that computers represent characters in a way that means all human languages (and some alien ones like Klingon) can be represented on a computer. It is just a code mapping characters to numbers, and it replaced the earlier American ASCII code that only allowed for the latin alphabet as used in American english. It means that computers can display and letter or character from any language from Japanese to Egyptian Hieroglyphs.

So where does poo come in? Well, the Egyptians had a hieroglyph for it, so unicode has a number for it. There’s even more unicode poo in the emoji character set but the Egyptians got there 1000s of years earlier. Here is how the Ancient Egyptians wrote or carved poo:

𓄽

See https://en.wikipedia.org/wiki/List_of_Egyptian_hieroglyphs and search for excrement.

You can add any unicode character to a web page by including it in the html by putting &#x before the hexadecimal number corresponding to the unicode number of the character and following it by a semicolon so the Egyptian hieroglyph for excrement is written in html above as 𓄽

To write the heiroglyph for one of my favourites, an Egyptian Vulture, you use 𓄿 for example (it is also used to represent the letter aleph so a sound like our a when spelling out words).

𓄿

(If you don’t see the hieroglyphs it may just be that your browser can’t cope with unicode, try a different one!).

Paul Curzon, Queen Mary University of London

Instant 3×3 Magic Squares

A 3x3 magic square containing numbers
6 1 8
7 5 3
2 9 4 — Image by CS4FN

Amaze your family and friends this holiday showing your mathematical prowess by generating instant magic squares at will. In the previous article we saw how to generate 4×4 magic squares. If that was a bit too hard, here is a simpler version for generating instant 3×3 magic squares. Learn the trick and some computer science about algorithms and how they prove they always work.

The Trick

First ask an audience member to pick a number out of a hat. That will be the target number. You then write out a magic square that adds to that number.

The Secret

Building this type of magic square is based on the algorithm below that creates magic squares from 9 consecutive numbers. The secret is first to make sure all the numbers you put in the hat are multiples of 3 (i.e. are in the 3 times table). You then follow the algorithm below that tells you what numbers to put where in the grid.

The Magical Algorithm

Place lots of numbers on folded pieces of paper in a hat. All are multiples of 3 (but the audience do not know that).
Ask an audience member to pull one out at random.
Announce that that number is the TARGET number. You will create a magic square that adds up to that number so that is the number that the square rows and so on will add to.
In your head divide that number by 3. For example, if TARGET was 15 THEN you divide 15 by 3 to get 5. Let’s call this value MID, to allow us to be general when we follow the rest of the instructions.
On a 3 by 3 grid, put MID in the centre square (so in our example, put 5 in the middle).
Place the number (MID + 3) in the upper right-hand square (in our example, 5+3 = 8).
Place the number (MID – 3) in the lower left-hand square (in our example, 5-3 = 2).
Place the number (MID + 1) in the upper left-hand square (in our example, 5+1 = 6).
Place the number (MID – 1) in the lower right-hand square (in our example, 5-1 = 4).
Fill in the remaining squares to make the magic square work, so that the rows and columns add to TARGET (subtracting the other two numbers from TARGET in each case to get the missing one).

A 3x3 magic square template containing
MID+1 ___ MID+3
___ MID ___
MID-3 ___ MID-1 — Image by CS4FN

For the last step, you just need to fill in the empty squares, to make sure the rows and columns add to the right number, TARGET. To do this you just need to keep in mind the target magic number you calculated. (For our example, remember it was 15). It’s a bit of simple arithmetic to find these final numbers and voila, you have built a magic square that adds up to a total picked at random..

Practice doing the maths in your head so that you can make it seem magical.

Does it always work?

You can actually prove the trick always works using some simple algebra based on the template magic square above. See if you can work out how yourself. Using MID and TARGET in place of numbers, for the trick to always generate a correct magic square you need to check that all rows and columns simplify to be equivalent to TARGET. Visit our Conjuring with Computation website to see the detail of how.

Proving a magic trick in this way is just the same thing computer scientists do when they invent new computing algorithms to make sure they work. It increases the assurance that the algorithm and so programs implementing it do work.

If you can program, then you could write a program to generate magic squares using the above algorithm, and then your proof would be a step in verifying your program, as long as it does correctly implement the algorithm!

	The art of animatron… on I’m (not) a little …
	The Decline and Fall… on Victorian volunteers needed…
	Gatsby Benchmarks fo… on Finding work experience, or a…
	BBC Sound Effects li… on AMPER: AI helping future you r…
	PEEECS Bulletin Augu… on Involving disabled people in t…