Last one out of the Kinjaverse, turn out the lights.
Last one out of the Kinjaverse, turn out the lights.

Nerding out on the Comp Sci in The Imitation Game

I had been avoiding The Imitation Game 'cause I was way afraid of the way it'd portray Turing's work. Instead, it incorporated more bits and pieces of computer science than I thought it would, and did it all surprisingly well. So, I'd like to share with you some of the fundamentals of Computer Science that are sprinkled throughout the movie.


I need to steal the movie's explanation of cryptography, 'cause that mechanical process of machine does one way scrambling of message based on settings? That's more or less what modern cryptographic software is doing, just using math to figure out the settings. Those settings are called the cipher (or cryptographic key), and are just a set of rules for how to scramble the text. If you'd like to learn more, I highly suggest checking out the NSA's CryptoKid page.



Illustration for article titled Nerding out on the Comp Sci in The Imitation Game

In the movie, Christopher (Turing's machine for breaking the code, and in reality called a Bombe) takes forever and a day to find the correct settings, but he goes much much faster once they learn about a daily 6:00AM weather report that always contains the words " Heil Hitler". Because they know this appears encrypted every day, the machine can effectively instantly tell whether it's encrypting or decrypting correctly based on just this string of words. And so, the logic goes that because it can tell very quickly if it's wrong, it can be more efficiently be programmed to only search for the settings to decrypt these words (because the settings are the same for all words) and quickly cut off searches down blind allies, hence the speed up.

So this whole thing about quick verification equaling quick solution? That's the heart of this open problem in computer science called P versus NP. The p stands for polynomial and the NP stands for nondeterministic polynomial (thanks Daniel), and what they're talking about is how long it takes (in steps, memory, or time) to solve a problem. The going theory is that because it takes a short (polynomial) amount of time to check that the right answer is right, the problem should also be solvable in that amount of time. This theory is still unproven.


Edited to add: And, as a couple of commentators pointed out, pretty much the entire computer science community thinks that the theory is false and P=/=NP.


Turing Test

The Turing Test is a real thing, that works more or less as described. The goal is to program a piece of software (often called a bot) such that a person talking to it can't tell if it's a person or bot doing the speaking. If you've ever talked to a chat bot (or much of modern customer support), you're talking to the descendants of the Turing test.


Turing Machine


A Turing machine is a machine with a single read/write head that's fed an infinitely long blank tape cut up into cells. It can do very few things with this tape, one cell at a time:

  1. read a 0, 1, or blank from it
  2. write a 0, 1, or blank to it
  3. move the tape left or right
  4. make decisions 1-3 based on it's last action (1-3)

And that's basically it, but through a whole lot of math and logic and the like, Turing proved that if (and only if) problem can be solved computationally(correction: as commentator denziloe pointed out) wrote out this formal definition of how to solve a problem computationally and how if that's possible, it can be solved on this machine. The flip side of this is that if a machine can do what a Turing machine can do, it can compute anything that can possibly be computed.


My favorite extension of the theory is called Turing Completeness, which says that if a programming language can simulate a Turing Machine (and most of 'em can by design), then it can compute anything. This means that almost any language can theoretically be used to program most anything, and the real difference in programming languages is just how effective they are in solving a specific class of problems.

Share This Story

Get our newsletter