There are several Pi Day’s (14 March: 3.14; 22 July: 22/7) so we should look at how on earth you compute a number like Pi (3.1.4159….). It has an infinite number of digits containing no repeating pattern so you can never tie it down exactly. One of my favourite ways for calculating pi was first devised by the Indian mathematician Mādhava of Sangamagrāma 600 years ago. He worked out an algorithm for working out Pi based on the maths of infinite series that he had also worked out.
Pi is one of the most useful numbers in all of maths. In school you come across it when working out the area or circumference of a circle, but it crops up all over the place including in practical computer science situations. Digital music, for example, relies on it deep down. Remember that the next time you stream your favourite music!
So how, 600 years ago did Mādhava manage to work out a much more accurate version of Pi than anyone before him? He had worked out that certain sequences of infinite numbers wouldn’t get bigger and bigger but would just get closer and closer to some specific number. In particular, he worked out one such sequence linked to pi.
π / 4 = 1 – 1/3 + 1/5 – 1/7 + 1/9 – …
Writing this a slightly different way it gives us a way of calculating pi itself
π = 4 – 4/3 + 4/5 – 4/7 + 4/9 – …
With an infinite number of terms, this gives an accurate value for pi. We can’t add an infinite number of numbers together though. Instead, we can use it to get a good answer. To get an approximation to pi we just follow an algorithm where we gradually add / subtract the next term. Each new calculation then gives us a better estimate of what pi is.
So to start with we just take the first term which says
π = 4 (very approximately)
That isn’t very good as it doesn’t get any digits right! Pi is closer to 3 than to 4. So its not looking hopeful! That doesn’t matter though as it is just a starting point. When we subtract the next term it gets a bit better
π = 4 – 4/3 = 2.6666…
Hmm. Now we have overshot the other way. However, we are closer to the real value of pi than we were. So don’t lose heart, keep going and add the next term
π = 4 – 4/3 + 4/5 = 3.46666…
And another term …
π = 4 – 4/3 + 4/5 – 4/7 = 2.895 …
And another term …
π = 4 – 4/3 + 4/5 – 4/7 + 4/9 = 3.339…
and so on.
The important thing to notice is that after each term included we get a more accurate answer, and we can keep adding terms for as long as we are happy to do the calculations. Mādhava (or his followers) obviously liked doing calculations so kept going until he had worked out pi accurate to 10 decimal places (3.1415926535…) : a new world record at the time beating the previous best of 6 decimal places by a Chinese astronomer Zhao Youqin using a different algorithm, That record had been set 80 years earlier but was smashed by 4 decimal places. This new record lasted for another 96 years. In doing these calculations Mādhava was acting as a ‘computer’ in the original meaning of the word: a human following an algorithm to do computation.
His algorithm is what computer scientists call an iterative algorithm. This kind of algorithm is used quite a lot by computer scientists as it gives a general way of getting a good enough (if not perfect) answer to a problem that otherwise is hard (or impossible) to get a perfect answer to in a reasonable time. You start with a good guess and then gradually refine the answer until you are happy that it is accurate enough. These algorithms can be straightforward to code as it is just running a loop doing calculations that refine the answer. Mādhava was happy with 10 decimal places of accuracy but he could have kept going. The trouble is this is a very slow algorithm. As we saw with the first few iterations above, it takes a long time even to home in on the first digit being 3! Every new digit took a lot of extra work to get right. When calculating machines and then computers were invented it became easier to use slow algorithms like this, but even with a faster computer it is still better to have a faster algorithm. Now far faster algorithms have been invented and the world record at the time of writing gives pi accurate to 105,000,000,000,000 decimal places!
Mādhava would have needed to really like doing calculations (and have discovered the secret to eternal life) to have calculated pi that accurately. 600 years ago his world record for pi was still an amazing achievement.
Scientific fraud is worryingly common, though rarely talked about. It has been happening for years, but now Artificial Intelligence programs could supercharge it. If they do that could undermine Science itself.
Investigators of scientific fraud have found that large numbers of researchers have manipulated their results, invented data, or even produced nonsensical papers in the hope that no one will look closely enough to notice. Often, no one does. The problem is that science is built on the foundation of all the research that has gone before. If we can no longer trust that past research is legitimate, the whole system of science begins to break down. AI has the potential to supercharge this process.
We’re not at that point yet, luckily. But there are concerning signs that generative AI systems like ChatGPT and DALLE-E might bring us closer. By using AI technology, producing fraudulent research has never been easier, faster, or more convincing. To understand, let’s first look at how scientific fraud has been done in the past.
How fraud happens
Until recently, fraudsters would need to go through some difficult steps to get a fraudulent research paper published. A typical example might look like this:
Step 1: invent a title
Fraudsters look for a popular but very broad research topic. We’ll take an example of a group of fraudsters known as the Tadpole Paper Mill. They published papers about cellular biology. To choose a new paper to create, the group would essentially use a simple generator, or algorithm, based on a template. This uses a simple technique first used by Christopher Strachey to write love letters in an early “creative” program in the 1950s.
For each “hole” in the template a word is chosen from a word list.
Pick the name of a molecule
Either a protein name, a drug name or an RNA molecule name
Next, the fraudsters create the text of the paper. To do this, they often just plagiarise and lightly edit previous similar papers, substituting key words in from their invented title perhaps. To try to hide the plagiarism, they automatically swap out words, replacing them with synonyms. This often leads to ridiculous (and kind of hilarious) replacements, like these found in plagiarised papers:
“Big data” –> “Colossal information”
“Cloud computing” –> “Haze figuring”
“Developing countries” –> “Creating nations”
“Kidney failure” –> “Kidney disappointment”
Step 3: add in the results
Lastly, the fraudsters need to create results for the fake study. These usually appear in papers in the form of images and graphs. To do this, the fraudsters take the results from several previous papers and recombine them into something that looks mostly real, but is just a Frankenstein mess of other results that have nothing to do with the current paper.
A new paper is born
Using that simple formula, fraudsters have produced thousands of fabricated articles in the last 10 years. Even after a vast amount of effort, the dedicated volunteers who are trying to clean up the mess have only caught a handful.
However, committing fraud like this successfully isn’t exactly easy, either: the fraudsters still need to come up with a research idea, write the paper themselves without copying too much from previous research, and make up results that look convincing—at least at first glance.
AI: Adding fuel to the fire
So what happens when we add modern generative AI programs into the mix? They are Artificial Intelligence programs like ChatGPT or DALL-E that can create text or pictures for you based on written requests.
Well, the quality of the fraud goes up, and the difficulty of producing it goes way down. This is true for both text and images.
Let’s start with text. Just now, I asked ChatGPT-4 to “write the first two paragraphs of a research paper on a cutting edge topic in psychology.” I then asked it to “write a fake results table that shows a positive relationship between climate change severity and anxiety”. I won’t copy the whole thing—in part because I encourage you to try this yourself to see how it works (not to actually create a fake paper!)—but here’s a sample of what it came up with:
“As the planet faces increasing temperatures, extreme weather events, and environmental degradation, the mental health repercussions for populations worldwide become a crucial area of investigation. Understanding these effects is vital for developing strategies to support communities in coping with the psychological challenges posed by a changing climate.”
As someone who has written many psychology research papers, I would find the results very difficult to identify as AI-generated—it looks and sounds very similar to how people in my field write, and it even generated Python code to analyse the fake data. I’d need to take a really close look at the origin of the data and so on to figure out that it’s fraudulent.
But that’s a lot of work required from me as a fraud-buster. For the fraudster, doing this takes about 1 minute, and would not be detected by any plagiarism software in the way previous kinds of fraud can be. In fact, this might only be detected if the fraudsters make a sloppy mistake, like leaving in a disclaimer from the model as in the paper caught which included the text
“[Please note that as an AI language model, I am unable to generate specific tables or conduct tests, so the actual resutls should be included in the table.]”!
Generative AIs are not close to human intelligence, at least not yet. So, why are they so good at producing convincing scientific research, something that’s commonly seen as one of the most difficult things humans can do? Two reasons play a big part: (1) scientific research is very structured, and (2) there’s a lot of training data. In any given field of research, most papers tend to look pretty similar—an introduction section, a method describing what the researchers did, a results section with a few tables and figures, and a discussion that links it back to the wider research field. Many journals even require a fixed structure. Generative AI programs work using Machine Learning – they learn from data and the more data they are given the better they become. Give a machine learning program millions of images of cats, telling it that is what they are, and it can become very good at recognising cats. Give it millions of images of dogs and it will be able to recognise dogs too. With roughly 3 million scientific papers published every year, generative AI systems are really good at taking these many, many examples of what a scientific report looks like, and producing similar sounding, and similarly structured pieces of text. They do it by predicting what word, sentence and paragraph would be good to come next based on probabilities calculated from all those examples.
Trusting future research
Most research can still be trusted, and the vast majority of scientists are working as hard as they can to advance human knowledge. Nonetheless, we all need to look carefully at research studies to ensure that they are legitimate, and we should be on extra alert as generative AI becomes even more powerful and widespread. We also need to think about how to improve universities and research culture generally, so that people don’t feel like they need to commit scientific fraud—something that usually happens because people are desperate to get or keep a job, or be seen as successful and reap the rewards. Somehow we need to change the game so that fraud no longer pays.
What do you think? Do you have ideas for how we can prevent fraud from happening in the first place, and how can we better detect it when it does occur? It is certainly an important new research topic. Find a solution and you could do massive good. If we don’t find solutions then we could lose the most successful tool human-kind has ever invented that makes all our lives better.
In school we learn about the maths that others have invented: results that great mathematicians like Euclid, Pythagoras, Newton or Leibniz worked out. We follow algorithms for getting results they devised. Ada Lovelace was actually taught by one of the great mathematicians, Augustus De Morgan, who invented important laws, ‘De Morgan’s laws’ that are a fundamental basis for the logical reasoning computer scientists now use. Real maths is about discovering new results of course not just using old ones, and the way that is done is changing.
We tend to think of maths as something done by individual geniuses: an isolated creative activity, to produce a proof that other mathematicians then check. Perhaps the greatest such feat of recent years was Andrew WIles’ proof of Fermat’s Last Theorem. It was a proof that had evaded the best mathematicians for hundreds of years. Wiles locked himself away for 7 years to finally come up with a proof. Mathematics is now at a remarkable turning point. Computer science is changing the way maths is done. New technology is radically extending the power and limits of individuals. “Crowdsourcing” pulls together diverse experts to solve problems; computers that manipulate symbols can tackle huge routine calculations; and computers, using programs designed to verify hardware, check proofs that are just too long and complicated for any human to understand. Yet these techniques are currently used in stand-alone fashion, lacking integration with each other or with human creativity or fallibility.
‘Social machines’ are a whole new paradigm for viewing a combination of people and computers as a single problem-solving entity. The idea was identified by Tim Berners-Lee, inventor of the world-wide web. A project led by Ursula Martin at the University of Oxford explored how to make this a reality, creating a mathematics social machine – a combination of people, computers, and archives to create and apply mathematics. The idea is to change the way people do mathematics, so transforming the reach, pace, and impact of mathematics research. The first step involves social science rather than maths or computing though – studying what working mathematicians really do when working on new maths, and how they work together when doing crowdsourced maths. Once that is understood it will then be possible to develop tools to help them work as part of such a social machine.
The world changing mathematics results of the future may be made by social machines rather than solo geniuses. Team work, with both humans and computers is the future.
– Ursula Martin, University of Oxford and Paul Curzon, Queen Mary University of London
The history of computational devices: automata, core rope memory (used by NASA in the Moon landings), Charles Babbage’s Analytical Engine (never built) and Difference Engine made of cog wheels and levers, mercury delay lines, standardising the size of machine parts, Mary Coombs and the Lyons tea shop computer, computers made of marbles, i-Ching and binary, Ada Lovelace and music, a computer made of custard, a way of sorting wood samples with index cards and how to work out your own programming origin story.
Subscribe to be notified whenever we publish a new post to the CS4FN blog.
This blog is funded by EPSRC on research agreement EP/W033615/1.
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.
“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.
————————-
“…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.”
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 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 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 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…
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.
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…
Subscribe to be notified whenever we publish a new post to the CS4FN blog.
This blog is funded by EPSRC on research agreement EP/W033615/1.
The Lego Computer Science posts were 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.
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… 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 DataValues 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. 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. 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…).
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.
“I’m in a choir”. “Really, what do you sing?” “I did a blackbird last week, but I think I’m going to be woodpecker today, I do like a robin though!”
This is no joke! Marcus Coates a British artist, got up very early, and working with a wildlife sound recordist, Geoff Sample, he used 14 microphones to record the dawn chorus over lots of chilly mornings. They slowed the sounds down and matched up each species of bird with different types of human voices. Next they created a film of 19 people making bird song, each person sang a different bird, in their own habitats, a car, a shed even a lady in the bath! The 19 tracks are played together to make the dawn chorus. See it on YouTube below.
Marcus didn’t stop there, he wrote a new bird song score. Yes, for people to sing a new top ten bird hit, but they have to do it very slowly. People sing ‘bird’ about 20 times slower than birds sing ‘bird’ ‘whooooooop’, ‘whooooooop’, ‘tweeeeet’. For a special performance, a choir learned the new song, a new dawn chorus, they sang the slowed down version live, which was recorded, speeded back up and played to the audience, I was there! It was amazing! A human performance, became a minute of tweeting joy. Close your eyes and ‘whoop’ you were in the woods, at the crack of dawn!
Computationally thinking a performance
Computational thinking is at the heart of the way computer scientists solve problems. Marcus Coates, doesn’t claim to be a computer scientist, he is an artist who looks for ways to see how people are like other animals. But we can get an idea of what computational thinking is all about by looking at how he created his sounds. Firstly, he and wildlife sound recordist, Geoff Sample, had to focus on the individual bird sounds in the original recordings, ignore detail they didn’t need, doing abstraction, listening for each bird, working out what aspects of bird sound was important. They looked for patterns isolating each voice, sometimes the bird’s performance was messy and they could not hear particular species clearly, so they were constantly checking for quality. For each bird, they listened and listened until they found just the right ‘slow it down’ speed. Different birds needed different speeds for people to be able to mimic and different kinds of human voices suited each bird type: attention to detail mattered enormously. They had to check the results carefully, evaluating, making sure each really did sound like the appropriate bird and all fitted together into the Dawn Chorus soundscape. They also had to create a bird language, another abstraction, a score as track notes, and that is just an algorithm for making sounds!
Fun to try
Use your computational thinking skills to create a notation for an animal’s voice, a pet perhaps? A dog, hamster or cat language, what different sounds do they make, and how can you note them down. What might the algorithm for that early morning “I want my breakfast” look like? Can you make those sounds and communicate with your pet? Or maybe stick to tweeting? (You can follow @cs4fn on Twitter too).
Enjoy the slowed-down performance of this pet starling which has added a variety of mimicked sounds to its song repertoire.
You often hear about unethical behaviours, be it in politicians or popstars, but getting to grips with ethics, which deals with issues about what behaviours are right and wrong, is an important part of computer science too. Find out about it and at the same time try our ethical puzzle below and learn something about your own ethics…
Is that legal?
Ethics are about the customs and beliefs that a society has about the way people should be treated. These beliefs can be different in different countries, sometimes even between different regions of the same country, which is why it’s always important to know something about the local area when going on holiday. You don’t want to upset the local folk. Ethics tend to form the basis of countries’ laws and regulations, combining general agreement with practicality. Sticking your tongue out may be rude and so unethical, but the police have better things to do than arrest every rude school kid. Similarly, slavery was once legal, but was it ever ethical? Laws and ethics also have other differences; individuals tend to judge unethical behaviour, and shun those who behave inappropriately, while countries judge illegal behaviour – using a legal system of courts, judges and juries to enforce laws with penalties.
Dilemmas, what to do?
Now imagine you have the opportunity to go treading on the ethical and legal toes of people across the world from the PC in your home. Suddenly the geographical barriers that once separated us vanish. The power of computer science, like any technology, can be used for good or evil. What is important is that those who use it understand the consequences of their actions, and choose to act legally and ethically. Understanding legal requirements, for example contracts, computer misuse and data protection are important parts of a computer scientist’s training, but can you learn to be ethical?
Computer scientists study ethics to help them prepare for situations where they have to make decisions. This is often done by considering ethical dilemmas. These are a bit like the computer science equivalent of soap opera plots. You have a difficult problem, a dilemma, and have to make a choice. You suddenly discover you have a unknown long lost sister living on the other side of the Square, do you make contact or not, (on TV this choice is normally followed by a drum roll as the episode ends).
Give it a go
Here is your chance to try an ethical dilemma for yourself. Read the alternatives and choose what you would do in this situation. Then click on the poll choice. Like all good ‘personality tests’ you find out something about yourself: in this case which type of ethical approach you have in the situation according to some famous philosophers. There are also some fascinating facts to impress your mates. We’ll share the answers tomorrow.
Your Dilemma and your ethical personality
You are working for a company who are about to launch a new computer game. The adverts have gone out, the newspapers and TV are ready for the launch … then the day before you are told that there is a bug, a mistake, in the software. It means players sometimes can’t kill the dragon at the end of the game. If you hit the problem the only solution is to start the final level again. It can be fixed they think but it will take about a week or so to track it down. The computer code is hard to fix as it’s been written by 10 different people and 5 of them have gone on a back-packing holiday so can’t be contacted.
Subscribe to be notified whenever we publish a new post to the CS4FN blog.
This blog is funded by EPSRC on research agreement EP/W033615/1.
The answers
If you picked Option 1
1) Go ahead and launch. After all, there are still plenty of parts to the game that do work and are fun, there will always be some errors, and for this game in particular thousands have been signing up for text alerts to tell them when it’s launched. It will make many thousands happy.
That means you follow an ethical approach called ‘Act utilitarianism’.
Act Happy
The main principle of this theory, put forward by philosopher John Stuart Mill, is to create the most happiness (another name for happiness here is utility thus utilitarianism). For each situation you behave (act) in a way that increases the happiness of the largest number of people, and this is how you decide what is wrong or right. You may take different actions in similar situations. So you choose to launch a flawed game if you know that you have pre-sales of a hundred thousand, but another time decide to not launch a different flawed game where there are only one thousand pre-sales, as you wont be making so many people unhappy. It’s about considering the utility for each action you take. There is no hard and fast rule.
If you picked Option 2
2) Cancel the launch until the game is fixed properly, no one should have to buy a game that doesn’t work 100 per cent.
That means you follow an ethical approach called ‘Duty Theory’
Do your Duty
Duty theories are based on the idea of there being universal principles, such as ‘you should never ever lie, whatever the circumstances’. This is also known as the dentological approach to ethics (philosophers like to bring in long words to make simple things sound complicated!). The German philosopher Emanuel Kant was one of the main players in this field. His ‘Categorical Imperative’ (like I said long words…) said “only act in a way that you would want everyone else to act” (…simple idea!). So if you don’t think there should ever be mistakes in software then don’t make any yourself. This can be quite tough!
If you picked Option 3
3) Go ahead and launch. After all it’s almost totally working and the customers are looking forward to it. There will always be some errors in programs: it’s part of the way complicated software is, and a delay to game releases leads to disappointment.
You would be following the approach called ‘Rule utilitarianism’.
Spread a little happiness
Say something nice to everyone you meet today…it will drive them crazy
The main principle of this flavour of utilitarianism theory, put forward by philosopher Jeremy Bentham, is to create the most happiness (happiness here is called utility thus utilitarianism). You follow general rules that increase the happiness of the largest number of people, and this is how you decide what’s wrong or right. So in our dilemma the rule could be ‘even if the game isn’t 100% correct, people are looking forward to it and we can’t disappoint them’. Here the rule increases happiness, and we apply it again in the future if the same situation occurs.
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.
Image drawn and digitised by Jo Brodie.
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! Image drawn and digitised by Jo Brodie.
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“.
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.
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. Edge-notched Card (without the edges notched) by Daniel MacKay, image has been released into the public domain (CC0).
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.
This is a practical 'wood identification kit'.
The manual multi-access key is poked through different holes on the identification cards, which represent specific characteristics of the wood, to help determine which one you’re handling. pic.twitter.com/CLNkFyRlMJ
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. Randlochkarte mit zwei Schlitzungen (handgemalt) [Perforated card with two slots (hand-painted)] by Peter Frankfurt, image has been released into the public domain (CC0).
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.
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.
cs4fn 