Alan Turing 1

Bob: Next up, some bonus information about Alan Turing. Recall we mentioned that Turing was one of the codebreakers who started working part-time for British intelligence before World War II began. We also said that when Dilly Knox returned from the July 1939 meeting with the Poles, he was eager to share what he had learnt with his colleagues—especially with Alan Turing.

Hanne: Yep.

Bob: Well, here's an interesting question: Given what we now know about all the secrecy surrounding the Bletchley Park operations, why was Turing—who was still a new recruit at the time—brought into the loop so early? Many of the other new recruits were only briefed in September of 1939, after the war had begun. Knox could have chosen to share the sensitive Polish breakthroughs only with senior British staff—but why was he so eager to share them with Turing?

Hanne: Hmm… yeah?

Bob: Also, recall that in the early days, Turing worked in a separate room, away from the bustle of the main codebreaking operations. Again, as a newcomer, why was he allowed to do this? Sure, we now know about all his codebreaking achievements, but back then—before any of his breakthroughs—why was he given such freedom? It seems that British intelligence placed a special level of trust in Alan Turing from the very beginning.

Hanne: It does seem so.

Bob: So, to put it simply: Who was Alan Turing before World War II?

Hanne: That is the question.

Bob: Well, even before his Bletchley Park days, Turing already had a reputation as a mathematical genius. In 1936, at just 24 years old, he published a groundbreaking paper titled On Computable Numbers, with an Application to the Entscheidungsproblem. The Entscheidungsproblem—German for "decision problem"—was a major open question in mathematics. It asked whether there was a general, systematic method to determine whether any mathematical statement is true or false.

Hanne: Interesting…

Bob: And Turing was able to prove that the decision problem is unsolvable—that is, no universal algorithm could decide the truth or falsity of every mathematical statement. However, what made his proof especially remarkable was how he did it. Turing first introduced the concept of a "universal machine"—a theoretical device that could read a set of instructions and simulate the behaviour of any other machine. Then, using that concept, he reformulated the decision problem by describing something called the "halting problem". The halting problem asks whether it is possible, on this universal machine, to write a program—say, \(X\)—that takes as input another program—say, \(Y\)—as well as \(Y\)'s input, and determines whether \(Y\) will halt or run forever.

Hanne: Wait… let me just see if I can wrap my head around that.

(Hanne thinks.)

Hanne: Basically, in the halting problem, Turing was asking whether it is possible to write a program, \(X\), that takes two inputs—one being the instructions of a program, and the other its input—and then figure out whether running that program with the input would cause it to eventually halt or if it would run forever.

Bob: Spot on! And Turing proved that the halting problem is unsolvable—and by extension, the broader decision problem is unsolvable too!

Hanne: I see.

Bob: Also, the universal machine that Turing introduced when describing the halting problem is especially noteworthy. His description of this universal machine, today known as a "Turing machine", became one of the first formal models of a general-purpose machine. This was a groundbreaking concept because, until then, machines were typically designed for a specific task. But Turing showed that, in theory, a single machine could be reprogrammed to do anything—as long as it was given the correct instructions. This was essentially the blueprint for modern-day computers, and it's why Alan Turing is widely considered to be "the father of computer science".

Hanne: Oh!

Bob: So, Turing's fame from his 1936 paper likely explains why British intelligence would have recruited him early on and had such high expectations of him. It also explains why Knox was so eager to tell Turing about the Polish Enigma codebreaking machine—because he knew that if the British were to design a machine of their own, Turing would play a key role in that effort.

Hanne: Makes sense.

Alice: Now, as we've mentioned that Turing proved the halting problem is unsolvable, let's also give you a rough outline of how he did it. However, we should warn you… this bit will take some time to understand. In fact, I had to spend an entire afternoon thinking about it while stroking my chinny chin chin before I finally understood it.

Hanne: Wow!

Alice: So, for now, just try to get the general idea behind Turing's proof.

Hanne: Alrighty.

Alice: Basically, Turing began by assuming that a program, \(X\), capable of solving the halting problem exists. We can represent this as:

\[X(Y,I) \rightarrow Halts\ /\ Runs\ Forever\]

Here, \(X\) takes in the instructions of a program, \(Y\), and some input, \(I\), and outputs whether running \(Y\) with input \(I\)—that is, \(Y(I)\)—will eventually halt or run forever.

Hanne: Right.

Alice: Then, under the assumption that \(X\) exists, Turing described another program—let's call it \(Z\). The simple way of thinking about \(Z\) is that it does the opposite of what \(X\) predicts a program would do. However, to be more precise, \(Z\) takes as input the instructions of a program, \(Y\), passes it along to \(X\) as both the program and its input, and then does the opposite of what \(X\) says \(Y\) will do when run with itself as input:

\[Z(Y) \rightarrow opposite\ of\ X(Y,Y)\]

Admittedly, this is a bit difficult to grasp, but we can break it down into four steps:

1. \(Z\) takes as input the instructions of a program \(Y\).
2. \(Z\) makes a copy of \(Y\).
3. \(Z\) passes these two copies of \(Y\) as input into \(X\). This asks: If the instructions of \(Y\) were given as input into \(Y\) itself—\(Y(Y)\)—would \(Y\) halt or run forever? And yes, giving a program itself as input is something that can be done.
4. \(Z\) then does the opposite of whatever \(X\) says \(Y\) will do when given itself as input. So, if \(X\) says \(Y\) will halt, \(Z\) runs forever; and if \(X\) says \(Y\) will run forever, \(Z\) halts.

Hanne: Fair enough.

Alice: Now here's the mind-boggling bit—if your mind isn't quite boggled yet. Turing considered what would happen when \(Z\) was given itself as input:

\[Z(Z) \rightarrow opposite\ of\ X(Z,Z)\]

Again, you'll need to spend some time thinking about what exactly this means, but what you would find is that it results in a contradiction. \(Z\) does the opposite of what \(X\) says the input to \(Z\) will do when run with itself as input. But in this case, \(Z\) is the input to \(Z\)! This means that if \(X\) says \(Z\) runs forever, then \(Z\) halts, and if \(X\) says \(Z\) halts, then \(Z\) runs forever. In other words, \(X\) will never be able to correctly predict what \(Z(Z)\) will do.

Bob: Right. And we can even see it in the expression for \(Z(Z)\):

\[Z(Z) \rightarrow opposite\ of\ X(Z,Z)\]

This is the same as:

\[Z(Z) \rightarrow opposite\ of\ X\left( Z(Z) \right)\]

And since \(X\) simply says what \(Z(Z)\) will do, this is effectively saying:

\[Z(Z) \rightarrow opposite\ of\ Z(Z)\]

This is a logical fallacy! Hot can't be cold; left can't be right; and \(Z(Z)\) can't be the same as its opposite. In mathematics, this is called a contradiction, and when one appears in a proof, it means that the original assumption was wrong. In this case, the assumption was that a program \(X\) capable of solving the halting problem exists. But since this led to a contradiction, it means that no such program can exist—and therefore, the halting problem is unsolvable. That was the essence of Turing's proof.

Hanne: Well, that was… something. I think I will also need to spend an afternoon thinking about it while stroking my chinny chin chin before I can wrap my head around it.

Alice: Yes, Hanne. Do not underestimate the power of the chinny chin chin—there is great wisdom in it.

Hanne: Understood.

Bob: And to say a bit about the significance of all this, there are problems that computers cannot solve today—at least not quickly enough—but they might be able to solve in the future as technology advances. With that in mind, it might seem reasonable to think that as computers continue to get more powerful, they will eventually be able to solve all problems.

Hanne: Right.

Bob: However, what Turing showed with the halting problem is that there are problems computers will never be able to solve—no matter how fast or powerful they become! For instance, consider the case of designing a program to analyse any piece of software and determine whether it contains security vulnerabilities or malicious code. It turns out that if it were possible to design such a program, then it would also be possible to solve the halting problem. But since the halting problem is unsolvable, then coming up with a systematic security-checking program is also impossible.

Hanne: Oh!

Bob: Of course, it's worth noting that we can still carry out many useful security checks on software applications. However, the key point here is that it is impossible to develop a rigorous, foolproof program that can detect all possible vulnerabilities or malicious code in every piece of software. This is the lasting significance of Turing's proof—it established logical limits to what computers can achieve. And he did this all the way back in 1936, before the field of computing had even begun!

Hanne: That's incredible! It makes sense why his paper was such a big deal.

Bob: Indeed. So, we encourage you to explore the many great resources online to learn more about Turing's 1936 paper. As a starting point, we recommend the YouTube channel Up and Atom, run by the Australian content creator Jade Tan-Holmes. She covers complex topics in math, physics, and computer science in a clear, engaging, and entertaining way. You can check out these videos on her channel:

• The Halting Problem — An Impossible Problem to Solve
• Turing Machines — How Computer Science Was Created By Accident
• The Impossible Problem NO ONE Can Solve (The Halting Problem)

Hanne: Okay, will do.

Bob: Awesome.

Alice: So, that was a bit on some of Turing's pre-war work. The next area worth touching on is what he was up to after the war. After World War II, Turing began working on building his universal machine. In fact, there were two major computing projects in Britain after the war. One was based in London, where Turing was involved, and another was based in Manchester, led by Max Newman. Both Turing and Newman had seen the engineering potential demonstrated by Colossus at Bletchley Park and were inspired to bring Turing's 1936 concept of a universal machine to life.

Bob: Right. And as an interesting aside, Turing had first learnt about the Entscheidungsproblem from a series of lectures by Max Newman—which then led to him writing his groundbreaking 1936 paper, On Computable Numbers, with an Application to the Entscheidungsproblem. Furthermore, when Turing finished the paper, it was Newman who helped him get it published. These two maintained a strong professional relationship throughout their careers.

(Hanne thinks.)

Hanne: Okay. But then… why didn't Newman and Turing collaborate after the war on building the universal machine?

Bob: Ah, fair question. This was likely due to their different institutional affiliations at the time.

Hanne: Oh.

Alice: And to cut a long story short, the London project that Turing was involved in moved at a painstakingly slow pace. This was due to poor communication, bureaucratic issues, and a lack of available engineers, many of whom had been reassigned to post-war reconstruction projects in Britain. It also didn't help that Turing's design aimed to build a large, powerful machine, while Newman's team in Manchester focused on building something smaller and simpler to explore the machine's potential as quickly as possible.

Hanne: The constant battle of perfection versus progress.

Alice: Yes. As a result, Newman's team advanced more quickly, and in 1948, they got a working machine. It became known as the "Manchester Baby", and it was the world's first stored-program electronic computer! Turing was invited to see it and use it, and he eventually joined Newman's team in Manchester after becoming frustrated by the slow progress in London.

Hanne: I see.

Alice: You'll hear the Manchester Baby again when we get to the section with Tommy Flowers, where we'll say a few words about the early history of computing. For now, the key takeaway is that immediately after World War II, Turing was involved in projects aimed at turning his universal machine into a reality.

Hanne: Got it.

Bob: Moving on with some more of Turing's post-World War II work, in 1950, he published another influential paper titled Computing Machinery and Intelligence. In our view, this is one of the most visionary papers ever written.

Hanne: Oh!

Bob: In it, Turing considered the question, "Can machines think?" However, he noted that the terms "machine" and "think" can be a bit ambiguous, as it is difficult to get a widely accepted definition that covers all the nuances of each term. So instead, Turing proposed a game—the "Imitation Game"—as an alternative to tackling the question directly. He argued that if a machine could succeed in the Imitation Game, then that would be sufficient to consider it to be thinking.

Hanne: Okay…

Bob: Here's how the game works. A human interrogator communicates—via written messages—with two entities that are behind closed doors. One entity is a human, and the other is a machine. However, the interrogator does not know which is which.

• The interrogator's objective is to correctly identify which entity is the human.
• The machine's objective is to fool the interrogator into making the wrong choice.

In other words, the machine has to imitate a human in order to deceive the interrogator—hence the name "Imitation Game".

Hanne: Okay. Seems pretty straightforward.

Bob: Yes. That's really all there is to it. We encourage you, however, to imagine yourself as the interrogator and think about what questions you would ask to differentiate the machine from the human. Keep in mind that the machine is trying to imitate a human, so if you ask about its hair length, eye colour, or emotional state, you will get a response. If you ask it a complex mathematical question, it might delay its response or even give you an incorrect answer, making a common arithmetic mistake in its calculations.

Hanne: Hmm… yeah. I'll need to spend some time thinking about what questions I would ask if I were the interrogator.

Bob: Fair enough.

Alice: Now, Turing predicted that in about 50 years, it would be possible to build a machine that could

… play the imitation game so well that an average interrogator will not have more than 70 per cent chance of making the right identification after five minutes of questioning.

In other words, a machine that can win the Imitation Game at least 30% of the time after five minutes of questioning.

Hanne: Right.

Alice: However, this was simply Turing's prediction in 1950 of what would be possible in 50 years. He did not say that these were the strict set of conditions that the Imitation Game had to be performed under. Yet, over time, this prediction became treated as a benchmark, and today, these are the conditions a machine must meet for it to be considered successful in the Imitation Game—win at least 30% of the time after five minutes of questioning from an average interrogator.

Hanne: I see.

Alice: And there are those who take issue with this. Some say that a 30% win rate for the machine is too low, others that five minutes of questioning is too short, and some that expert interrogators should be used instead of average interrogators. After all, an interrogator who first learns about the Imitation Game a few minutes before questioning the two entities would naturally ask less challenging questions than someone who knew about the Imitation Game for a while and had the opportunity to come up with more challenging questions.

Hanne: Right. I'd definitely need a bit of time to come up with some good questions myself.

Alice: Exactly—and you're a remarkably intelligent little one. Imagine what it would be like for everyone else.

Hanne: Oh… oh no.

Alice: But despite these criticisms, winning the Imitation Game with a 30% win rate after five minutes of questioning remains one of the most famous measures for answering the question, "Can machines think?" And many new systems are still formally and informally put to the test. Though, it's worth noting that today, the Imitation Game is more commonly referred to as the "Turing Test". So, rather than talking about "winning the Imitation Game", we talk about "passing the Turing Test".

Hanne: Understood.

Alice: Excellent. So, we highly recommend that you read Turing's Computing Machinery and Intelligence paper in full, as it is very insightful and is actually pretty easy to read for an academic paper. However, if you're just interested in some of the key ideas, you can check out the YouTube video titled "The original 'Turing Test' paper is unbelievably visionary" on the YouTube channel Tibees. This channel is run by Toby Hendy, a New Zealand YouTuber who makes fun and insightful videos on physics, math, and astronomy.

Hanne: Okay. I'll check it out.

(Hanne thinks.)

Hanne: So, has any machine ever been able to pass the Turing Test?

Alice: Ooooh. Well, the short answer is yes. But Turing's 1950 prediction that it would be possible in about 50 years was a bit off. Rather, it took about 75 years.

Hanne: Oh!

Alice: However, for the long answer, we'll need to give you some insight into the evolution of chatbots and the field of artificial intelligence. Basically, chatbots are programs designed to engage in human-like conversation, and these are what had to be developed to pass the Turing Test. Chatbots, however, form part of the broader field of artificial intelligence—commonly shortened to "AI"—which involves creating systems capable of performing tasks that typically require human intelligence. These include things like learning, reasoning, problem-solving, decision-making and so on. AI is a broad field, and chatbots are just one part of it, but in many cases, you'll find the terms "chatbot" and "AI" being used interchangeably.

Hanne: Okay.

Alice: So, let's take a bit of a detour and give you some insight into the evolution of chatbots and the field of artificial intelligence, and then we'll get back to Alan Turing.

Hanne: Ah… this was the bonus bonus topic. Let's go!