Breaking the Enigma: Alan Turing and the Turing Machine

Breaking the Enigma!

Alan Turing Aged 16
Passport photo of Alan Turing at age 16 (Source: Wikimedia)

Very rarely do you find individuals that change the course of history purely through sheer brilliance. But, when you do find such individuals it is imperative to celebrate them. These individuals tend to produce magnificence through brilliance so effortlessly and with such fluency that it is hard not to remain awestruck. Alan Turing was one such individual. Alan Turing is the man who formulated many of the theoretical concepts that have enabled modern computation. He is widely regarded as the father of computer science, and, rightfully so.

About Alan Turing

Alan Turing was an English mathematician and cryptanalyst whose work in breaking the Enigma code and work in the development of computer science gained him a lot of recognition. He is also credited as being the father of Artificial Intelligence, which, is an exciting and promising field. He studied at King’s College, Cambridge and was widely considered to possess brilliance that was far beyond his age.

Turing Machine

Turing machine is a hypothetical simplistic machine that was created by Alan Turing as a solution to the decision problem. The simplicity of the Turing machine made it a phenomenon. The field of computer science was still in its initial stages and was a burgeoning field and the role of the Turing machine in its growth cannot be overstated. The contribution of the Turing machine was immense in the development and acceptance of computer science.
A Turing machine consists of an infinitely long memory tape that contains input characters or symbols. Upon reading a character on the memory tape, the state of the machine could change. There were operations such as read, write or modify that could be carried out on the tape. There also existed a set of rules that defined what would happen for a particular state and input symbol. These rules specified the effect of the character read from the tape on the current state. Each memory tape had a head. The head was responsible for carrying out either the operation of read, or, that of write. This head could also be moved either to the left or to the right.
This seems simple, right? This is where the beauty of the system lies. Without being overly complicated, the Turing machine had the potential of solving any problem. Alan Turing stated that this machine could solve any computational problem, given enough time and memory. This simplistic machine could solve everything!

An Enigma decryption machine called a “bombe.” This machine, made by National Cash Register of Dayton, Ohio, eliminated all possible encryptions from intercepted messages until it arrived at the correct solution. (U.S. Air Force photo)

Therefore, the Turing machine provided the basis for computational studies. In terms of solving computational problems, there is no computer more powerful than the Turing machine. Any computer that is considered to be as powerful as the Turing machine is considered to be Turing complete. Every modern computing system is considered to be Turing complete.
To answer the decision problem, Turing proposed a puzzle that is renowned as the halting problem. This problem aims to figure out whether there exists an algorithm that can determine if the machine will keep running, or, halt, given the input tape and description of the Turing machine.
This halting problem can be used to determine whether computer programs would halt or continue perpetually. Alan Turing was successful in proving that the halting problem was in fact unsolvable. Consider a Turing machine that takes the description of a program and certain inputs for its memory tape. Also, consider the output for this machine to be either Yes if the program halts or No if the program fails to cease. Now consider another Turing machine that is built on top of this machine. Now, if the output of the first Turing machine is Yes, which means that the program halts, then, we make the second machine run in an infinite loop. If the output of the first Turing machine is No, which means the program does not halt, then, we make the second machine output No and halt.
If you have followed carefully, you will notice that the second Turing machine does the exact opposite of the first one. Consider the combination of these machines as a single unified machine. Let’s call this machine, Alan. Now if we pass the description of the unified machine, Alan, as input to the same machine, Alan, then we are asking the system to evaluate itself. If the first Turing machine in Alan outputs Yes, the second machine goes into an infinite loop and it does not halt. If the first machine outputs No, the second machine halts.
So, the first machine cannot determine the solution to this problem. It results in a paradox. Since Turing proved that all computational problems can be solved on the Turing machine, the fact that this problem cannot be solved on it means that the problem does not have a solution. He, therefore, proved through contradiction that the halting problem is not solvable. By showing that the halting problem was not solvable, he proved that the decision problem had no solutions.
You may ask, what is the decision problem? Decision problem was put forth by David Hilbert. The problem asks for an algorithm that takes a sentence of first-order logic as input and produces either a Yes or a No according to whether the statement is universally valid or not.
Alonzo Church also proved that the decision problem had no solutions through his lambda calculus. This led to the formation of the Church-Turing thesis, which, says that lambda calculus and Turing machines are capable enough to solve all computational problems that have solutions.

Breaking the Enigma

Turing played a pivotal part in the Second World War in deciphering German codes that were created through the Enigma machine. This machine scrambled any text and transmitted the scrambled text. This scrambling was carried out by the Germans to ensure that nobody intercepts and understands their messages. The scrambling was not random, it was determined by the rotors of the Enigma machine, which meant that it could be descrambled on another Enigma machine. Thus, the Germans would transmit messages encrypted by one Enigma machine and receive messages decrypted by the receiving Enigma machine. The challenge for Turing was to crack the Enigma and understand the rotor configurations.
Alan Turing came up with the Bombe, which, was an enhancement of the Polish code breaking system that aimed to crack Enigma codes. Bombe predicted rotor settings of the Enigma machine more effectively than any other system. The Germans would periodically update the Enigma machine and add rotors to ensure that codes were not being encrypted by anyone else. Turing and his colleagues worked tirelessly to break this code and were appreciated for potentially reducing the duration of the war by several years.

Turing Test

Perhaps, the most promising contribution of Alan Turing was his contribution to Artificial Intelligence. Turing hypothesized that a computer can achieve intelligence equivalent to that of a human being, or at least, intelligence that is indistinguishable from human intelligence if it could successfully lead a human being to believe that the machine was human. The Turing test is renowned for being the basis for classifying machine as either intelligent or not intelligent.
The Turing test involves a human evaluator who is responsible for determining which of the two entities he is talking to is actually human. The evaluator is allowed to ask a series of questions to carry out this classification. These questions are asked to both the human being and the machine. If the human evaluator fails to determine which one is human, and which one is a machine, based on the responses, then, the machine is said to have successfully fooled the evaluator and is deemed to be intelligent.

Controversy regarding Alan Turing

Sadly, the greatness of this brilliant individual was marred with controversy. Alan Turing was homosexual in a time when homosexuality in the United Kingdom was illegal. When he was convicted of these charges, he was given the option of either imprisonment or chemical castration. He chose chemical castration so that he could continue his academic work. As a result, he spent much of his post-war life unable to conform to the changes that resulted in him due to chemical castration. He, unfortunately, took his own life at a very young age of 41.

Artificial Intelligence

The gift of Artificial Intelligence was provided to us by Alan Turing. Artificial Intelligence has shown immense potential and could soon be incorporated into everyday systems. Although one could say that Artificial Intelligence is still only a burgeoning field, the accomplishments of Artificial Intelligence are already so significant that it would be foolish to not consider it to be a powerful aspect of society in the not so distant future.
The genius, Alan Turing once said, “We can only see a short distance ahead, but we can see plenty there that needs to be done”. Alan Turing had tremendous dedication towards his work. He was even willing to undergo chemical castration to be able to continue with his academic work. That was the dedication that the man possessed.
There probably are not enough adjectives to describe the brilliance that Alan Turing possessed. Then again, it probably would be an injustice to the great man to express appreciation towards his intelligence through mere words. The potential the man possessed could not be, nay, should not be described through mere words constrained by the vocabulary. It is tragic how his story unfolded, but, his contributions to the field of computer science and artificial intelligence will forever live on. He was truly a rare gem.


Please enter your comment!
Please enter your name here