Tag: Alan Turing

Dr Who? Dr You???

Image by Eduard Solà, CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0, via Wikimedia Commons

When The Doctor in Dr Who knows their time is up – usually because they’ve been injured so badly that they are dying – like all Time Lords, they can regenerate. They transform into a completely different body. They ends up with a new personality, new looks, a new gender, even new teeth. Could humans one day regenerate too?

Your body is constantly regenerating itself too. New cells are born to replace the ones that die. Your hair, nails and skin are always growing and renewing. Every year, you lose and regain so much that you could make a pile of dead cells that would weigh the same as your body. And yet with all this change, every morning you look in the mirror and you look and feel the same. No new personality, no new teeth. How does the human body keep such incredible control?

Here’s another puzzler. Even though our cells are always being renewed, you can’t regrow your arm if it gets cut off. We know it’s not impossible to regrow body parts: we do it for small things like cells, including whole toe nails and some animals like lizards can regrow tails. Why can we regrow some things but not others?

Creation of the shape

All of those questions are part of a field in biology called morphogenesis. The word is from Greek, and it means ‘creation of the shape’. Scientists who study morphogenesis are interested in how cells come together to create bodies. It might sound a long way from computing, but Alan Turing became interested in morphogenesis towards the end of his life. He was interested in finding out about patterns in nature – and patterns were something he knew a lot about as a mathematician. A paper he wrote in 1951 described a way that Turing thought animals could form patterns like stripes and spots on their bodies and in their fur. The mechanisms he described explain how uniform cells could end up turning into different things so not only different patttens in different places, but different body parts in different places. That work is now the foundation of a whole sub-discipline of biology.

Up for the chop

Turing died before he could do much work on morphogenesis, but lots of other scientists have taken up the mantle. One of them is Alejandro Sánchez Alvarado, who was born in Venezuela but works at the Stowers Institute for Medical Research in Kansas City, in the US. He is trying to get to the bottom of questions like how we regenerate our bodies. He thinks that some of the clues could come from working on flatworms that can regenerate almost any part of their body. A particular flatworm, called Schmidtea mediterranea, can regenerate its head and its reproductive organs. You can chop its body into almost 280 pieces and it will still regenerate.

A genetic mystery

The funny thing is, flatworms and humans aren’t as different as you might think. They have about the same number of genes as us, even though we’re so much bigger and seemingly more complicated. Even their genes and ours are mostly the same. All animals share a lot of the same, ancient genetic material. The difference seems to come from what we do with it. The good news there is that as the genes are mostly the same, if scientists can figure out how flatworm morphogenesis works, there’s a good chance that it will tell us something about humans too.

One gene does it all

Alejandro Sánchez Alvarado did one series of experiments on flatworms where he cut off their heads and watched them regenerate. He found that the process looked pretty similar to watching organs like lungs and kidneys grow in humans as well as other animals. He also found that there was a particular gene that, when knocked out, takes away the flatworm’s ability to regenerate.

What’s more, he tried again in other flatworms that can’t normally regenerate whole body parts – just cells, like us. Knocking out that gene made their organs, well, fall apart. That meant that the organs that fell apart would ordinarily have been kept together by regrowing cells, and that the same gene that allows for cell renewal in some flatworms takes care of regrowing whole bodies, Dr Who-style, in others. Phew. A lot of jobs for one gene.

Who knows, maybe Time Lords and humans share that same gene too. They’re like the lucky, regenerating flatworms and we’re the ones who are only just keeping things together. But if it’s any consolation, at least we know that our bodies are constantly working hard to keep us renewed. We still regenerate, just in a slightly less spectacular way.

– the CS4FN team (updated from the archive)

More on …

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

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

QMUL CS4FN EPSRC logos

How did the zebra get its stripes?

Head of a fish with a distinctive stripy, spotty pattern
Image by geraldrose from Pixabay

There are many myths and stories about how different animals gained their distinctive patterns. In 1901, Rudyard Kipling wrote a “Just So Story” about how the leopard got its spots, for example. The myths are older than that though, such as a story told by the San people of Namibia (and others) of how the zebra got its stripes – during a fight with a baboon as a result of staggering through the baboon’s fire. These are just stories. It was a legendary computer scientist and mathematician, who was also interested in biology and chemistry, who worked out the actual way it happens.

Alan Turing is one of the most important figures in Computer Science having made monumental contributions to the subject, including what is now called the Turing Machine (giving a model of what a computer might be before they existed) and the Turing Test (kick-starting the field of Artificial Intelligence). Towards the end of his life, in the 1950s, he also made a major contribution to Biology. He came up with a mechanism that he believed could explain the stripy and spotty patterns of animals. He has largely been proved right. As a result those patterns are now called Turing Patterns. It is now the inspiration for a whole area of mathematical biology.

How animals come to have different patterns has long been a mystery. All sorts of animals from fish to butterflies have them though. How do different zebra cells “know” they ultimately need to develop into either black ones or white ones, in a consistent way so that stripes (not spots or no pattern at all) result, whereas leopard cells “know” they must grow into a creature with spots. They both start from similar groups of uniform cells without stripes or spots. How do some that end up in one place “know” to turn black and others ending up in another place “know” to turn white in such a consistent way?

There must be some physical process going on that makes it happen so that as cells multiply, the right ones grow or release pigments in the right places to give the right pattern for that animal. If there was no such process, animals would either have uniform colours or totally random patterns.

Mathematicians have always been interested in patterns. It is what maths is actually all about. And Alan Turing was a mathematician. However, he was a mathematician interested in computation, and he realised the stripy, spotty problem could be thought of as a computational kind of problem. Now we use computers to simulate all sorts or real phenomena, from the weather to how the universe formed, and in doing so we are thinking in the same kind of way. In doing this, we are turning a real, physical process into a virtual, computational one underpinned by maths. If the simulation gets it right then this gives evidence that our understanding of the process is accurate. This way of thinking has given us a whole new way to do science, as well as of thinking more generally (so a new kind of philosophy) and it starts with Alan Turing.

Back to stripes and spots. Turing realised it might all be explained by Chemistry and the processes that resulted from it. Thinking computationally he saw that you would get different patterns from the way chemicals react as they spread out (diffuse). He then worked out the mathematical equations that described those processes and suggested how computers could be used to explore the ideas.

Diffusion is just a way by which chemicals spread out. Imagine dropping some black ink onto some blotting paper. It starts as a drop in the middle, but gradually the black spreads out in an increasing circle until there is not enough to spread further. The expanding circle stops. Now, suppose that instead of just ink we have a chemical (let’s call it BLACK, after its colour), that as it spreads it also creates more of itself. Now, BLACK will gradually uniformly spread out everywhere. So far, so expected. You would not expect spots or stripes to appear!

Next, however, let’s consider what Turing thought about. What happens if that chemical BLACK produces another chemical WHITE as well as more BLACK? Now, starting with a drop of BLACK, as it spreads out, it creates both more BLACK to spread further, but also WHITE chemicals as well. Gradually they both spread. If the chemicals don’t interact then you would end up with BLACK and WHITE mixed everywhere in a uniform way leading to a uniform greyness. Again no spots or stripes. Having patterns appear still seems to be a mystery.

However, suppose instead that the presence of the WHITE chemical actually stops BLACK creating more of itself in that region. Anywhere WHITE becomes concentrated gets to stays WHITE. If WHITE spreads (ie diffuses) faster than BLACK then it spreads to places first that become WHITE with BLACK suppressed there. However, no new BLACK leads to no more new WHITE to spread further. Where there is already BLACK, however, it continue to create more BLACK leading to areas that become solid BLACK. Over time they spread around and beyond the white areas that stopped spreading and also create new WHITE that again spreads faster. The result is a pattern. What kind of pattern depends on the speed of the chemical reactions and how quickly each chemical diffuses, but where those are the same because it is the same chemicals the same kind of pattern will result: zebras will end up with stripes and leopards with spots.

This is now called a Turing pattern and the process is called a reaction-diffusion system. It gives a way that patterns can emerge from uniformity. It doesn’t just apply to chemicals spreading but to cells multiplying and creating different proteins. Detailed studies have shown it is the mechanism in play in a variety of animals that leads to their patterns. It also, as Alan Turing suggested, provides a basis to explain the way the different shapes of animals develop despite starting from identical cells. This is called morphogenesis. Reaction-diffusion systems have also been suggested as the mechanism behind how other things occur in the natural world, such as how fingerprints develop. Despite being ignored for decades, Turing’s theory now provides a foundation for the idea of mathematical biology. It has spawned a whole new discipline within biology, showing how maths and computation can support our understanding of the natural world. Not something that the writers of all those myths and stories ever managed.

– Paul Curzon, Queen Mary University of London

More on …

Magazines …

Front cover of CS4FN issue 29 - Diversity in Computing

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.

QMUL CS4FN EPSRC logos

Was the first computer a ‘Bombe’?

Image from a set of wartime photos of GC&CS at Bletchley Park, Public domain, via Wikimedia Commons

A group of enthusiasts at Bletchley Park, the top secret wartime codebreaking base, rebuilt a primitive computing device used in the Second World War to help the Allies listen in on U-boat conversations. It was called ‘the Bombe’. Professor Nigel Smart, now at KU Leuven and an expert on cryptography, tells us more.

So What’s all this fuss about building “A Bombe”? What’s a Bombe?

The Bombe didn’t help win the war destructively like its explosive name-sakes but using intelligence. It was designed to find the passwords or ‘keys’ into the secret codes of ‘Enigma’: the famous encryption machine used both by the German army in the field and to communicate to U-Boats in the Atlantic. It effectively allowed the English to listen in to the German’s secret communications.

A Bombe is an electro-mechanical special purpose computing device. ‘Electro-mechanical’ because it works using both mechanics and electricity. It works by passing electricity through a circuit. The precise circuit that is used is modified mechanically on each step of the machine by drums that rotate. It used a set of rotating drums to mirror the way the Enigma machine used a set of discs which rotated when each letter was encrypted. The Bombe is a ‘special purpose’ computing device rather than a ‘general purpose’ computer because it can’t be used to solve any other problem than the one it was designed for.

Why Bombe?

There are many explanations of why it’s called a ‘Bombe’. The most popular is that it is named after an earlier, but unrelated, machine built by the Polish to help break Enigma called the Bomba. The Bomba was also an electro-mechanical machine and was called that because as it ran it made a ticking sound, rather like a clock-based fuse on an exploding bomb.

What problem did it solve?

The Enigma machine used a different main key, or password, every day. It was then altered slightly for each message by a small indicator sent at the beginning of each message. The goal of the codebreakers at Bletchley Park each day was to find the German key for that day. Once this was found it was easy to then decrypt all the day’s messages. The Bombe’s task was to find this day key. It was introduced when the procedures used by the Germans to operate the Enigma changed. This had meant that the existing techniques used by the Allies to break the Enigma codes could no longer be used. They could no longer crack the German codes fast enough by humans alone.

So how did it help?

The basic idea was that many messages sent would consist of some short piece of predictable text such as “The weather today will be….” Then using this guess for the message that was being encrypted the cryptographers would take each encrypted message in turn and decide whether it was likely that it could have been an encryption of the guessed message. The fact that the German army was trained to say and write “Heil Hitler” at any opportunity was a great help too!

The words “Heil, Hitler” help the German’s lose the war

If they found one that was a possible match they would analyze the message in more detail to produce a “menu”. A menu was just what computer scientists today call a ‘graph’. It is a set of nodes and edges, where the nodes are letters of the alphabet and the edges link the letters together a bit like the way a London tube map links stations (the nodes) by tube lines (the edges). If the graph had suitable mathematical properties that they checked for, then the codebreakers knew that the Bombe might be able to find the day key from the graph.

The menu, or graph, was then sent over to one of the Bombe’s. They were operated by a team of women – the World’s first team of computer operators. The operator programmed the Bombe by using wires to connect letters together on the Bombe according to the edges of the menu. The Bombe was then set running. Every so often it would stop and the operator would write down the possible day key which it had just found. Finally another group checked this possible day key to see if the Bombe had produced the correct one. Sometimes it had, sometimes not.

So was the Bombe a computer?

By a computer today we usually mean something which can do many things. The reason the computer is so powerful is that we can purchase one piece of equipment and then use this to run many applications and solve many problems. It would be a big problem if we needed to buy one machine to write letters, one machine to run a spreadsheet, one machine to play “Grand Theft Auto” and one machine to play “Solitaire”. So, in this sense the Bombe was not a computer. It could only solve one problem: cracking the Enigma keys.

Whilst the operator programmed the Bombe using the menu, they were not changing the basic operation of the machine. The programming of the Bombe is more like the data entry we do on modern computers.

Alan Turing who helped design the Bombe along with Gordon Welchman, is often called the father of the computer, but that’s not for his work on the Bombe. It’s for two other reasons. Firstly before the war he had the idea of a theoretical machine which could be programmed to solve any problem, just like our modern computers. Then, after the war he used the experience of working at Bletchley to help build some of the worlds first computers in the UK.

But wasn’t the first computer built at Bletchley?

Yes, Bletchley park did build the first computer as we would call it. This was a machine called Colossus. Colossus was used to break a different German encryption machine called the Lorenz cipher. The Colossus was a true computer as it could be used to not only break the Lorenz cipher, but it could also be used to solve a host of other problems. It also worked using digital data, namely the set of ones and zeros which modern computers now operate on.

– Nigel Smart, KU Leuven

More on …

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

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

QMUL CS4FN EPSRC logos

Alan Turing’s life

by Jonathan Black, Paul Curzon and Peter W. McOwan, Queen Mary University of London

From the archive

Alan Turing Portrait
Image of Alan Turing: Elliott & Fry, Public domain, via Wikimedia Commons

Alan Turing was born in London on 23 June 1912. His parents were both from successful, well-to-do families, which in the early part of the 20th century in England meant that his childhood was pretty stuffy. He didn’t see his parents much, wasn’t encouraged to be creative, and certainly wasn’t encouraged in his interest in science. But even early in his life, science was what he loved to do. He kept up his interest while he was away at boarding school, even though his teachers thought it was beneath well-bred students. When he was 16 he met a boy called Christopher Morcom who was also very interested in science. Christopher became Alan’s best friend, and probably his first big crush. When Christopher died suddenly a couple of years later, Alan partly helped deal with his grief with science, by studying whether the mind was made of matter, and where – if anywhere – the mind went when someone died.

The Turing machine

After he finished school, Alan went to the University of Cambridge to study mathematics, which brought him closer to questions about logic and calculation (and mind). After he graduated he stayed at Cambridge as a fellow, and started working on a problem that had been giving mathematicians headaches: whether it was possible to determine in advance if a particular mathematical proposition was provable. Alan solved it (the answer was no), but it was the way he solved it that helped change the world. He imagined a machine that could move symbols around on a paper tape to calculate answers. It would be like a mind, said Alan, only mechanical. You could give it a set of instructions to follow, the machine would move the symbols around and you would have your answer. This imaginary machine came to be called a Turing machine, and it forms the basis of how modern computers work.

Code-breaking at Bletchley Park

By the time the Second World War came round, Alan was a successful mathematician who’d spent time working with the greatest minds in his field. The British government needed mathematicians to help them crack the German codes so they could read their secret communiqués. Alan had been helping them on and off already, but when war broke out he moved to the British code-breaking headquarters at Bletchley Park to work full-time. Based on work by Polish mathematicians, he helped crack one of the Germans’ most baffling codes, called the Enigma, by designing a machine (based on earlier version by the Poles again!) that could help break Enigma messages as long as you could guess a small bit of the text (see box). With the help of British intelligence that guesswork was possible, so Alan and his team began regularly deciphering messages from ships and U-boats. As the war went on the codes got harder, but Alan and his colleagues at Bletchley designed even more impressive machines. They brought in telephone engineers to help marry Alan’s ideas about logic and statistics with electronic circuitry. That combination was about to produce the modern world.

Building a brain

The problem was that the engineers and code-breakers were still having to make a new machine for every job they wanted it to do. But Alan still had his idea for the Turing machine, which could do any calculation as long as you gave it different instructions. By the end of the war Alan was ready to have a go at building a Turing machine in real life. If it all went to plan, it would be the first modern electronic computer, but Alan thought of it as “building a brain”. Others were interested in building a brain, though, and soon there were teams elsewhere in the UK and the USA in the race too. Eventually a group in Manchester made Alan’s ideas a reality.

Troubled times

Not long after, he went to work at Manchester himself. He started thinking about new and different questions, like whether machines could be intelligent, and how plants and animals get their shape. But before he had much of a chance to explore these interests, Alan was arrested. In the 1950s, gay sex was illegal in the UK, and the police had discovered Alan’s relationship with a man. Alan didn’t hide his sexuality from his friends, and at his trial Alan never denied that he had relationships with men. He simply said that he didn’t see what was wrong with it. He was convicted, and forced to take hormone injections for a year as a form of chemical castration.

Although he had had a very rough period in his life, he kept living as well as possible, becoming closer to his friends, going on holiday and continuing his work in biology and physics. Then, in June 1954, his cleaner found him dead in his bed, with a half-eaten, cyanide-laced apple beside him.

Alan’s suicide was a tragic, unjust end to a life that made so much of the future possible.

More on …

Related Magazines …

cs4fn issue 14 cover

This blog is funded through EPSRC grant EP/W033615/1.

Chocolate Turing Machines (edible computing)

A delicious looking box of chocolates
Image by congerdesign from Pixabay

Could you make the most powerful computer ever created…out of chocolates? It’s actually quite easy. You just have to have enough chocolates (and some lollies). It is one of computer science’s most important achievements.

Imagine you are in a sweet factory. Think big – think Charlie and the Chocolate Factory. A long table stretches off into the distance as far as you can see. On the table is a long line of chocolates. Some are milk chocolate, some dark chocolate. You stand in front of the table looking at the very last chocolate (and drooling). You can eat the chocolates in this factory, but only if you follow the rules of the day. (There are always rules!)

The chocolate eating rules of the day tell you when you can move up and down the table and when you can eat the chocolate in front of you. Whenever you eat a chocolate you have to replace it with another from a bag that is refilled as needed (presumably by Oompa-Loompas).

You also hold a single lolly. Its colour tells you what to do (as dictated by the rules of the day, of course). For example, the rules might say holding an orange one means you move left, whereas a red one means you move right. Sometimes the rules will also tell you to swap the lolly for a new one.

The rules of the day have to have a particular form. They first require you to note what lolly you are holding. You then check the chocolate on the table in front of you, eat it and replace it with a new one. You pick up a lolly of the colour you are told. You finally move left, move right or finish completely. A typical rule might be:

If you hold an orange lolly and a dark chocolate is on the table in front of you, then eat the chocolate and replace it with a milk one. Swap the lolly for a pink one. Finally, move one place to the left.

A shorthand for this might be: if ORANGE, DARK then MILK, PINK, LEFT.

You wouldn’t just have one instruction like this to follow but a whole collection with one for each situation you could possibly be in. With three colours of lollies, for example, there are six possible situations to account for: three for each of the two types of chocolate.

As you follow the rules you gradually change the pattern of chocolates on the table. The trick to making this useful is to make up a code that gives different patterns of chocolates different meanings. For example, a series of five dark chocolates surrounded by milk ones might represent the number 5.

See Chocoholic Subtraction for a set of rules that subtracts numbers for you as a result of shovelling chocolates into your face.

Our chocolate machine is actually a computer as powerful as any that could possibly exist. The only catch is that you must have an infinitely long table!

By powerful we don’t mean fast, but just that it can compute anything that any other computer could. By setting out the table with different patterns at the start, it turns out you can compute anything that it is possible to compute, just by eating chocolates and following the rules. The rules themselves are the machine’s program.

This is one of the most famous results in computer science. We’ve described a chocoholic’s version of what is known as a Turing machine because Alan Turing came up with the idea. The computer is the combination of the table, chocolates and lollies. The rules of the day are its program, the table of chocolates is its memory, and the lollies are what is known as its ‘control state’. When you eat chocolate following the rules, you are executing the program.

Sadly Turing’s version didn’t use chocolates – his genius only went so far! His machine had 1s and 0s on a tape instead of chocolates on a table. He also had symbols instead of lollies. The idea is the same though. The most amazing thing was that Alan Turing worked out that this machine was as powerful as computers could be before any actual computer existed. It was a mathematical thought experiment.

So, next time you are scoffing chocolates at random, remember that you could have been doing some useful computation at the same time as making yourself sick.

– Paul Curzon, Queen Mary University of London

More on …

Related Magazine …

This article was originally published on the CS4FN website and a copy can also be found on page 10-11 of Issue 14 of CS4FN, “Alan Turing – the genius who gave us the future”, which can be downloaded as a PDF, along with all our other free material, here: https://cs4fndownloads.wordpress.com/

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.

QMUL CS4FN EPSRC logos