HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
An Introduction to the concept of Theory of
Computation
One of the basic questions that strike to me as a computer science student and as a computer professional is to find out the limit of a computing device to solve any problem. As a child I used to think that computer is a magic machine that has answers for all my questions irrespective of the domain of queries. Then later on as a computer science student I realized that its a machine that works the way we people are going to design it. It can answer only those queries for which it is designed to answer.
Why should the problem of computational limit be of any interest to anybody? There are two major reasons for this - one is definitely a business interest and the other is inquisitive human nature. It is beyond the scope of this article to explain the business interest. As far as other reason is concern, the geeks are always after efficient utilization of the available resources. We will always be interested to extract as much work from the device as possible. And for that we must know the limit of the device.
So still the basic question is how many different and difficult problems a computing device can solve?
The simple answer to this question is- how many problems we are able to design that many problems we will be able to solve with a computing device. This is what the computational theory is trying to answer.
In order to elaborate the answer it is necessary to define in a formal way what a computer is. There are a number of useful models of computation. Some widely known models are: Deterministic finite state machine?, Pushdown automaton? and Turing machine?.
Of all these models Turing machine is the generic model, as it simulates computation in the absence of predefined resource limits memory and read/write head movement.
Turing machines are very simple and basic symbol-manipulating devices which can be adapted to simulate the logic of any computer that could possibly be constructed. Turing machines were described in 1936 by Alan Turing?. Turing machine is just technical concept and not meant to be a practical computing technology. Thus they were not actually constructed.
For example we can define a turing machine to indentify whether a given integer is an even number or an odd number over a set of positive integers.
Now with this computational model in hand, if we are able to find out the limitations of the model to solve a problem, we will be able to find the computational limit of the computer.
But wait, we are trying to take help from a machine to solve our problems. How are we supposed to get an answer to it until we are able to communicate the problem to the machine? Surrprized what I am talking about?
Similar to two human beings, a man and a machine also require a language to communicate their ideas. In computer science we define different type of languages that can be accepted by models of computation.
We are required to map the design solution in the language accepted to the model, then the computational model will be able to solve the problem and also the problem is required to be translated into the language.
All those solutions which cannot be mapped to the language accepted by Turing machine are the problems which define the limits of computational device or computer.
We will discuss further the problem classification.
maintained by: manjusha.kakirde@hsc.com
Comments
