Turing Machines: An Ugly Model of Computation

This post is a basic introduction into what Turing Machines are and clarifying a misconception about what they might be. This post is in preparation for the post on Lambda Calculus, so that it can be better understood and appreciated. Note: most (if not all) posts (including this one) are intended for non-mathematicians, so there may be some informal terminology or slight simplifications to make it more readable, but without sacrificing intellectual integrity.

Clearing up a Misconception

First of all, I have not seen the film “Imitation Game”, but I believe that it may have either provided false information, or mislead people to believe something false. A Turing Machine is NOT a device built to crack the Enigma machine (speaking of which, why does no one ever mention the Lorenz Cipher?). A Turing Machine is NOT a real physical device of any kind; it is a purely hypothetical device, devised originally solely as a thought experiment type of thing (completely and utterly unrelated to his work in cryptanalysis – which in my opinion is the only noteworthy work he did, but more on that later).

So, what IS a Turing Machine?

Note: the following may not make complete sense at first, but below is an example, which should help the whole thing make sense, if it didn’t already.

A Turing Machine is an abstract device which has a few parts or components:

  • A “Tape”, a strip divided into a squares (called “cells”), stretching on forever.
  • A “Head”, which moves along the “Tape”.

Each cell of the tape is either empty, or it has exactly one “symbol” on it (belonging to a finite pre-defined set of symbols). The “head” also has any one of a finite number of “internal states” (also belonging to a finite pre-defined set). The “head” is always over a single cell of the tape, and it can read the symbol in that cell. The combination of the symbol it reads and the “internal state” it is currently in then determine (based on a pre-defined set of instructions in the form of a table), what the machine will do. At every such step it will do 3 things:

  1. Write a new symbol over the one just read (or leave it alone)
  2. Move the head one cell to the left or to the right (or stay where it is)
  3. Change the internal state of the head (or leave it alone)

The following is a (very) simple example of a Turing machine which takes as input a series of ‘0’s and ‘1’s and negates them. So for example, ‘1011’ would end up as ‘0100’.

Current State Read Symbol Write Symbol Move New State
A [empty] [empty] Right Halt
A 0 1 Right A
A 1 0 Right A

This machine has only 1 state, and 2 symbols, and when it reads a symbol it overwrites it with the opposite symbol; then it moves to the right and stays in the same internal state. Finally, if it reads an empty cell, the machine stops, because it is done. This will go through the symbols 1-by-1 and replace each “0” with a “1” and vice-versa.

Now, this is a VERY simple example, and it turns out that any algorithm can be run on a Turing Machine (given the appropriate table of instructions). It can add numbers, subtract numbers, multiply numbers, etc. It can theoretically compute anything that any actual modern computer can. But, it is important to make the distinction that “Turing machines are not intended to model modern computers, but rather computation itself” (Wikipedia). For example, there are many things modern computers can do that are not computational in nature, but rather interact with the world in different ways, such as printing documents, or receiving a live stream of data (as with a video-game).

Actually, I lied. Or at least made a misleading remark. I said that any algorithm can be run on a Turing Machine. But, really, the reason Turing devised the idea of such a machine was to be able to define the term “algorithm”. He defined an “algorithm” as a the instruction table given to a Turing Machine. So, to say that an algorithm can be run on a Turing Machine is meaningless, as Turing Machines are what give meaning to the word algorithm. Now, it turns out to be generally agreed upon by every computer scientist and mathematician that everything that can be computed by any set of rules, can be computed by a Turing Machine (in other words, they agree with Turing’s definition of algorithm).

Universal Turing Machines

So, now you (supposedly) know what a Turing Machine is…but what is a “Universal Turing Machine”? Well, a “Universal Turing Machine”, is any Turing Machine which can simulate any other Turing Machine. That is, a Turing Machine (A) is “Universal”, if it takes as input (on its strip of tape) a table of instructions of some other Turing Machine (B), and then it essentially runs a simulation of that machine (B). Here is an analogy (although, keep in mind it may not be perfect): Think of a normal Turing Machine like a simple calculator, which can do any number of a predefined set of operations on arbitrary input(s), but if you have a calculator that doesn’t have a “square-root” button, then it can’t compute the square root; Now, think of a Universal Turing Machine as a computer, which can do any task you want, even if it wasn’t pre-programmed, but you have to then tell it “how” to do what you want it to (as programmers do for computers by writing programs).

Coming Soon…

I intend to write a post on Lambda Calculus soon, in which I will also present my opinion that Alan Turing is over-popularized and overrated (not to say he wasn’t brilliant, because he was, and he helped crack the enigma machine, but I think the Turing Machine gets far more credit than it deserves, as will be explained soon).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s