Last week the Bank of England announced that the new £50 note will have Alan Turing on it. The current note features James Watt and Matthew Bolton, the pioneers of the steam engine. It was determined early that the new note would continue to feature a scientist or engineer. The shortlist was:

Mary Anning, Paul Dirac, Rosalind Franklin, William Herschel and Caroline Herschel, Dorothy Hodgkin, Ada Lovelace and Charles Babbage, Stephen Hawking, James Clerk Maxwell, Srinivasa Ramanujan, Ernest Rutherford, Frederick Sanger, and Alan Turing.

You can Google their names if you are unfamiliar with them. As it happens, I wrote about James Clerk Maxwell yesterday in Virtuoso Meets Maxwell.

That binary on the note? If you turn it into a number you will get 23061912, Turing's date of birth, June 23rd, 1912. Alan Turing was one of the founders of what we now call computer science.

Turing's Life

Turing did a lot in his short life, but the most famous is probably being in charge of breaking the German Naval Code that used Enigma Machines at Bletchley Park during World War II. I have written before about Bletchley Park in my post British Computer Museums and I covered what happened after the war in "Lick" Licklider, Unsung Hero of US Computer Science. The British engineers, such as Turing, at Bletchley Park were even more unsung since, in what I consider an extremely shortsighted decision, the British destroyed all the machines at Bletchley Park and swore everyone to secrecy for 30 years. It set British computer science back by decades. I only discovered my great aunt worked at Bletchley Park after she died. My father says he thought she was just a typist, but with the post-war secrecy, the women were all told to say they were secretaries and typists as a cover story, so who knows? By the end of the war in 1945, 75% of the people at Bletchley Park were women.

I have no idea to what extent this honor is partially because of the appalling way Turing was treated at the end of his life. He was convicted of gross indecency with a man in 1952 since homosexuality was still illegal, put on some sort of emasculation drugs, and died, under murky circumstances but ruled a suicide, in 1954. He was just 41. The Economist says about him that:

[His codebreaking work] won Turing scant recognition though, partly because of the project’s secrecy and partly because he was gay, and homosexual activity was then illegal in Britain.

Actually, being gay had nothing to do with it. He won zero recognition, along with everyone else who worked at Bletchley Park in the war, since the British Government, as I said above, destroyed everything. Many top computer scientists such as Donald Michie at Edinburgh, worked at Bletchley Park and also won less than scant recognition. Even when I was doing the rounds to pick where to do a PhD (this would have been in 1975 and 1976) the story was still secret...I didn't realize I what the people I was talking to had done as young men. It was only when Brian Randall, head of the CS department at Newcastle University, wrote to then-prime-minister Ted Heath in 1972 that even the existence of Bletchley Park was admitted.

Having said all that, the BBC's summary of Turing's life in their piece about the £50 note, leaves out Bletchley Park completely:

Computable Numbers and Turing Machines

That paper in the BBC table actually has a weirder name: On Computable Numbers, with an Application to the Entscheidungsproblem. That last German word means decision problem. This was a proof (actually a second one since Alonzo Church had shown something similar in predicate logic) that some decision problems were undecidable. It was simply impossible to build a machine that could compute the answer. One particular case of this is the "halting problem", that it is impossible to create a program that will always determine whether a second program will halt or get stuck in an infinite loop. In 1931, Kurt Gödel would go on to demonstrate that things are worse than this, that it is possible to make statements in mathematics that are impossible to prove to be true or false, they are unprovable. Axiomatic systems cannot be both complete—you can prove anything that is true—and consistent—nothing is both true and false.

In that paper, Turing came up with a sort of fundamental computing engine known as a Turing Machine. I won't try and explain it. If you are a computer scientist, you probably have a passing knowledge of it, and if not you probably aren't that interested. Turing showed that it was a "universal computer"—it could run any program that any other computer could run (albeit very slowly). Any computer that can emulate a Turing Machine thus has this property, too, and is known as "Turing Complete".

We have a similar property in designing digital electronics. If you can design a two-input NAND-gate (or a NOR-gate for that matter), then you can design any computer and the system is Turing Complete. Of course, there are better ways to build a chip than just using two-input NANDs, just as there are much better computer architectures than a Turing Machine. Some odd things have been proven in this way. For example, in Conway's Game of Life, it is possible to build a NAND-gate and so you can build a universal computer in that world. Or this image is one built in Minecraft (which, since it is Turing Complete, can be used to run...Minecraft).

Bletchley Park

I said above that Turing headed up the project, Hut 8, to decrypt German naval (Kriegsmarine) Enigma messages In fact, the code ended up having to be broken twice since in the middle of the war the Germans added an extra rotor to the machine, which meant that the codebreaking approaches already worked out were not longer effective. Allied shipping losses to U-boats went way up, partially because, ironically, the Germans had broken the code used by the Royal Navy and they were very slow to change it despite Bletchley Park having already told them.

Turing created the initial design of the Bombes electromechanical machines that were used to identify, or at least narrow down, which rotors were being used by the Germans that day (the rotor order changed daily or every two days). Turing did the original design and Gordon Welchman made a major improvement, the diagonal board, that made the Bombe much more efficient.

Subsequently, Bletchley Park created Colossus, by some measures the first programmable electronic computer, using 2400 valves/tubes (and a 5,000-character-per-second paper-tape reader). Turing is sometimes wrongly credited with the design, but it was actually created by Tommy Flowers of the General Post Office (which also ran the phone system, so it's not quite as odd as it sounds). It did, however, incorporate Turing's work on probability in cryptanalysis. Amazingly, this work was kept secret for 70 years. The Applications of Probability to Cryptography written in 1941/2 at Bletchley, was released by GCHQ (the UK equivalent of the NSA, and the successor to Bletchley Park) in 2012 after GCHQ felt that they had "squeezed the juice" out of it. It's barely credible that any work that is 70 years old is still so significant that it was felt necessary to keep it confidential. But that would be continuing the tradition of Britain's secrecy that started with destroying everything at Bletchley after the war.

Turing Test

The Turing Test was proposed by Turing in 1950 in his paper Computing Machinery and Intelligence as a way to define intelligence and answer "can machines think?". To perform the test, you use a keyboard/screen (it was a teletypewriter in 1950) to communicate with an unknown partner. If you couldn't tell if the partner was a computer or a person then the computer was intelligent by definition.

For my take in this area, see my post Can Computers Think? Or Understand Chinese?

This definition immediately rules out things like, say, AlphaGo which can only play Go and not carry on a conversation. In fact, Turing created the first chess program. But this was before computers existed so it was just an algorithm, but it looked two moves ahead. Gary Kasparov played it in 2012, beating it in 16 moves. But he said “I would compare it to an early car—you might laugh at them but it is still an incredible achievement." (As it happens, I wrote about early cars just a couple of weeks ago in The Mercedes Benz Museum and the Invention of the Automobile.)

These days the Turing test is considered a bit limited. If we had a true self-driving car already, that could operate in all conditions (level 5 in the jargon), then for sure it is intelligent in some way, even if it can't carry on a conversation on an arbitrary subject. If you've experienced some London taxi-drivers, that's the last thing you'd want in a car.

Turing Award

The highest award in Computer Science is named after Alan Turing (officially the "ACM A. M. Turing Award") and generally accepted as the closest we have to a Nobel Prize in Computer Science. I wrote about some recent winners at the time:

• Hennessy and Patterson Receive the 2018 Turing Award
• Geoff Hinton, Yann LeCun, and Yoshua Bengio Win 2019 Turing Award

Watch this blog next March to find out who are the 2020 honorees.

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.