Everyone these days has heard of Alan Turing, the father of computer science, the man who cracked the Enigma code and the eponymous “inventor” of both Turing Machines and the Turing Test. Science fiction tends to conflate the two, but they are completely different things, both emanating from that same genius.
The Turing Machine
I don’t work as a computer scientist. I know people who do, but because I have a mortgage to pay I work as a software engineer, even though my discipline is computer science. Computer scientists live in colleges, generally in Cambridge although there may be one or two in Oxford. Back in the 70’s there were even some in the US of A, copying the stuff they learnt from Cambridge (Ok, Kernighan, Ritchie, Thompson et al, this isn’t meant to be serious, please don’t sue me) . They don’t do anything as demeaning as writing software. So what do they do?
How to be a genius: step 1. Think in abstract terms. Einstein worked with thought experiments, like, “if I were sitting on a photon, what would I see if another photon went past me, and at what time would we both think it was time for tea?”. How did Alan Turing imagine computers before they existed? What’s even more astonishing is that Turing worked out the kinds of problems that you could and couldn’t solve with a computational engine before there was any such thing as a computational engine. That is the power of abstraction in the hands of a genius. I’ve only ever met one true genius in my life and his gift was to explain the complex in very simple terms. There are not many people in the world with this gift. Think Feynman, Turing, Einstein…
Can you imagine a machine that can add 3 and 4, without building the actual machine, even before such a machine has been built?
Turing suggested that you imagine a machine which:
a. Takes its input from an infinite tape made up of cells
b. Has a read/write head which can read the cell under the head
c. Has some instructions (a stored program) which tells it what to do depending on what is under the head.
For example, the instruction might say:
Do the following forever:
If there is a non-blank under the head Then
Move the head right to the 2nd blank cell
Write “1”
Move the head left to the 2nd blank cell
Move the head right one space
Erase the cell contents
Otherwise
Stop
These are the instructions to add two numbers together. When the machine stops the answer should be on the tape.
(I can’t do graphics so the following images are from https://vimeo.com/46913004)
If you just follow the instructions (i.e. program) then you will end up with:
It’s worthwhile just working through this example. It has nothing to do with binary notation or real tapes – it doesn’t matter whether each cell on the tape has 0’s, 1’s, apples or bananas in it. The model is purely conceptual.
Not only did Alan Turing come up with this fantastically elegant idea, he also defined the limits of this wonderful abstract machine; not only what could it do, but what couldn’t it do. Adding is fine, so is multiplication, division etc. But one very important question is, “if the input is infinite, is the machine ever guaranteed to reach the ‘Otherwise Stop‘ state?”. In Computer science this is called the Halting Problem. It says a lot that Turing was aware of this even back in 1937. Things have moved on a lot since then but computer science is still the science of the nature of problems that can and can’t be solved by computational engines.
It turns out that there is a whole class of problems that can be solved with Turing machines. If you’re interested you might want want to check out the Game of Life, invented by John Conway, which, while not only being a mathematical model for evolution also turns out to be able to solve any problem solvable by a Turing machine.
The Turing Test
Even back in the 1930’s as a young under-graduate, Turing could see the logical consequences of his assertions about what could and could not be computed with a computational engine. Naturally (if you’re a genius) his thoughts turned to machine intelligence. Imagine that you were having a conversation with another “person” on the other side of a wall. How could you be certain that you were talking with a person rather than a computational engine or robot, of some kind? This is similar to the famous “cogito” problem in philosophy. We all know that external factors can affect our thoughts. Descartes put this in terms of a mischievous imp but we can imagine that things like brain tumours, hallucinogenic drugs etc. can induce visions. The question is, how can we prove that what we see is real? Descartes reduced this to Cogito ergo sum (I think therefore I am). i.e. the fact that I am thinking means that I must exist. Everything else could be down to the mischievous imp. So imagine a conversation through a brick wall. How could you be certain that the entity (mischievous imp or otherwise) on the other side 0f the wall is intelligent? In Turing’s terms “is it possible for machinery to show intelligent behaviour?”.
This is the so-called Turing Test. The basic idea is that if you can’t tell the difference then artificial intelligence has been achieved (this is a massive generalisation! Many computer scientists would disagree with this statement. Fortunately, this is a blog, not a PhD thesis). The really important point is that someone was even thinking these ideas before computers actually existed.
So, this is computer science. Turing Machines and Turing Tests are completely different things. Perhaps you did a physics degree but are working as a clinical scientist, bio-med or EBME engineer. The difference between being a “physicist” and a bio-med is similar to the difference between being a computer scientist and a software engineer. I studied the former, but my mortgage is paid by the latter.
It’s the difference between SQL and relational calculus/algebra (I’m sure there’ll be a post about this soon!).
As a post-script, many years ago when I was at university, like most students I developed a skill for knowing what was likely to be in the exams. Exam questions, by their very nature, have to be answerable in a given time or number of paragraphs. Artificial Intelligence is so mathematically complex that only the most general areas lend themselves to exam questions. Thus, when it came to revision, AI was not top of my list, as the maths was too complex for a 4-hour exam. Imagine my horror when the AI question required a mathematical explanation of the differentiation between circles and tubes in satellite photographs (i.e. rocket launchers versus sewage works). It’s a good job I wasn’t working for JFK in the 60’s as I would have recommended a pre-emptive strike on the Ely sewage works!