The Turing Machine

Thursday marked the would be 99th birthday of one of the most important (and possible under-appreciated) mathematician and computer scientist of the modern era. To mark this occasion, I thought an article on his still very relevant living legacy would be rather appropriate.

We all know Alan Turing from his pivotal role at Bletchley Park and his contributions to cryptanalysis during the second world war and in particular, his role in cracking the enigma code. However, he was also a main player in birth of computer science of which some concepts are still very relevant today. The “Turing Machine” is one of them. It is a theoretical thought experiment described by Alan Turing in 1932 and to this day helps computer scientist understand the limits of mechanical computation.

It’s basic idea is to determine if a task is computable, i.e. if it is possible to specify a sequence of instructions (known as an algorithm) which, when carried out, will result in the completion of the task. The concept makes it unnecessary to know how the machine carries out these instructions. As we are purely interested in the limitations of what can be computed, it is only required that the instructions can be uniquely defined and the assumption that the theoretical machine can be carry out these instructions.

There are many different definitions of this theoretical machine, however in simple terms, the Turing Machine is a state machine and that the instructions consist of conditions under which the machine will transition between one state and another. The consideration must then be made that this machine must be able to transition between states and hence carry out the instructions in order to determine if a particular task is computable.

As in most definitions available in the literature, the Turing Machine has a tape which is infinitely long and split into cells each containing a single symbol. It contains a read-write head which is capable of reading the current cell and modifying it if necessary. The action of the machine is then determined completely by the current state of the machine, the symbol in the cell currently being scanned by the head and a table of transition rules, which serve as the “program” for the machine.

The transition rules follow the general form “if the machine is in a current state and the cell being scanned contains a particular symbol then move into the next state by taking a particular action” i.e. by writing a new symbol on the cell, moving to next cell etc.

If a particular task whose computability is to be tested can be defined by a particular states and a unique clearly defined table of transition rules, then the task is computable. This however, does not mean that there exists a machine which can actually perform the task. For example, the Turing Machine’s tape is assumed to be infinitely long. This is analogous to a computer’s memory. There is of course, a limit to how much memory a computer can use. Similarly, in practical terms, it is arguable that a task can be termed “computable” if it requires an infinite amount of time.

In the real world, this is a very simple model for for a modern computer. It shows the importance of logic which is the fundamental requirement of all modern computing techniques. It has given birth to many areas of computer science ensuring that the legacy of Alan Turing continues to live on. Next year will be his 100th birthday. Let’s hope it’s marked properly.

“RSA Encryption” by Emilio Pierro

“Emilio Pierro, originally from Bedforshire, England, graduated from the University of Birmingham with a Masters in Mathematical Sciences. In his spare time, Emilio enjoys music, photography, drawing, languages and travel. He was also kind enough to contribute this article on RSA encryption. Hope you enjoy it, thanks Emilio!” If you’d like tto contribute an article, feel free to contact me on twitter @GaryBroughton15 or supermassivescience@live.co.uk. Gary

RSA Encryption – by Emilio Pierro

How secure is the information we send over the internet? Over a public wifi connection one can intercept the communications of another with very little effort indeed, so how can we be sure that the information we send, emails, pictures, bank details, are secure?

E-commerce has changed the way we shop and live at both the consumer end, and at the enterprise end. In a few years companies such as Amazon and eBay have gone from conception to becoming huge players in the global business market. Their modus operandi and therefore their success is built purely on the ability to send and receive sensitive information, such as bank details, securely over the world wide web. But how secure is your information? In this article we aim to show you exactly how secure.

To send information over the web securely, we need a method of encryption that is both efficient and secure. Broadly speaking there are two methods of cryptosystem –

1) Symmetric, or secret-key cryptosystems where the same “key” is used to encode and decode messages.

2) Asymmetric, or public-key cryptosystem where each user has a private key to decode messages, but a single public key used to encode messages.

Each methods has its pros and cons… the main disadvantage of the secret-key method is that we need a secure way of distributing our key in the first place. The public-key method gets around this via the fact that our messages cannot be decoded with just the public-key, an eavesdropper would need the key we keep private as well in order to decode the message.

So where does Prime Number Theory, the least accessible branch of the least accessible science fit into all of this? Think of this… take two prime numbers and multiply them together, say 17 and 19. That’s 323 if you were born after the invention of the calculator. Pretty easy stuff, right? How long did it take you to work that out? A minute or two, at most, doing the calculation longhand? A few seconds on a calculator? Well, now try it in the opposite direction. Suppose I give you 323 and ask you to find the unique prime factors (and you hadn’t read the preceding bit of this paragraph). Worked it out yet? Give yourself as long as it takes.

We use numbers that are the product of two unique prime numbers because this makes the factors as rare as possible. As you can see, even with a very small example, this takes a while. Until somebody can devise an efficient way of breaking numbers down to their prime factors (which several thousand years of trying has yet to produce) the only real way to try and crack this problem is a brute force method, i.e. Divide by 1 and check if we get an integer, divide by 2 and check if we get an integer, divide by 3…, and you get the idea. But how long will this take?

The numbers which are used in the implementation of RSA crytography are at least 128-bits in length, i.e.  128 characters of 0s and 1s. How many of these are there? Since there are two choices for each of the 128 characters, there are 2^128 possible words. This is greater than 3.4 * 10^38. This is a big number. To put it into perspective, it would take 10 billion computer, testing 10 billion numbers every second approximately 100 billion years to test every single number, making the search its prime factors practically impossible to calculate.

This shows that prime numbers provide the perfect candidate for for our public and private key system. So how does the RSA algorithm work?

RSA is based on an area of mathematics called modular arithmetic where we work “modulo” a whole number. An example in everyday life would be telling the time where we work “modulo 12”. This means we see “13 o’clock” as 1pm. What we are actually doing is seeing two numbers, here 1 and 13, as the same if the difference between them is a multiple of the number we are working modulo. In this case, the difference between 1 and 13 is 12, and since we’re working modulo 12 we see these numbers as the same. Similarly, we see “24 ‘o’clock” as “0 ‘o’clock” as the difference between them is a multiple of 12.

One way to visualise what is happening in RSA is by imagining that our messages have a clock attached to them and can only be read when the clock reads a specific time. When somebody sends us a message they use our public key to move the clock forward in time by a given amount. Then when we receive the message we use our secret key to push the clock the remaining amount of time forward to the time which the message can be read. So if someone were to intercept our message they would just see a clock with a specific time on it and without the private key to push the clock forward to the agreed time, the message cannot be unlocked.

To delve into the mathematics a little, RSA uses something called Euler’s Theorem which says if we work modulo a number, n, we can take a number, x, and raise it to the power of some number, y, (whose factors are related to the prime factors of n) to get x back again. Then one of the factors becomes part of our secret key and the other becomes part of our public key.

Rest assured though, that the security of RSA relies not on being able to comprehend the mathematics behind it. I believe that with enough time and willpower anyone could understand it. The security lies in the very non-obvious task of trying to break a number into its prime factors. Which is good, because the security of much of our sensitive online communication is based on this. In fact whenever you see the padlock icon on your web browser, the chances are that the security of your connection is relying on RSA. In fact, just scanning a few of my most-visited sites: Gmail, Facebook (over https), Twitter (over https) and Amazon, all three of these have their digital certificates encrypted by RSA. Something I wasn’t even aware of myself!