Turing Machines – A Review

It’s known that the Turing machine was the first theoretical model of modern day computers. But it’ll be a fruitful effort to find out why? The fascinating thing was it’s still capable of computing most of the existing computer operations including basic arithmetic (addition, subtraction, etc…) into much complex algorithms. Therefore it’s worth digging down deep into this idea and see how it relates to (or how it does) computer operations.

The bare roots of Turing Machines go back into the theory of computation. During the early decades of 1900’s there’s been an increasing demand for a machine capable of computing. Obviously this was a part of several military projects run by allied groups for gaining victory over the war. So that, this signifies the necessity for defining the science behind computing. Generally, the computational theory consists of three parts.

  • Complexity
  • Computability
  • Automata

Let’s take a bottom-up approach. Automata is an art of modeling a machine based around the graph theory. A machine can be represented by states, inputs and state transitions. Basically it’s a directed graph where nodes represent the states and edges resemble the transitions. Next, Computability can be described as the ability to do a computation. Not all problems in this world are computable. For instance we can compute 2 + 2 = 4, but “will it rain today? ” sort of problems are out of the scope. Finally, Complexity is about how hard the computation is (complexity of the algorithm).

There’s a clear relationship between these three. Any computation has to be modeled, then it’s computed and evaluated how complex the steps in involved in computation. Turing machine addresses the first two – i.e. modeling a computation and then compute.

Turing machine was inspired by push-down automata. The elements of a Turing machine include a tape (having an infinite length), a tape header, states, inputs and state transitions. The tape header is capable of reading & writing to the tape, and also can move along either Left or Right direction of the tape. The tape contains the input string. The tape header can read, write, move Left, or move Right one input symbol at a time. A given input string can be either accepted or rejected, allowing us to decide the computability (known as decidability). Following illustrates a Turing machine in the simplest form.

Let’s see how it does a computation. A computation can be represented by a set of symbols. For instance aaaba can be thought of as 3 -1 , where a’s represent an integer and b’s represent the subtraction operator. And following is a Turing machine that can perform a subtraction operation.

We can start with the input string aaaba and then finally we get aa once we trace the operation through this Turing Machine. Which means aaaba gives aa, in other words 3 – 1 = 2. Likewise, a one can build a collection of Turing machines or a single machine capable of doing all these mathematical operations.

In conclusion, this idea presented in 1936 by Alan Turing, made a significant contribution for the development of a computable machine (computer in other words) and surprisingly, after so many decades it’s still applicable for today.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s