Category: Computer Architecture

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.

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

by Paul Curzon, Queen Mary University of London

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

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)

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.

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 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

More on …

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

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)

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 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

More on …

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

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…

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

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.

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 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

More on …

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.

Getting off the beach, fast

by Paul Curzon, Queen Mary University of London

Paul goes on holiday and sees how a car park can work like a computer.

Fibre optic cables image by Chaitawat Pawapoowadon from Pixabay

Computers get faster and faster every year. How come? Because computer scientists and electronic engineers keep thinking up new tricks, completely new ways to make them go faster. One way has been to shrink the components so signals don’t have as far to go. Another is to use the same trick they were using in a beach car park I came across on holiday.

Woolacombe coast image by adammphillip5 from Pixabay

Woolacombe Sands in Devon is one of the most popular beaches around. There is a great expanse of beautiful sand as well as rocks for kids to climb on and good surfing too. The weather is even good there – well most of the time. The car park, right on the edge of the beach fills in the morning. Since most people arrive early and stay all day it’s a standard price of £5.50 for the day. Entry and exit barriers control the numbers. The entry barrier only allows a car to go in if there is a space and another allows people out when they have paid.

That’s where there is a problem though. The vast majority of people leave around 5pm as the ice cream vans pack up and it’s time to look for dinner. The machine only takes coins, and you insert the money from your car at the barrier. Each driver has to fumble with 5 one-pound coins and a 50p and that takes time. Once the current car moves on out there is then another delay as the driver behind pulls forward to get into a position to put their money in. Without some thought it would lead to long queues behind. Not only that it wouldn’t be very green. Cars are at there worst pumping out pollution when in a jam.

The last thing you want to do to a family who’ve had a great day on your beach is then irritate them by clogging them up in a traffic jam when they try to leave. So what do you do? How can you speed things up (and make sure you aren’t just moving the queue to the morning or to some other ticket machine somewhere else)?

The problem is similar to one in designing a computer chip. Think of the cars as data waiting to be processed (perhaps as part of a calculation) and the barrier as a processing unit where some manipulation of that data is needed. Data waiting to be processed has to be fetched before it can be used, just as the cars have to move up to the barrier before the driver can pay. The fact that the problems are so similar suggests that a solution to one may also be a a solution to the other.

Speed it up

There are lots of ways you could change the system to improve the speed of cars being processed in the car park. This speed that data passes through a system is called the ‘throughput’ of the system. Woolacombe have thought of a simple way to improve their throughput. They put a person with a bit of change next to the barrier to help the drivers. This allows them to keep the relatively simple barrier system they have. It also has advantages in keeping the money in one place and being a foolproof way of ensuring there is a space for everyone who enters. It still maintains all the safeguards of the ticket barrier though. How can that one person speed things up?

What would you do?

So what would YOU do if you were that person? Would you speed things up? Or would you just stand there powerless watching the misery of all those families?

Pound coins image by PublicDomainPictures from Pixabay

The first thing you could do is to stand by the machine and take the change off the driver and insert it yourself. That will speed things up a little bit because it takes longer for drivers to put the money in as they have to stretch out the window of a car. Also if the driver only has a five pound note you can take it and just insert coins from your change bag rather than wasting time passing it back to the driver to then insert. Similarly if the driver only has 50 pence pieces say, rather than wasting time inserting 10 of them you can take them and insert 5 one-pound coins.

You’ve done some good, and removed problems of the slow people inserting coins but you haven’t really solved the bad problems. Cars aren’t moving at all while you are inserting the 6 coins, and after each car moves through the barrier you are doing nothing but waiting for the next car to pull forward. In an ideal system, with the best throughput, the cars barely stop at all and you are constantly busy.

A Pipeline of Cars

It turns out you can do something about that. It’s called pipelining. There is a way you can be busy dealing with the next car even before it’s got to you. You just have to get ahead of yourself!

Cars image by Ambady Sasi from Pixabay

How? Before the first car arrives, insert 5 pound coins into the machine and wait. As the driver gets to you and gives you the money, insert his or her 50p, keeping the rest. The barrier opens immediately for the driver who barely has to stop. Better still you are now holding 5 pound coins that you can insert as the next car arrives, leaving you back in an identical situation. That means the next car can drive straight through too, and you are constantly busy as long as there are cars arriving.

Speedy data

So you’ve helped the families leaving the beach, but how might a similar trick speed up a computer? Well you can do a similar thing in the way you get a computer processor to execute the instructions from a program. Suppose your program requires the processor to get some numbers from storage, process them (perhaps multiplying the numbers together) and then store the result somewhere else for later use. Typically a program might do that over and over again, varying where the data comes from and how it is processed.

Early computers would do each instruction in turn – doing the fetching, processing and storing of one instruction before starting the next. But that is just like a car in our car park coming to the barrier, being processed and leaving before the next one moves. Can we pull off the same trick to speed things up? Well, yes of course.

All you need to do is overlap the separate parts. Just as at any time in the car park a car will be driving out, a second will be handing over money and a third pulling forward, the same can happen in the computer. As the first instruction’s result is being stored, the next instruction can already be being processed and the data from the one after that can be fetched from memory. Just by reorganising the way the work is done, we have roughly tripled the speed of our computer as now three things are happening at once.

What we have done is set up a ‘pipeline’ – with a series of instructions all flowing through it, being executed, at the same time. Woolacombe has a pipeline of cars, but in a computer we pipeline data. Either way things get done faster and people are happier.

Computer science happens in some unexpected places – even at the beach – but then perhaps that isn’t so surprising given computers are made of sand!

Toy truck on sand image by Sebastian Mey from Pixabay

This article was originally published on the CS4FN website.

Other beach-themed articles on this blog include how the origins of how Paul learned to program while on holiday (“The beach, the missionary and my origin myth”) and messages hidden (steganography) within the stripes of deckchairs (“Encrypted deckchairs”).

The beach, the missionary and my origin myth
Encrypted Deckchairs

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

A PC Success

by Paul Curzon, Queen Mary University of London

An outline of a head showing the brain and spinal column on a digital background of binary and circuitry

Image by Gerd Altmann from Pixabay

We have moved on to smartphones, tablets and smartwatches, but for 30 years the desktop computer ruled, and originally not just any desktop computer, the IBM PC. A key person behind its success was African American computer scientist, Mark Dean.

IBM is synonymous with computers. It became the computing industry powerhouse as a result of building large, room-sized computers for businesses. The original model of how computers would be used followed IBM’s president, Thomas J Watson’s, supposed quote that “there is a world market for about five computers.” They produced gigantic computers that could be dialled into by those needed computing time. That prediction was very quickly shown to be wrong, though, as computer sales boomed.

Becoming more personal

Mark Dean was the first African American
to receive IBM’s highest honour.

By the end of the 1970s the computing world was starting to change. Small, but powerful, mini-computers had taken off and some companies were pushing the idea of computers for the desktop. IBM was at risk of being badly left behind… until they suddenly roared back into the lead with the IBM personal computer and almost overnight became the world leaders once more, revolutionising the way computers were seen, sold and used. Their predictions were still a little off with initial sales of the IBM PC 8 times more than they expected! Within a few years they were selling many hundreds of thousands a year and making billions of dollars. Soon every office desk had one and PC had become an everyday word used to mean computer.

Get on the bus

So who was behind this remarkable success? One of the design team who created the IBM PC was Mark Dean. As a consequence of his work on the PC, he became the first African American to be made an IBM fellow (IBM’s highest honour). One of his important contributions was in leading the development of the PC’s bus. Despite the name, a computer bus is more like a road than a vehicle, so its other name of data highway is perhaps better. It is the way the computer chip communicates with the outside world. A computer on its own is not really that useful to have on your desktop. It needs a screen, keyboard and so on. A computer bus is a bit like your nervous system used to send messages from your brain around your body. Just as your brain interacts with the world receiving messages from your senses, and allowing you to take action by sending messages to your muscles, all using your nervous system, a computer chip sends signals to its peripherals using the bus. Those peripherals include things like mouse, keyboard, printers, monitors, modems, external memory devices and more; the equivalents of its way of sensing the world and interacting with it. The bus is in essence just a set of connectors into the chip so wires out with different allocated uses and a set of rules about how they are used. All peripherals then follow the same set of rules to communicate to the computer. It means you can easily swap peripherals in and out (unlike your body!) Later versions of the PC bus, that Mark designed, ultimately became an industry standard for desktop computers.

Mark can fairly be called a key member of that PC development team, given he was responsible for a third of the patents behind the PC. He didn’t stop there though. He has continued to be awarded patents, most recently related to artificial neural networks inspired by neuroscience. He has moved on from making computer equivalents of the nervous system to computer equivalents of the brain itself.

More on …

Related Magazines …

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

Mark Dean: An Inspiration

by Dean Miller, former student QMUL

From the archive: This article is an edited version of one of the 2006 winning essays from the Queen Mary University of London, Department of Computer Science, first year essay competition.

Mark Dean

May I ask you a question? When you think of the computer what names ring a bell? Bill Gates? Or for those more in touch with the history behind computers maybe Charles Babbage is a familiar name? May I ask you another question please? Do you know who Dr Mark Dean is? No, well you should. Do not worry yourself though, you are definitely not alone. I did not know of him either.

Allow me to enlighten you..

Mark Dean is in my opinion a very creative and inspirational black computer scientist. He is a vice-president at IBM and holds 3 of IBM’s first 9 patents on the personal computer. He has over 30 patents pending. He won the Black Engineer of the Year Presidents Award and was made an IBM fellow in 1995. An IBM fellow is IBM’s highest technical honor. Only 50 of IBM’s employee’s are fellows and Mark Dean was the first black one. Prior to joining IBM in 1980 he earned degrees in Electrical Engineering before going back to school to gain a PhD in the field from Stanford University. He was born in 1957 in Jefferson City, Tennessee and was one of the first black students to attend Jefferson City High School. He was an exceptional student and enjoyed athletics. Early manifestations of his desire to create were shown when he and his father built a tractor from scratch when he was just a boy.

Upon joining IBM Mark Dean and a partner led the team that developed the interior architecture (ISA systems bus) which allowed devices like the keyboard and printer to be connected to the motherboard making computers a part of our lives. It was that which earned him a spot in the National Inventors Hall of Fame. While at IBM he has been involved in numerous positions in computer system hardware architecture and design. He was responsible for IBM’s research laboratory in Austin, Texas where he focused on developing high performance microprocessors, software, systems and circuits. It is here where he made history by leading the team that built a gigahertz chip which did a billion calculations per second. In 2004, he was chosen as one of the 50 most important Blacks in Research Science.

He and his father built a tractor
from scratch when he was just a boy

I think that such a man should be well recognized in computer science, especially to black computer science students because from what I can see we are rare. We as a minority need an inspirational figure like Mark Dean. He inspires me, I wanted to share that with you. Before this small article it is very probable you had no knowledge of this man. So if there comes a time where you are asked about important names in the field of computers, I hope Dr Mark Dean springs to mind and rings a bell for you to hear loud and clear.

More on …

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