Alan Turing would celebrate his 100th birthday on this very day if he hadn't swallowed some cyanide when he was 41.As Google's Doodle reminds us today,
Because he may be considered the forefather of computer science, it's kind of incredible to realize how fast the progress in computer science and computer industry has been in the recent 100 years. Given the current state of medicine, the forefather of these fields could easily be with us today.
He's not but that's just due to an unlucky accident.
And we must appreciate that the first 24 years of this century of computer science were passive: only when Turing was 24, in 1936, he described his a-machine (automatic machine) or Turing machine, as we call it today. This machine was important as a "proof of concept" to show that deterministic gadgets based on a rather simple philosophy were capable of doing pretty much all mechanical tasks that humans can do with the information and numbers.
Today, we understand this principle rather well and real-world computers have lots of internal structure not described by the Turing machine design. However, the Turing machine is still being used as a mathematical model of a device that can do everything that men (and women) can do with the information – and everything that equivalent computers can do.
What is a Turing machine?
It has an infinite tape with infinitely many squares. Each of them contains a symbol from a finite set that can be rewritten. One symbol/square in this infinite memory is just being read by the "head". This symbol is \(a\). However, you can't live with the tape only. You also need some "processor", right?
A Turing machine has a processor that can be reduced to a finite memory, the state register whose immediate state is denoted \(q\), and... What about the part that actually calculates? This whole part is represented by a table and nothing else. That's enough. The table says\[
q(t)a(t) \mapsto q(t+1)a(t+1)d(t+1).
\] Depending on the variable data, namely the state \(q\) of the state register and the character \(a\) that the "head" is just reading, the table determines what the new state of \(q,a\) should be – those things are being rewritten in the state register as well as on the tape – and for these values of \(q,a\), the table also says whether the head should stay at the same place, i.e. \(d=0\), or move by one square to the right or to the left, \(d=\pm 1\). That's it. That's everything you need. That was Turing's representation of the Al Gore Rhythm that he was able to invent years before Al Gore, the inventor of the Internet and the savior of the world, was even born.
Well, for finite projects, you don't really need the infinite tape, either. A finite tape would be enough and its memory could be incorporated in the state register, your humble correspondent would simplify the Turing machine. ;-) But with this simplification, the machine would be really dull: everything it could do would be written in the table. The separation of the memory to the tape and the state register in the Turing machine conveys the fact that a computer is supposed to process a huge amount of data with instructions, codes, and processors that are much more limited.
What your CPU or GPU is doing is just one gigantic table. Of course, it is a table with many patterns that contains addition and multiplication tables and many other more complicated tables as its subtables. These tables aren't being remembered in a gigantic amount of memory. Instead, they're being calculated. New computers are calculating – and doing many complicated things with graphics as well – by a synchronized dance of many transistors. Modern computers have many layers of memory (and cache) that interpolate between the tape and the state register, too. But in principle, a large enough table would be enough. It wouldn't be equally practical but it would be mathematically equivalent.
If you haven't heard about the cyanide story, I must tell you. In 1952, he was arrested and accused of a sexual contact with another gay – the same kind of a "crime" that has previously haunted Oscar Wilde as well and that would instantly promote you to the chair of an Ivy League university president nowadays. He was fired and had to undergo an estrogen therapy. Because of the latter, the thin marathon runner got fat and acquired breasts. He was disgusted by these new organs so in 1954, he got inspired by his favorite fairy-tale hero, Ms Snow White. In particular, he took "an especially keen pleasure in the scene where the Wicked Queen immerses her apple in the poisonous brew". He did the very same thing. Just like in the 1937 Snow White movie, he died – but something else was born at the same moment. Of course, I am talking about the logo of Apple:
Now, you just add a few more details by John von Neumann, Bill Gates, Steve Jobs, and a few others – apologies if I have forgotten about your name but the state register of this particular blog entry was limited and I didn't want to write it on the tape – and lots of straightforward work and you get to the current state of the computer science and computer industry. ;-)
Happy birthday and rest in peace, Alan Turing.