Tag: EP/K040251/2

A visit to the Turing Machine: a short story

by Greg Michaelson

Greg Michaelson is an Emeritus professor of computer science at Heriot-Watt University in Edinburgh. He is also a novelist and a short story writer. He wrote this story for CS4FN.

From the cs4fn archive.

Burning City
Image by JL G from Pixabay

“Come on!” called Alice, taking the coat off the peg. “We’re going to be late!”

“Do I have to?” said Henry, emerging from the front room.

“Yes,” said Alice, handing him the coat. “Of course you have to go. Here. Put this on.”

“But we’re playing,” said Henry, wrestling with the sleeves.

“Too bad,” said Alice, straightening the jacket and zipping it up. “It’ll still be there when we get back.”

“Not if someone knocks it over,” said Henry, picking up a small model dinosaur from the hall table. “Like last time. Why can’t we have electric games like you did?”

“Electronic games,” said Alice, doing up her buttons. “Not electric. No one has them anymore. You know that.”

“Were they really digital?” asked Henry, fiddling with the dinosaur.

“Yes,” said Alice, putting on her hat. “Of course they were digital.”

“But the telephone’s all right,” said Henry.

“Yes,” said Alice, checking her makeup in the mirror. “It’s analogue.”

“And radio. And record players. And tape recorders. And television,” said Henry.

“They’re all analogue now,” said Alice, putting the compact back into her handbag. “Anything analogue’s fine. Just not digital. Stop wasting time! We’ll be late.”

“Why does it matter if we’re late?” asked Henry, walking the dinosaur up and down the hall table.

“They’ll notice,” said Alice. “We don’t want to get another warning. Put that away. Come on.”

“Why don’t the others have to go?” asked Henry, palming the dinosaur.

“They went last Sunday,” said Alice, opening the front door. “You said you didn’t want to go. We agreed I’d take you today instead.”

“Och, granny, it’s so boring…” said Henry.

They left the house and walked briskly to the end of the street. Then they crossed the deserted park, following the central path towards the squat neo-classical stone building on the far side.

“Get a move on!” said Alice, quickening the pace. “We really are going to be late.”

————————-

Henry really hadn’t paid enough attention at school. He knew that Turing Machines were named for Alan Turing, the first Martyr of the Digital Age. And he knew that a Turing Machine could work out sums, a bit like a school child doing arithmetic. Only instead of a pad of paper and a pencil, a Turing Machine used a tape of cells. And instead of rows of numbers and pluses and minuses on a page, a Turing Machine could only put one letter on each cell, though it could change a letter without having to actually rub it out. And instead of moving between different places on a piece of paper whenever it wanted to, and maybe doodling in between the sums, a Turing Machine could only move the tape left and right one cell at a time. But just like a school child getting another pad from the teacher when they ran out of paper, the Turing Machine could somehow add another empty cell whenever it got to the end of the tape.

————————-

When they reached the building, they mounted the stone staircase and entered the antechamber through the central pillars. Just inside the doorway, Alice gave their identity cards to the uniformed guard.

“I see you’re a regular,” she said approvingly to Alice, checking the ledger. “But you’re not,” sternly to Henry.

Henry stared at his shoes.

“Don’t leave it so long, next time,” said the guard, handing the cards back to Alice. “In you go. They’re about to start. Try not to make too much noise.”

Hand in hand, Alice and Henry walked down the broad corridor towards the central shrine. On either side, glass cases housed electronic equipment. Computers. Printers. Scanners. Mobile phones. Games consoles. Laptops. Flat screen displays.

The corridor walls were lined with black and white photographs. Each picture showed a scene of destitution from the Digital Age.

Shirt sleeved stock brokers slumped in front of screens of plunging share prices. Homeless home owners queued outside a state bank soup kitchen. Sunken eyed organic farmers huddled beside mounds of rotting vegetables. Bulldozers shovelled data farms into land fill. Lines of well armed police faced poorly armed protestors. Bodies in bags lay piled along the walls of the crematorium. Children scavenged for toner cartridges amongst shattered office blocks.

Alice looked straight ahead: the photographs bore terrible memories. Henry dawdled, gazing longingly into the display cases: Gameboy. Playstation. X Box…

“Come on!” said Alice, sotto voce, tugging Henry away from the displays.

At the end of the corridor, they let themselves into the shrine. The hall was full. The hall was quiet.

————————-

Henry was actually quite good at sums, and he knew he could do them because he had rules in his head for adding and subtracting, because he’d learnt his tables. The Turing Machine didn’t have a head at all, but it did have rules which told it what to do next. Groups of rules that did similar things were called states, so all the rules for adding were kept separately from all the rules for subtracting. Every step of a Turing machine sum involved finding a rule in the state it was working on to match the letter on the tape cell it was currently looking at. That rule would tell the Machine how to change the symbol on the tape, which way to move the tape, and maybe to change state to a different set of rules.

————————-

On the dais, lowered the Turing Machine, huge coils of tape links disappearing into the dark wells on either side, the vast frame of the state transition engine filling the rear wall. In front of the Turing Machine, the Minister of State stood at the podium.

“Come in! Come in!” he beamed at Alice and Henry. “There’s lots of space at the front. Don’t be shy.”

Red faced, Alice hurried Henry down the aisle. At the very front of the congregation, they sat down cross legged on the floor beneath the podium.

“My friends,” began the Minister of State. “Welcome. Welcome indeed! Today is a special day. Today, the Machine will change state. But first, let us be silent together. Please rise.”

The Minister of State bowed his head as the congregation shuffled to its feet.

———————–

According to Henry’s teacher, there was a different Turing Machine for every possible sum in the world. The hard bit was working out the rules. That was called programming, but, since the end of the Digital Age, programming was against the law. Unless you were a Minister of State.

————————

“Dear friends,” intoned the Minister of State, after a suitable pause. “We have lived through terrible times. Times when Turing’s vision of equality between human and machine intelligences was perverted by base greed. Times when humans sought to bend intelligent machines to their selfish wills for personal gain. Times when, instead of making useful things that would benefit everybody, humans invented and sold more and more rarefied abstractions from things: shares, bonds, equities, futures, derivatives, options…”

————————

The Turing Machine on the dais was made from wood and brass. It was extremely plain, though highly polished. The tape was like a giant bicycle chain, with holes in the centre of each link. The Machine could plug a peg into a hole to represent a one or pull a peg out to represent a zero. Henry knew that any information could be represented by zeros and ones, but it took an awful lot of them compared with letters.

————————-

“… Soon there were more abstractions than things, and all the wealth embodied in the few things that the people in poor countries still made was stolen away, to feed the abstractions made by the people in the rich countries. None of this would have been possible without computers…”

————————-

The state transition unit that held the rules was extremely complicated. Each rule was a pattern of pegs, laid out in rows on a great big board. A row of spring mounted wooden fingers moved up and down the pegs. When they felt the rule for the symbol on the tape cell link, they could trigger the movement of a peg in or out of the link, and then release the brakes to start up one revolution of the enormous cog wheels that would shift the tape one cell left or right.

A stone looking like a scared face
Image by Dean Moriarty from Pixabay

————————-

“…With all the computers in the world linked together by the Internet, humans no longer had to think about how to manage things, about how best to use them for the greatest good. Instead, programs that nobody understood anymore made lightening decisions, moving abstractions from low profits to high profits, turning the low profits into losses on the way, never caring how many human lives were ruined…”

————————-

The Turing Machine was powered by a big brass and wooden handle connected to a gear train. The handle needed lots of turns to find and apply the next rule. At the end of the ceremony, the Minister of State would always invite a member of the congregation to come and help him turn the handle. Henry always hoped he’d be chosen.

——————————

“…Turing himself thought that computers would be a force for untold good; that, guided by reason, computers could accomplish anything humans could accomplish. But before his vision could be fully realised, he was persecuted and poisoned by a callous state interested only in secrets and profits. After his death, the computer he helped design was called the Pilot Ace; just as the pilot guides the ship, so the Pilot Ace might have been the best guide for a true Digital Age…”

——————————

Nobody was very sure where all the cells were stored when the Machine wasn’t inspecting them. Nobody was very sure how new cells were added to the ends of the tape. It all happened deep under the dais. Some people actually thought that the tape was infinite, but Henry knew that wasn’t possible as there wasn’t enough wood and brass to make it that long.

——————————

“…But almost sixty years after Turing’s needless death, his beloved universal machines had bankrupted the nations of the world one by one, reducing their peoples to a lowest common denominator of abject misery. Of course, the few people that benefited from the trade in abstractions tried to make sure that they weren’t affected but eventually even they succumbed…”

——————————

Nobody seemed to know what the Turing Machine on the dais was actually computing. Well, the Minister of State must have known. And Turing had never expected anyone to actually build a real Turing Machine with real moving parts. Turing’s machine was a thought experiment for exploring what could and couldn’t be done by following rules to process sequences of symbols.

——————————

“…For a while, everything stopped. There were power shortages. There were food shortages. There were medical shortages. People rioted. Cities burned. Panicking defence forces used lethal force to suppress the very people they were supposed to protect. And then, slowly, people remembered that it was possible to live without abstractions, by each making things that other people wanted, by making best use of available resources for the common good…”

——————————

The Turing Machine on the dais was itself a symbol of human folly, an object lesson in futility, a salutary reminder that embodying something in symbols didn’t make it real.

——————————

“…My friends, let us not forget the dreadful events we have witnessed. Let us not forget all the good people who have perished so needlessly. Let us not forget the abject folly of abstraction. Let the Turing Machine move one step closer along the path of its unknown computation. Let the Machine change its state, just as we have had to change ours. Please rise.”

The congregation got to their feet and looked expectantly at the Minister of State. The Minister of State slowly inspected the congregation. Finally, his eyes fixed on Henry, fidgeting directly in front of him.

“Young man,” he beamed at Henry. “Come. Join me at the handle. Together we shall show that Machine that we are all its masters.”

Henry looked round at his grandmother.

“Go on,” she mouthed. “Go on.”

Henry walked round to the right end of the dais. As he mounted the wooden stairs, he noticed a second staircase leading down behind the Machine into the bowels of the dais.

“Just here,” said the Minister of State, leading Henry round behind the handle, so they were both facing the congregation. “Take a good grip…”

Henry was still clasping the plastic dinosaur in his right hand. He put the dinosaur on the nearest link of the chain and placed both hands on the worn wooden shaft.

And turn it steadily…”

Henry leant into the handle, which, much to his surprise, moved freely, sweeping the wooden fingers across the pegs of rules on the state transition panel. As the fingers settled on a row of pegs, a brass prod descended from directly above the chain, forcing the wooden peg out of its retaining hole in the central link. Finally, the chain slowly began to shift from left to right, across the front of the Machine, towards Henry and the Minister of State. As the chain moved, the plastic dinosaur toppled over and tumbled down the tape well.

“Oh no!” cried Henry, letting go of the handle. Utterly nonplussed, the Minister of State stood and stared as Henry peered into the shaft, rushed to the back of the Machine and hurried down the stairs into the gloom.

A faint blue glow came from the far side of the space under the dais. Henry cautiously approached the glow, which seemed to come from a small rectangular source, partly obscured by someone in front of it.

“Please,” said Henry. “Have you seen my dinosaur?”

“Hang on!” said a female voice.

The woman stood up and lit a candle. Looking round, Henry could now see that the space was festooned with wires, leading into electric motors driving belts connected to the Turing Machine. The space was implausibly small. There was no room for a finite tape of any length at all, let alone an infinite one.

“Where are all the tape cells?” asked Henry, puzzled.

“We only need two spare ones,” said the woman. “When the tape moves, we stick a new cell on one end and take the cell off the other.”

“So what’s the blue light?” asked Henry.

“That’s a computer,” said the woman. “It keeps track of what’s on the tape and controls the Turing Machine.”

“A real digital computer!” said Henry in wonder. “Does it play games?”

“Oh yes!” said the woman, turning off the monitor as the Minister of State came down the stairs. “What do you think I was doing when you showed up? But don’t tell anyone. Now, let’s find that dinosaur.”

Related Magazines …

cs4fn issue 14 cover

More on …

EPSRC supports this blog through research grant EP/W033615/1,

Lego Computer Science: Turing Machines Part 3: the program

CS4FN Banner

by Paul Curzon, Queen Mary University of London

Image by CS4FN

We have so far built the hardware of a Lego Turing Machine. Next we need the crucial part: software. It needs a program to tell it what to do.

Our Turing Machine so far has an Infinite Tape, a Tape Head and a Controller. The Tape holds data values taken from a given set of 4×4 bricks. It starts in a specific initial pattern: the Initial Tape. There is also a controller. It holds different coloured 3×2 bricks representing an initial state, an end state, a current state and has a set of other possible states (so coloured bricks) to substitute for the current state.

Why do we need a program?

As the machine runs it changes from one state to another, and inputs from or outputs to the tape. How it does that is governed by its Program. What is the new state, the new value and how does the tape head move? The program gives the answers. The program is just a set of instructions the machine must blindly follow. Each instruction is a single rule to follow. Each program is a set of such rules. In our Turing Machines, these rules are not set out in an explicit sequence as happens in a procedural program, say. It uses a different paradigm for what a program is. Instead at any time only one of the set of rules should match the current situation and that is the one that is followed next.

Individual Instructions

A single rule contains five parts: a Current State to match against, a Current Value under the Tape Head to match against, a New State to replace the existing one, and a New Value to write to the tape. Finally, it holds a Direction to Move the Tape Head (left or right or stay in the same place). An example might be:

  • Current State: ORANGE
  • Current Value: RED
  • New State: GREEN
  • New Value: BLUE
  • Direction: RIGHT

But what does a rule like this actually do?

What does it mean?

You can think of each instruction as an IF-THEN rule. The above rule would mean:

IF 

  •    the machine is currently in state ORANGE AND    
  •    the Tape Head points to RED 

THEN (take the following actions)

  •     change the state to GREEN, 
  •     write the new value BLUE on the tape AND THEN
  •     move the tape head RIGHT.

This is what a computer scientist would call the programming language Semantics. The semantics tell you what program instructions mean, so what they do.

Representing Instructions in Lego

We will use  a series of 5 bricks in a particular order to represent the parts of the rule. For example, we will use a yellow 3×2 brick in the first position of a rule to represent the fact that the rule will only trigger if the current state is yellow. A blue 2×2 brick in the second position will mean the rule will also only trigger if the current value under the tape head is blue. We will use a grey brick to mean an empty tape value. The third and fourth position will represent the new state and new value if the rule does trigger. To represent the direction to move we will use a 1×2 Red brick to mean move Right, and a 1×2 yeLLow brick to mean move Left. We will use a black 1×2 brick to mean do not move the tape head (mirroring the way we are also using black to mean do nothing in the sense of the special end state). The above rule would therefore be represented in Lego as below. 

A Turing machine instruction Current state: orange Currnent value red New state green New value blue Direction red
A single instruction for a Lego Turing Machine. Image by CS4FN

Notice we are using the same colour to represent different things here. The representation is the colour combined with the size of brick and position in the rule. So a Red brick can mean a red state (a red 3×2 brick) or a red value (a red 2×2 brick) or move right (a red 1×2 brick).

Lego programs

That is what a rule, so single Turing Machine instruction, looks like. Programs are just a collection of such rules: so a series of lines of bricks.

Suppose we have a Turing machine with two states (Red and Orange) and two values on the tape (Blue or Empty), then a complete program would have 4 rules, one for each possible combination. We have given one example program below. If there were more states or more possible data values then the program would be correspondingly bigger to cover all the possibilities.

A Turing Machine Program Red-Blue -> Red-Blue-Red Red-Grey -> Orange-Blue-Yellow Orange-Blue -> Orange-Blue-Yellow Orange-Grey -> Black-Grey-Red
A 4 instruction Turing Machine Program for a Turing Machine with two states (Red, Orange) and two data values (Blue, Empty). Image by CS4FN

A Specific Turing Machine

Exactly what it does will depend on its input – the initial tape it is given to process, as well as the initial state and where the tape head initially points to. Perhaps you can work out what the above program does given a tape with an empty value followed by a series of three blue bricks (and then empty data values off to infinity (the blank value is the only value that is allowed to appear an infinite number of times on an initial tape) and the Head pointing to the rightmost blue brick value. The initial state is red. See the Lego version of this specific machine below.

A Turing Machine with Tape, Controller and Program.
A full Turing Machine ready to execute. Image by CS4FN

Note something we have glossed over. You also potentially need an infinite number of bricks of each value that is allowed on the tape. We have a small pile, but you may need that Lego factory we mentioned previously, so that as the Turing Machine runs you always have a piece to swap on to the machine tape when needed. Luckily, for this machine a small number of bricks should be enough (as long as you do not keep running it)!

What does this Turing Machine do? We will look at what it does and how to work it out in a future article. In the meantime try and work out what it does with this tape, but also what it does if the tape has more or less blue bricks in a row on it to start with (with everything else kept the same).

Note that, to keep programs smaller, you could have a convention that if no rule fits a situation then it means the program ends. Then you could have fewer rules in some programs. However,  that would just be shorthand for there being extra rules with black new states, the tape being left alone, and the tape head moves right. In real programming, it is generally a good idea to ALWAYS be explicit about what you intend the program to do, as otherwise it is an easy way for bugs to creep in, for example, because you just forgot to say in some case.

Alan Turing invented Turing Machines before any computer existed. At the time a “computer” was a person who followed rules to do calculations (just like you were taught the rules to follow to do long multiplication at primary school, for example). His idea was therefore that a human would follow the rules in a Turing Machine program, checking the current state and value under the tape head, and changing the state, the value on the tape and the movement of the head. A person provides the power and equivalent of a robotic arm that follows the underlying Turing Machine algorithm: the Turing Machine algorithm that if followed causes each Turing Machine’s program to execute.

If a human animating the machine was good enough for Turing, it is good enough for us, so that is how our Lego Turing Machines will work. Your job will be to follow the rules and so operate the machine. Perhaps, that is exactly what you did to work out what the program above does!

Next we will look at how to work out what a Turing Machine does. Then it will be time to write, then run, some Turing Machine programs of your own…

More on …

Lego Computer Science

Image shows a Lego minifigure character wearing an overall and hard hat looking at a circuit board, representing Lego Computing
Image by Michael Schwarzenberger from Pixabay

Part of a series featuring featuring pixel puzzles,
compression algorithms, number representation,
gray code, binary and computation.

Related Magazines …

cs4fn issue 14 cover

EPSRC supports this blog through research grant EP/W033615/1, The Lego Computer Science post was originally 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.

Lego Computer Science: Turing Machines Part 2: the controller

by Paul Curzon, Queen Mary University of London

Image by CS4FN

Last time we started to build a working computer out of Lego: a Turing Machine. So far we have seen that we can make the memory of a Turing Machine (its Infinite Tape) in Lego. We can also create a movable Tape Head that marks the position where data can be read from and written to the tape (see image).

Controlling states

How does the machine decide where and when to move the Tape Head, though? It has a Controller. The key part of the controller is that it holds a Current State of the machine. Think of traffic lights for what we mean by the state of a machine. In the UK traditional traffic lights have a Red state, an Amber state, a Green state and a Red-Amber state. Each means a different thing (such as “Stop” and “Go”). The controller of the lights moves between these different internal states. With a traffic light, the current internal state is also shown to the world by the lights that light up! Machine states do not have to be visible to the outside world, however. In fact, they only are if the person who designs the interface makes them visible. For most machines, only some of their internal state is made visible. In our Turing Machine we will be able to see the states as they will be visible in the controller. However, the output of a Turing Machine is the state of the tape, so if we wanted the states to really be visible we would write a version on to the tape. You can then imagine the tape triggering external lights to come on or off, or change colour as a simple form of actual output. This is what Computer Scientists call memory-mapped peripherals – where to send data (output) to a peripheral device (a screen, a panel of lights, a printer, or whatever, you write to particular locations in memory, and that data is read from there by the peripheral device. That is going beyond the pure idea of a Turing Machine though, where the final state of the machine when it stops is its output.

Representing States

How do we represent states in Lego? Any finite set of things (symbols) could be used to represent the different states (including numbers or binary codes, for example). We will use different coloured 3×2 blocks. Each colour of block will stand for a different state that the machine is in. The controller will have a space that holds the brick representing the Current State. It will also have space for a set of places for the blocks representing the other allowable states of this Turing Machine. As the machine runs, the state will change as represented by swapping one of these state bricks for another.

Different Turing Machines can allow a different number of possible states the machine could be in, so this part of the controller might be bigger or smaller depending on the machine and what it needs to do its job. Again think of traffic lights, in some countries, and on pedestrian crossings there are only two states, a Red state (stop) and a Green state (go). Its controller only needs two states so we would only need two different coloured bricks.

A Turing Machine Controller with current state red, end state black and three other possible states (green, orange and blue). Image by CS4FN

Initial States

The current state will always start in some initial state when the machine first starts up. It is useful to record in the controller what state that is so that each time we restart the machine anew it can be reset. We will just put a block in the position next to the current state to indicate what the initial state should be. We won’t ever change it for a given machine.

End States

One of the states of a Turing Machine is always a special End State. We will always use a black brick to represent this. Whatever is used has to be specified at the outset, though. When not in use we will keep the end state brick next to the initial state brick. Once the machine finishes operations it will enter this End State, or put another way, if the black brick ever becomes the current state brick the machine will stop. From that point on the machine will do nothing. Some machines might never reach an end state, they just go on forever. Traffic lights just cycle round the states forever, for example, never reaching an end state. Other machines do end though. For example, a kettle controller stops the machine when the water has boiled. An addition Turing Machine might end when it has output the answer to an addition. To do another addition you would start it up again with new information on the tape indicating what it was to add.

We have now created the physical part of the Turing Machine. All we need now is a Program to tell it what to do! Programs come next in Part 3…

More on …

Lego Computer Science

Image shows a Lego minifigure character wearing an overall and hard hat looking at a circuit board, representing Lego Computing
Image by Michael Schwarzenberger from Pixabay

Part of a series featuring featuring pixel puzzles,
compression algorithms, number representation,
gray code, binary and computation.

Related Magazines …

cs4fn issue 14 cover

EPSRC supports this blog through research grant EP/W033615/1, The Lego Computer Science post was originally 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.

Lego Computer Science: Turing Machines Part 1: the tape

by Paul Curzon, Queen Mary University of London

Image by CS4FN

It it possible to make a working computer out of lego and you do not even have to pay for an expensive robot Mindstorm kit…but only if you are willing to provide the power yourself.

A machine in theory

In fact, Alan Turing, grandfather of Computer Science worked out how to do it before the War and before any actual computer existed. His version also needed humans to power it. Now we call it a Turing Machine and it is a theoretical model of what is computable by any machine.

The Tape

To make a working Turing Machine you first need to build an infinitely long Tape that can hold Symbols, representing data values, along it at fixed intervals. That is easy (as long as you have a lego factory). You just need to create a long line of flat pieces, say 2 studs wide. Each 2×2 square on it is then a position on the Tape. 

An infinite tape out of Lego (relies on having a Lego factory at the right-hand end churning out new tape if and when it is needed...
An infinite tape out of Lego (relies on having a Lego factory at the right-hand end churning out new tape if and when it is needed… Image by CS4FN

Be lazy

Of course you can’t actually make it infinitely long, but you can make it longer every time you need some more of it (so no problem if you do have a lego factory to churn out extra bricks as needed!) This approach to dealing with infinite data structures where you just make it bigger only when needed is now called lazy programming by computer scientists and is an elegant way that functional programs deal with input that needs to represent an infinite amount of input…It is also the way some games (like Minecraft) represent worlds or even universes. Rather than create the whole universe at the start, things over the horizon, so out of sight, are only generated if a player ever goes there – just-in-time world generation! Perhaps our universe is like that too, with new galaxies only fleshed out as we develop the telescopes to see them!

Fill it with data

The Tape has a set of Data Symbols that can appear on it that act as the Data Values of the machine. Traditional computers have symbols 0 and 1 underpinning them, so we could use those as our symbols, but in a Turing Machine we can have any set of symbols we like: ten digits, letters, Egyptian hieroglyphs, or in fact any set of symbols we want to make up. In a lego Turing Machine we can just use different coloured blocks as our symbols. If our tape is made of grey pieces then we could use red and blue for the symbols that can appear on it. Every position on the tape will then either hold a red block or a blue block. We could also allow EMPTY to be a symbol too in which case some 2×2 slots could be empty to mean that.

A tape containing data where the allowed symbols are EMPTY, RED and BLUE
A tape containing data where the allowed symbols are EMPTY, RED and BLUE. Image by CS4FN

To start with

Any specific Turing Machine has an Initial Tape. This is the particular data that is on the tape at the start, before it is switched on. As the machine runs, the tape will change.

The tape with symbols on it takes the place of our computer’s memory. Just as a modern computer stores 1s and 0s in memory, our Lego Turing Machine stores its data as symbols on this tape. 

The Head

A difference is that modern computers have “random access memory” – you can access any point in memory quickly. Our tape will be accessed by a Tape Head that points to a position on the tape and allows you to read or change the data only at the point it is at. Make a triangular tape head out of lego so that it is clear which point on the tape it is pointing at. We have a design choice here. Either the Tape moves or the Head moves. As the tape could be very long so hard to move we will move the Head along beside it, so create a track for the Head to move along parallel to the tape. It will be able to move 2 studs at a time in either direction so that each time it moves it is pointing to a new position on the tape.

An infinite tape with Head (yellow) pointing at position 4 on the tape.
An infinite tape with Head (yellow) pointing at position 4 on the tape. Image by CS4FN

We have memory

We now have the first element in place of a computer, then: Memory. The next step will be to provide a way to control the tape head and how data is written to and read from the tape and so computation actually happen. (For that you need a controller which we cover in Part 2…).

More on …

Lego Computer Science

Image shows a Lego minifigure character wearing an overall and hard hat looking at a circuit board, representing Lego Computing
Image by Michael Schwarzenberger from Pixabay

Part of a series featuring featuring pixel puzzles,
compression algorithms, number representation,
gray code, binary, logic and computation.

Related Magazines …

cs4fn issue 14 cover

EPSRC supports this blog through research grant EP/W033615/1, The Lego Computer Science post was originally 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.

CS4FN Advent 2023 – Day 25: Merry Christmas! Today’s post is about the ‘wood computer’

Today is the final post in our CS4FN Christmas Computing Advent Calendar – it’s been a lot of fun rummaging in the CS4FN back catalogue, and also finding out about some new things to write about.

Advert for our Advent calendar

Each day we’ve published a blog post about computing with the theme suggested by the picture on the advent calendar’s ‘door’. Our first picture was a woolly jumper so the accompanying post was about the links between knitting and coding, the door with a picture of a ‘pair of mittens’ on led to a post about pair programming and gestural gloves, a patterned bauble to an article about printed circuit boards, and so on. It was fun coming up with ideas and links and we hope it was fun to read too.

We hope you enjoyed the series of posts (click on any of the Christmas trees in this post to see them all) and that you are already having a very Merry Christmas.

And on to today’s post which is inspired by the picture of a Christmas Tree, so it’ll be a fairly botanically-themed post. The suggestion for this post came from Prof Ursula Martin of Oxford University, who told us about the ‘wood computer’.

It’s a Christmas tree!

The Wood Computer

by Jo Brodie, QMUL.

Other than asking someone “do you know what tree this is?” as you’re out enjoying a nice walk and coming across an unfamiliar tree, the way of working out what that tree is would usually involve some sort of key, with a set of questions that help you distinguish between the different possibilities. You can see an example of the sorts of features you might want to consider in the Woodland Trust’s page on “How to identify trees“.

Tree silhouettes image by Clker-Free-Vector-Images from Pixabay

Depending on the time of year you might consider its leaves – do they have stalks or not, do they sit opposite from each other on a twig or are they diagonally placed etc. You can work your way through leaf colour, shape, number of lobes on the leaf and also answer questions about the bark and other features of your tree. Eventually you narrow things down to a handful of possibilities.

What happens if the tree is cut up into timber and your job is to check if you’re buying the right wood for your project. If you’re not a botanist the job is a little harder and you’d need to consider things like the pattern of the grain, the hardness, the colour and any scent from the tree’s oils.

Wooden bridge image by Peter H from Pixabay

Historically, one way of working out which piece of timber was in front of you was to use a ‘wood computer’ or wood identification kit. This was prepared (programmed!) from a series of index cards with various wood features printed on all the cards – there might be over 60 different features.

Every card had the same set of features on it and a hole punched next to every feature. You can see an example of a ‘blank’ card below, which has a row of regularly placed holes around the edge. This one happens to be being used as a library card rather than a wood computer (though if we consider what books are made of…).

Image of an edge-notched card (actually being used as a library card though), from Wikipedia.

I bet you can imagine inserting a thin knitting needle into any of those holes and lifting that card up – in fact that’s exactly how you’d use the wood computer. In the tweet below you can see several cards that made up the wood computer.

One card was for one tree or type of wood and the programmer would add notch the hole next to features that particularly defined that type. For example you’d notch ‘has apples’ for the apple tree card but leave it as an intact hole on the pear tree card.  If a particular type of timber had fine grained wood they’d add the notch to the hole next to “fine-grained”. The cards were known, not too surprisingly, as edge-notched cards.

You can see what one looks like here with some notches cut into it. You might have spotted how knitting needles can help you in telling different woods apart.

Holes and notches

Edge-notched card overlaid on black background, with two rows of holes. On the top a hole in the first row is notched, on the right hand side two holes are notched. Image from Wikipedia.

Each card would end up with a slightly different pattern of notched holes, and you’d end up with lots of cards that are slightly different from each other.

Example ‘wood computer’. At the end of your search (to find out which tree your piece of wood came from) you are left with two cards for fine-grained wood. If your sample has a strong scent then it’s likely it’s the tree in the card on the right (though you could arrive at the same conclusion by using the differences in colour too). The card at the top is the blank un-notched card.

How it works

Your wood computer is basically a stack of cards, all lined up and that knitting needle. You pick a feature that your tree or piece of wood has and put your needle through that hole, and lift. All of the cards that don’t have that feature notched will have an un-notched hole and will continue to hang from your knitting needle. All of the cards that contain wood that do have that feature have now been sorted from your pile of cards and are sitting on the table.

You can repeat the process several times to whittle (sorry!) your cards down by choosing a different feature to sort them on.

The advantage of the cards is that they are incredibly low tech, requiring no electricity or phone signal and they’re very easy to use without needing specialist botanical knowledge.

You can see a diagram of one on page 8 of the 20 page PDF “Indian Standard: Key for identification of commercial timbers”, from 1974.

The word ‘card’ features over 30 times on this page and the word Christmas over 10 times but this post isn’t actually about Christmas cards! We hope you had plenty of those 🙂 Merry Christmas.

Teachers: we have a classroom sorting activity that uses the same principles as the wood computer. Download our Punched Card Searching PDF from our activity page.

The creation of 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.

Advert for our Advent calendar
Click the tree to visit our CS4FN Christmas Computing Advent Calendar

EPSRC supports this blog through research grant EP/W033615/1.

CS4FN Advent 2023 – Day 24: Santa’s Sleigh – track its progress through the skies

We are nearly coming to the end of our CS4FN Christmas Computing Advent Calendar with one more post to come tomorrow. If you’ve missed any you can catch up by scrolling to the end and click on the Christmas Tree in the panel for the complete list so far.

Today’s advent calendar window shows Father Christmas’ sleigh with a sack full of presents ready for delivery. Today’s theme is about the many different online ways that you can now ‘track’ his movements around the world. This follows on from yesterday’s bonus post about how you may be able to see (cloud permitting) his sleigh ‘in person’ as it flies overhead at 5:54am on Christmas Day 2023. In reality it’s International Space Station whizzing past – but other interpretations are available.

You can track Father Christmas as he dashes through the sky, delivering presents.

1. NORAD Santa tracker

https://www.noradsanta.org/en/ for games
https://www.noradsanta.org/en/map (you can also track him on NORAD’s apps too)

In 1955, so the story goes, an American department store published a newspaper advert with a phone number for children to call so that they could speak to Father Christmas. Unfortunately a misprint meant that the wrong number was given and instead people found they were talking to the US military’s Air Defense Command (now called North America Air Defense Command or NORAD).

Realising the mistake, but also spotting a great public relations opportunity, the team capitalised on this and began to make an annual event of it.

NORAD uses radar and geosynchronous* satellites to monitor Father Christmas. The satellites are able to detect infrared (heat) radiation and apparently Rudolph’s red nose gives quite a strong signal. This data is then shared with everyone via their website, though they don’t know in advance what route he’ll take.

If you’re visiting the website hover over the different bits of the picture as there are linked activities and extra information too.

*geo = Earth, synchronous = matching / following (like when you sync devices), the satellite follows the Earth’s orbit and is always above the same spot, so effectively (from the Earth’s point of view) the satellite appears not to move (it is moving but it follows the Earth’s rotation).

2. FlightRadar24 Santa tracker

https://www.flightradar24.com/R3DN053/335a9682

FlightRadar24 is a great website for telling you the answer to “what was that aircraft that’s just flown by?” It tracks the flight of aircraft all over the globe in real time, using a signal transmitted by the aircraft’s beacon (called a transponder) which announces where it is. Father Christmas’ sleigh has its own transponder too which is transmitting its location to receivers around the world.

An aircraft, or Santa’s sleigh, gets information about where it is from a GPS satellite (very similar to using a maps app on a smartphone and it telling you where you are and whether you should go left or right) and it then transmits this location info, along with other data, through its transponder.

There are thousands of receivers here on Earth, many of them in people’s homes and gardens (you can even apply to host a receiver antenna, or build your own with a Raspberry Pi) and whenever Santa’s sleigh passes over one of these ‘ground stations’ its signal is picked up and collected by FlightRadar24. The receivers are in different places so they are receiving the same signal at slightly different times and this information can be used to work out (by triangulation) how fast the sleigh is moving and in what direction.

Apparently Santa has been “able to extend the reach of his transponder by using the reindeer antlers as additional antenna” so the tracking should be fairly accurate.

FlightRadar24’s Santa Tracker animated icon.

3. Google Santa tracker

https://santatracker.google.com/

Google’s Santa Tracker has lots of games to play while you wait for Santa and his sleigh to take flight, including Code Boogie where you can try and program some dancing elves. You move little blocks (a bit like Scratch) to copy the dance moves and, if you get it right, it will show you the underlying JavaScript code.

Dave Holmes, a developer who works at Google and who works on the Santa Tracker project says “Santa Tracker launched in 2004, and has been an important project at Google ever since. While there’s a small core team dedicated to Santa, up to 20 or so Googlers volunteer to help make it happen every year, and it’s become a true community effort. It’s also a way for our developers to try things and see what Google products can do … I like to say that everything I’ve learned at Google, I learned from Santa.”

Google has also added some ‘Easter eggs‘ to its search page – try typing in Christmas or where is Santa to https://www.google.com/. You can also colour in some images online at their Christmas-themed Art Coloring Book, from Google’s Arts and Culture.

Further reading

The Googlers who help track Santa each Christmas (22 December 2021) Google Blog

4. Early internet Santa-themed humour

Back in the early 1990s email was very new but right from the start people used it to send each other amusing things. One of them was a rather literal consideration of the physics of a sleigh that is laden with gifts and a traditionally overweight Santa, led by a team of reindeer moving at unlikely speeds (after all Father Christmas has to get around the entire world to deliver presents, in just one day). The author (unknown) began –

“No known species of reindeer can fly. BUT there are 300,000 species of living organisms yet to be classified, and while most of these are insects and germs, this does not COMPLETELY rule out flying reindeer which only Santa has ever seen.”

But then goes on to point out that such a gift-delivery system would be working far beyond normal levels and would probably end in disaster, suggesting that –

“In short, they will burst into flame almost instantaneously, exposing the reindeer behind them, and create deafening sonic booms in their wake. The entire reindeer team will be vaporized within 4.26 thousandths of a second. Santa, meanwhile, will be subjected to centrifugal forces 17,500.06 times greater than gravity. A 250-pound Santa (which seems ludicrously slim) would be pinned to the back of his sleigh by 4,315,015 pounds of force.”

Fortunately Father Christmas has his own magic, meaning that we don’t need to worry too much about him disobeying the laws of physics. But he and his reindeer really deserve those cookies, milk and carrots!

You can read the full post here: The Physics of Santa and His Reindeer Snopes.com

The creation of 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.

Advert for our Advent calendar
Click the tree to visit our CS4FN Christmas Computing Advent Calendar

EPSRC supports this blog through research grant EP/W033615/1.

CS4FN Advent 2023 – Day 23: Father Christmas – checking his list, spotting the errors

Our CS4FN Christmas Computing Advent Calendar has now been running for 23 days! That’s one post every single day, matching a computing-themed blog post to the image on the front of the advent calendar. If you’d like to see how well we’ve managed this please scroll to the end where you can find all of our previous Advent Calendar posts.

Today’s picture is of Father Christmas who, we’ll assume, is re-checking his list and packing his sleigh ready for a long flight around the world, where he’ll be collecting cookies as he goes.

Father Christmas, about to do his pre-flight checks (twice).

As the song implies, he takes particular care over his list checking it twice to make sure there are no mistakes. In that respect he’s a little like computer scientists who put systems in place to make sure that when they send data to someone else that person can tell quickly if it’s arrived correctly. Today’s post is about reducing errors (and trying to avoid introducing errors). (We don’t know what data collection methods Father Christmas used though.)

1. Reducing errors: check digits

Once I’d reached the age of about 12 my parents started to let me go by myself to my friend’s house which was about a 15 minute walk away. When I arrived I would use my friend’s parents’ landline phone (with permission) to “give 3 rings” to my parents. This meant that I rang my parents’ number – but they didn’t answer, instead they let the phone ring three times and then I hung up. That way they knew the call was from me (our pre-agreed code) but no-one was charged to make or receive a call and they knew I’d arrived safely. (Obviously if the phone rang for longer they’d know it was probably from someone else and answer it).

Computer scientists also use an agreed code when sending data to another person or computer over a network – they want to make sure their data arrived safely too. Data is* sent as binary 1s and 0s and sometimes there’s a scrambling error in the transmission resulting in a 1 arriving as a 0, or a 0 arriving as a 1. A neat way to find out if this might have happened is to double-check what it was supposed to be, by using something called a parity bit (parity means ‘equal’) or check digit. This digit is added to each block of data you’re sending and computer scientists came up with this to let you check if the arriving data looks correct.

Here’s how it works

Suppose you want to send a message consisting of the numbers 6, 13, 2 and 12. These numbers can be converted into binary for data transmission: for example 6 in binary is 0110, 13 is 1101, 2 is 0010 and 12 is 1100. In the 5-row table below these are written in black (the top line is 6 and the fourth row is 12 – we’ll come to the red numbers in a moment).

We’ll now add a parity bit to each row, according to a rule, to make them five digits long.

The rule is that if the binary number has an odd number of 0s we even it up by adding another 0. If there’s an even number of 0s we just add a 1.

In the 1st row 0110 has an even number of zeroes so a 1 is added, 1101 has an odd number of zeroes so an extra 0 is added. Once we’ve checked all four rows we end up with a new parity column (shown in red on the right to make it stand out) on the right. We can also add a new parity row at the bottom as well, by doing the same thing for each of the numbers but read as a column. The first column has an even number of zeroes so we add a 1, the next just has one odd zero so we add a 0 there and so on.

We’ve added extra data to be sent, but this redundancy check (the extra info isn’t part of the message itself but helps support it) makes it easier for the person receiving the information to know if it’s OK or where any problem is.

01101
11010
00100
11001
10101

Let’s pretend you’ve just pressed send and your 1s and 0s are winging their way to your friend.

Binary image by Gerd Altmann from Pixabay

Unfortunately there was a small error in transmission and one of the numbers has ‘flipped’. Will your friend be able to tell which one it is? (Remember they don’t know what your message actually said, they can only see what’s arrived).

Here’s the (slightly scrambled) data that they receive.

01101
10010
00100
11001
10101

They can use the parity bit information to check each row and column. The first row looks fine –

two zeroes (even) and the parity bit one says 1 so that’s right. The second row looks wrong though – there’s an even number of zeroes so you’d expect a 1 in the parity bit – but it says 0, so you know there’s a mistake somewhere in row 2, but your friend won’t know where yet. They need to check the columns too.

Column 1 looks good, there are two zeroes and the parity bit says 1 so that’s correct. Column 2 has an even number of zeroes so you’d expect the parity bit to be 1, but it’s 0. So we know the problem is in Row 2 and Column 2. If we look at where they intersect we can see that a 1 has flipped to a 0, shown below in bold and blue. Your friend can correct the data and translate the binary back into the original numbers.

01101
10010
00100
11001
10101

You could try this with a friend or family member. Think up any 4 numbers between 0 (binary 0000) and 15 (binary 1111) then transmit your binary code with one error and see if they can work out which data bit flipped. Or… you can do it as a magic trick with a pack of cards (see the activity at the end).

*are, for the pedants 🙂

Further reading

Writing together: Clarence ‘Skip’ Ellis – about Clarence Ellis who used his knowledge of computing to bypass parity checks. The company he worked for was running out of punched cards (we’ll look at these in more depth later in the week) which the company’s computer used to store data. He was able to find a way for his colleagues to re-use the cards they already had, without triggering parity check problems – in doing so the payroll program could be run and everyone could get paid.

Handy binary cheat sheet. (Repeated after the dividing black line to show how the binary number is formed).

2. Trying not to introduce errors: when spellcheck goes worng

Another thing Father Christmas needs to do is check that he has the correct names of all the good children he’ll be giving presents to. He might use a spellchecker for this – this is something that reads the words in a document and compares them to a pre-set list. If a word is spelled in an unusual way the computer will alert you and ask if you want to change it to the one in the list or if you want to add it as a new spelling to the list. It would spot that I spelled ‘wrong’ wrongly in the heading for this section and ask if I meant ‘wrong’ instead of ‘worng’.

Find and replace

Sometimes people want to change a word in their document that appears many times. For example you might put TBA (which can mean ‘to be agreed’ or ‘to be arranged’) as a temporary placemarker in a Word document and later decide that every time the document says ‘TBA’ you’d prefer it to say “to be determined” instead. You don’t have to manually delete and retype every single instance of ‘TBA’, you can ‘automate’ the process using the Find and Replace option. Word will then find every ‘TBA’ automatically and change it to ‘to be determined’.

Sometimes this doesn’t go quite as expected.

In the UK the word ‘ass’ just means donkey but in the US it’s a slightly less polite word for bottom. A slightly more polite word might be ‘butt’ so you – being polite – want to make sure that any time the word ‘ass’ appears in a particular document it’s replaced with the word ‘butt’. This is unfortunate though if you happen to be the editor of a book about donkeys, which is now suddenly about bottoms.

Not donkeys’ bottoms, but zebras‘ – image by chezbeate from Pixabay

It’s much worse if your document talks about your class at school (clbutt?). Or perhaps it’s some homework about the assassination of an American president (buttbuttination?). Or maybe you need a new password (pbuttword), or even a new passport (pbuttport). Your document is now absolute gibberish and you would not pbutt any exams with that. Where’s spellcheck when you need it?

These types of mistakes are not that uncommon, I’ve even done it myself with the addresses of schools where I send copies of our CS4FN magazine to teachers.

I had a column in my address database which said things like UK, U.K. or United Kingdom and I decided I wanted them all to match and say “United Kingdom”. So… I used find and replace and asked my computer to turn every mention of ‘UK’ or ‘U.K.’ into United Kingdom. It worked beautifully… but I didn’t check the other columns.

I discovered my mistake when ‘Luke’ at a school on ‘Duke Road’ didn’t get his copy of the magazine and it was returned to me by the Post Office as the address was unreadable. I then had to correct both Lunited Kingdome’s name and his DUnited Kingdome Road address 😉 Oops.

Here are some other examples

and here’s what happened when someone changed TBA to ‘to be determined’ without noticing that the string of letters also appears in the word basketball.

3. Magic trick activity: parity check with playing cards

You could demonstrate the parity checking (that we did above with 1s and 0s) as a card trick – you just need an assistant and an audience. If you look closely at the pattern of cards in the picture above, and the pattern of 1s and 0s further up in this post you might notice a similarity…

Give a pack of shuffled cards to an audience member and ask them to deal out 16 cards in four rows either face up or face down (their choice). An example is shown in the left of the picture above. Tell them that in a moment you’re going to ask them to turn over a card while you’re not looking and later, you’ll tell them which card they flipped over. Announce that your assistant is going to make it ‘even harder’ by adding an extra column and row (I bet you can see where this is going). Of course, your assistant is adding a parity bit to the rows and columns (but your audience doesn’t know that) – an example is shown in the middle picture above.

Now avert your eyes (or get someone to blindfold you) and ask the audience member to turn over one card from the grid without telling you which. (Example in the picture on the right, above).

When you look at the grid you can quickly work out which one has been turned over, using exactly the same method we used with the 1s and 0s above.

This trick is a variation of one invented by New Zealand computer scientist, Tim Bell, and you can find more information about it and detailed instructions (as well as ideas to make it seem like you’re really a magician) in our free booklet called The Magic of Computer Science: card tricks special. The trick is called ‘The Out of Body Experience‘ and you can find it on pages 24-31 (pages 13 – 16 of the 33 page PDF).

The Magic of Computer Science 1

The creation of 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.

Other picture credits: the card (faces) comes from Wikipedia and the back is by Clker-Free-Vector-Images from Pixabay

Advert for our Advent calendar
Click the tree to visit our CS4FN Christmas Computing Advent Calendar

EPSRC supports this blog through research grant EP/W033615/1.

CS4FN Advent 2023 – Day 22: wreaths and rope memory – weave your own space age computer

Each day throughout December (until Christmas Day) we’ll be publishing a computing-themed blog post suggested by the picture on the front of our Advent Calendar. Today’s image on the door of the CS4FN Christmas Computing Advent Calendar is a Christmas wreath which made me think of wires and of weaving.

A Christmas wreath

You might remember that our first advent calendar post was about the links between coding and knitting. Today’s post looks at an even more literal version of that: core rope memory.

1. Core rope memory: the Apollo space mission’s woven computer memory

by Jo Brodie, QMUL.

Firstly it looks like this.

Rope memory from the Apollo Guidance Computer. Image from Wikipedia.

Secondly it got us to the Moon!

Probably the world’s first portable computer

Core rope memory was made up of small ‘eyelets’ or beads of metal called ferrite that can be magnetised (these ring-shaped magnets were known as cores) and copper wire which was woven through some of the eyelets but not others. An electrical current passing through the wires made the whole thing work. A wire that passed through an eyelet would be read as a binary 1 when the current was on but if it passed around one then it would be read as 0. This meant that a computer program, made up of sequences of 1s and 0s, could be permanently stored by the pattern that was woven. This formed the ‘fixed’ read-only memory in the Apollo guidance computer system; a different configuration (using smaller cores) made up its erasable magnetic-core memory.

This type of memory was woven in the 1960s for NASA’s Apollo moon mission by women who were skilled textile workers. They would work in pairs and use a special hollow needle to thread the copper wire through one magnetic core and then the other person would thread it back through a different one, following instructions from another program which indicated which of the eyelets to use.

That program was first developed on a computer (the sort that took up a whole room back then) and then translated into instructions for a machine which helped the weavers get the wire threads into the correct position. It was very difficult to undo a mistake so a great deal of care was taken to get things right the first time, especially as it could take up to two months to complete one block of memory. Some of the rope weavers were overseen by Margaret Hamilton, one of the women who developed the software used on board the spacecraft.

Margaret Hamilton, in 1969, standing next to listings of the software she and her MIT team produced for the Apollo project. Image from Wikipedia.

Several of these pre-programmed core rope memory units were combined and installed in the guidance computers of the Apollo mission spacecraft, to fly astronauts safely to the Moon and back.

NASA needed on-board guidance systems to control the spacecraft independently of Mission Control back on Earth. They needed something that didn’t take up too much room or weigh too much, that could survive the shaking and juddering of take-off and background radiation – core rope memory fitted the bill perfectly.

It packed a lot* of information into a small space and was very robust as it could only break if a wire came loose or one of the ferrite eyelets was damaged (which didn’t happen). To make sure though, the guidance computer’s electronics were protected by being sealed from the atmosphere. They survived and worked well, guiding the Landing Modules safely onto the Moon.

*well, not by modern standards! The guidance computer contained only around 70 kilobytes of read only memory.

2. A brief history of the digital revolution, part 1: from birth to the moon

by Lewis Dartnell. This post, from 2008, was originally published on the CS4FN website.

The Royal Institution Christmas Lectures 2008 invited you on a high tech trek to build the ultimate computer. The Christmas Lectures talk a lot about the current cutting-edge of computer technology, but what were things like in the early days of the digital revolution? The researcher for the 2008 Christmas Lectures, Lewis Dartnell, takes us through the story.

Electronic computers have come a long way since their birth only 50 years ago. One of the very first digital computers was built at the University of Manchester, a prototype called Manchester Mark I. The machine was revolutionary, with its complex processing circuits and storage memory to hold both the program being run and the data it was working on. The Mark I was first run on 21 June 1948 and paved the way as a universal computer that is truly versatile and can be reprogrammed at will, rather than being hard-wired for a single particular task.

A vacuum-tube (specifically a voltage-regulator tube) in use. Image from Wikipedia.

These earliest computers used technology called vacuum tubes, which were essentially just like filament light bulbs. Because they get so hot, such vacuum tubes were really power hungry and not very reliable. Typically, computers like the Manchester Mark I, processing using vacuum tubes, could only be run for a few hours at a time before one of the vacuum tubes broke and had to be replaced. The biggest break-through in modern computing came with the invention of the transistor, a small electronic component that can perform the same function as a vacuum tube, but is much more energy efficient and reliable. The beauty of the transistor is that computer scientists found ways of making them smaller and smaller, and to connect a number of them together into a single miniaturized processing board called an integrated circuit. These came to be known as microchips, and form the basis of all the computers made today.

A major drive for the development of microchip technology was the Apollo programme, begun in 1961 to land humans on the Moon. Although the vast majority of the complex calculations to do with plotting the trajectory and navigating to the moon were performed by enormous banks of computers back on Earth, it was crucial for the spacecraft to have their own on-board computer system. This was called the Apollo Guidance Computer (AGC), and both the command module and the lunar module, which actually made the descent to the surface of the moon, had one each. These ground-breaking computers provided the astronauts with crucial flight information, helped them make course corrections and to touch-down gently on the moon’s surface. Because it’s absolutely crucial to reduce the amount of mass and power usage on a spacecraft as far as possible, developing these guidance computers really pushed the technology in miniaturising integrated circuits.

The Display and Keyboard Interface (known as DSKY and pronounced Disky) of the Apollo mission’s guidance computer. Image from Wikipedia

The Apollo Guidance Computer not only helped drive the early development of microchips, but it also suffered one of the most infamous computer crashes in history. During the descent down to the Moon’s surface the AGC started displaying two error messages that the two astronauts, Neil Armstrong and Buzz Aldrin, weren’t familiar with. Engineers back at mission control on Earth quickly tried to identify the error code, and what it might mean for the lunar landing. Something that had never happened in any of the training simulations was now overloading the flow of data into the computer, the first time it had ever been used for real. Time was running out with only a limited amount of rocket fuel on-board and the Moon rushing up towards them. Luckily the computer entered a fail-safe mode, aborting low-priority calculations but able to continue with the critical tasks for the landing.

It wasn’t until the investigation afterwards that it was realized just how lucky Neil Armstrong and Buzz Aldrin had really been. The root of the problem was that the real attempt at the Moon landing was the first time an important radar system had been plugged into the computer, sending data into the AGC that wasn’t needed for the landing. This almost totally overloaded the computer, but by amazing luck, the amount of spare processing power built into the system for safety was almost exactly the amount being wasted by the un-needed radar, and the AGC didn’t crash completely.

The story of the digital revolution continues in part 2.

3. Activity 1 – make your own core rope memory

A nice craft activity is to create a cut-down version with beads and coloured threads. You string 8 beads (with a gap between them) on one thread to form a single ‘byte’ (of 8 binary bits). Then think of a short word or name. Using one piece of thread for each letter (easier to see if threads are coloured but not essential) you can weave it through or around each bead according to the binary code for each letter. If the thread goes through the bead that’s a 1, around the bead is 0.

To make the capital letter A (01000001, according to the conversion from binary to letters table) you’d go around the first bead, through the second, then around all the other beads until going through the eighth bead.

My name’s JO so mine would have only three threads (one to hold the 8 beads and two to spell my name). One of my threads would go around, through, around, around, through, around, through, around to ‘spell’ the capital letter J (01001010). Let’s hope you have a slightly longer name!

4. Activity 2 – create an origami laurel wreath

Not only do we have a wreath-themed activity in our back catalogue (!) but in a delightful coincidence this story also relates to Apollo (the Greek god). If you’re wondering what origami might have to do with computing it’s just another way of looking at algorithms and instructions. Also, decomposition (breaking a problem into smaller parts) because you can re-use the instructions needed for the laurel wreath to make other origami items. We like using ‘unplugged’ activities like this to demonstrate computing concepts.

Wreath instructions here.

Create an origami laurel wreath from nested triangles of paper.

The creation of 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.

Advert for our Advent calendar
Click the tree to visit our CS4FN Christmas Computing Advent Calendar

EPSRC supports this blog through research grant EP/W033615/1.

CS4FN Advent 2023 – Day 21: stars and celestial navigation

Every day from the 1st to the 25th of December this blog will publish a Christmas Computing post, as part of our CS4FN Christmas Computing Advent Calendar. On the front of the calendar for each day is a festive cartoon which suggests the post’s theme – today’s is a star, so today’s post is about finding your way: navigation.

Follow that star…

In modern cities looking up at the night sky is perhaps not as dramatic as it might have been in the past, or in a place with less light pollution. For centuries people have used stars and the patterns they form to help them find their way.

GPS Orbital Navigator Satellite (DRAGONSat), photograph by NASA

There are many ways our explorations of space have led to new technologies, though satellites have perhaps had the most obvious effect on our daily lives. Early uses were just for communication, allowing live news reports from the other side of the world, with networks that span the globe. More recently GPS – the Global Positioning System has led to new applications and now we generally just use our phones or satnav to point us in the right direction.

The very first computers

by Paul Curzon, QMUL. This post was first published on the CS4FN website.

Victorian engineer Charles Babbage designed, though never built the first mechanical computer. The first computers had actually existed for a long time before he had his idea, though. The British superiority at sea and ultimately the Empire was already dependent on them. They were used to calculate books of numbers that British sailors relied on to navigate the globe. The original meaning of the word computer was actually a person who did these calculations. The first computers were humans.

An American almanac from 1816. Image by Dave Esons from Pixabay

Babbage became interested in the idea of creating a mechanical computer in part because of computing work he did himself, calculating accurate versions of numbers needed for a special book: ‘The Nautical Almanac’. It was a book of astronomical tables, the result of an idea of Astronomer Royal, Nevil Maskelyne. It was the earliest way ships had to reliably work out their longitudinal (i.e., east-west) position at sea. Without them, to cross the Atlantic, you just set off and kept going until you hit land, just as Columbus did. The Nautical Almanac gave a way to work out how far west you were all the time.

Maskelyne’s idea was based on the fact that the angle from the moon’ to a person on the Earth and back to a star was the same at the same time wherever that person was looking from (as long as they could see both the star and moon at once). This angle was called the lunar distance.

The lunar distance could be used to work out where you were because as time passed its value changed but in a predictable way based on Newton’s Laws of motion applied to the planets. For a given place, Greenwich say, you could calculate what that lunar distance would be for different stars at any time in the future. This is essentially what the Almanac recorded.

Moon image by PollyDot from Pixabay

Now the time changes as you move East or West: Dawn gradually arrives later the further west you go, for example, as the Earth rotates the sun comes into view at different times round the planet). That is why we have different time zones. The time in the USA is hours behind that in Britain which itself is behind that in China. Now suppose you know your local time, which you can check regularly from the position of the sun or moon, and you know the lunar distance. You can look up in the Almanac the time in Greenwich that the lunar distance occurs and that gives you the current time in Greenwich. The greater the difference that time is to your local time, the further West (or East) you are. It is because Greenwich was used as the fixed point for working the lunar distances out, that we now use Greenwich Mean Time as UK time. The time in Greenwich was the one that mattered!

This was all wonderful. Sailors just had to take astronomical readings, do some fairly simple calculations and a look up in the Almanac to work out where they were. However, there was a big snag. it relied on all those numbers in the tables having been accurately calculated in advance. That took some serious computing power. Maskelyne therefore employed teams of human ‘computers’ across the country, paying them to do the calculations for him. These men and women were the first industrial computers.

Book of logarithms, image by sandid from Pixabay

Before pocket calculators were invented in the 1970s the easiest way to do calculations whether big multiplication, division, powers or square roots was to use logarithms (not to be confused with algorithm). The logarithm of a number is just the number of times you can divide it by 10 before you get to 1. Complicated calculations can be turned in to simple ones using logarithms. Therefore the equivalent of the pocket calculator was a book containing a table of logarithms. Log tables were the basis of all other calculations including maritime ones. Babbage himself became a human computer, doing calculations for the Nautical Almanac. He calculated the most accurate book of log tables then available for the British Admiralty.

The mechanical computer came about because Babbage was also interested in finding the most profitable ways to mechanise work in factories. He realised a machine could do more than weave cloth but might also do calculations. More to the point such a machine would be able to do them with a guaranteed accuracy, unlike people. He therefore spent his life designing and then trying to build such a machine. It was a revolutionary idea and while his design worked, the level of precision engineering needed was beyond what could be done. It was another hundred years before the first electronic computer was invented – again to replace human computers working in the national interest…but this time at Bletchley Park doing the calculations needed to crack the German military codes and so win the World War II.

The creation of 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.

Advert for our Advent calendar
Click the tree to visit our CS4FN Christmas Computing Advent Calendar

EPSRC supports this blog through research grant EP/W033615/1.

CS4FN Advent 2023 – Day 20: where’s it @? Gift tags and internet addresses

We’re doing a post a day for Advent 2023 with a mix of new articles and ones from our extensive CS4FN (Computer Science For Fun) archives. CS4FN has been going since 2005 and we have hundreds of articles to choose from, on a huge variety of topics.

We hope you’re enjoying our daily posts and if you’ve missed any just scroll to the end to catch up with the full set.

Today is Day 20 of the CS4FN Christmas Computing Advent Calendar and the picture today is a gift tag, which is a way of addressing a gift. So today’s post is all about internet addresses.

A festive gift-tag

1. Wh@ a history!

by Peter McOwan, QMUL. This article originally appeared on the CS4FN website.

The @ symbol of your email address first appeared in the Middle Ages. Monks would translate and copy books, but there were often problems when the bookbinders put the pages together in the wrong order. To get round this the monks repeated the last line of each page on the top of the next. This was very laborious so they came up with quick abbreviations even for small but common words like “ad”. It is Latin for “at” or “to”, and the medieval monks sometimes wrote ‘d’ like a mirrored ‘6’. The @ symbol was born. Morse code was updated in 2003 with a special code for @ (•–•-•) so that people could send email addresses by Morse code!

2. La Chiocchiola pasta

by Jo Brodie, QMUL.

In 1999 an Italian pasta company decided to create a pasta shape to celebrate the humble @ symbol. “@” had already been in use in email addresses for several decades (since the 1960s) but was becoming more popular as the use of email expanded and spread beyond businesses, the military and academia (universities etc).

@ symbol image by Pete Linforth from Pixabay

The ‘cyberpasta’ was called “La Chiocchiola” which is the Italian word for snail and you can probably see why they use that word to describe the similarly-shaped symbol. The pasta was awarded a prize from the National Museum of Pasta in Rome where samples of the @ shape were displayed and also given away free. Thanks to the Internet Archive you can even see a copy of the English language version of the pasta company’s website from May 1999 (only a few months after Google was founded).

3. Do @ me

by Jo Brodie, QMUL.

We can thank Ray Tomlinson for the earliest use of the @ symbol to separate an individual computer use from the network they’re using, and to act as an addressing system. Millions of people use Gmail and have an email address ending in gmail.com but (generally) each one gets only their own messages thanks to whatever unique set of letters and numbers is in front of the @. He chose the symbol because it’s a character that never appears in people’s name so could be used as a marker to separate the person from the machine or network. This neat and simple solution made it possible for people to send email anywhere in the world.

Further reading

How does email work? (31 May 2021) Namecheap – a detailed guide to what happens after you press SEND.

How telephone calls used to be connected (From Wikimedia Commons).

4. The internet’s address book

by Jo Brodie, QMUL.

Type any web address like www.google.com into a browser address bar, press enter and that address is instantly converted behind the scenes into a series of numbers.

The web address is known as a domain name and it’s an easy to remember version of the website’s address. The series of numbers is called the IP address (which stands for Internet Protocol). The human-readable domain name is translated into the machine-readable IP address by the DNS (Domain Name System) which acts as the internet’s ‘address book’. A DNS server can ‘look up’ the domain name in a list and find the corresponding IP address.

Everything that is connected to the internet has its own IP address including smartphones, laptops, networked printers etc and IP addresses have been in use for decades, helping direct traffic around the internet. We don’t usually see these IP addresses (we don’t generally need to!) but they look like a string of digits chunked into 4 groups, for example 198.51.100.0.

Each of those four ‘chunks’ is actually represented by an 8-digit binary number (or ‘octet’), so the range of each 8-digit octet goes from 00000000 (zero) to 11111111 (255). As 11111111 is the largest 8-digit binary number possible, no chunk can be above 255.

  • There are four octets (each containing 8 digits) in an IP address
  • Each of the octets can range from 00000000 to 11111111 (represented by 0 to 255)
  • Every IP address is therefore made up of a string of 32 (4 octets x 8 digits) ones or zeroes in a particular combination.

This means that there are 232 (two to the power of 32) possible IP address combinations giving an enormous number of over 4 billion addresses (which can be written as 4,294,967,296 or 4.294967296 × 109). Note that it’s “2” because in binary it’s either a 1 or a 0.

You might think that this would give us plenty of addresses to be going on with, but no! It was predicted that as more devices were connected to the internet, as its use expanded, we’d eventually start to run out and sure enough in 2011 we actually began to run out of these 32-bit addresses. Fortunately a new internet protocol (version 6, so it’s IPv6) was developed that uses 128 bits, which means there’s now a possible 2128 variations, giving an even more enormous number of 3.402823669 x 1038 addresses. Well, that should keep us going for a while!

Example IP address (from Wikimedia Commons).

5. Cracking a smart meter

by Paul Curzon, QMUL. This article originally appeared on the CS4FN website.

Smart electricity meters are clever meters that are connected to the Internet so they can send data back to the power company about your minute by minute electricity usage for billing purposes. If burglars could get hold of data from a smart electricity meter they can tell whether you are in or not (See Smart meter snooping).

How could anyone other than the power company get the data though? A German research team led by Dario Carluccio decided to see if it was possible. They have shown that the data from at least one kind of smart meter can be intercepted by anyone with the right software. Data needs to be encrypted – transmitted using an uncrackable code – to be safe from prying eyes. For the smart meter they examined that wasn’t done securely. They could not only intercept the data, they could even tamper with what was sent back to the company, which could be used, for example to lower their bills. All you needed was what is known as the ‘MAC address‘ of the smart meter. A MAC address is just the unique network name that a computer uses to identify itself- all computers connecting to the Internet have one. Unless special security is used any computer can pretend it is some other computer just by using the target computer’s MAC address when asked to identify itself. With the smart meter to send bogus data you essentially just need to get another computer to use the smart meter’s MAC address before sending data. The researchers demonstrated this by change the electricity usage data in a way that made the graph of peaks and troughs of usage read the message “U have been hacked”!

(A device’s MAC address is used locally, to identify it to your home broadband whereas the IP address identifies your device to the internet so that it can receive information from anyone, anywhere).

The creation of 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.

Advert for our Advent calendar
Click the tree to visit our CS4FN Christmas Computing Advent Calendar

EPSRC supports this blog through research grant EP/W033615/1.