Introduction

When we study computability, we study problems in an abstract sense. For example,

1. a. Addition is the problem of returning a third number that is the sum of two given numbers.

2. b. Travelling Salesman problem (TSP) is one in which a list of distances between some number of cities are given and the person is asked to find the shortest route so that he visits each city once and returns to the start.

3. c. Halting Problem (HP) is one in which a program is given some appropriate input and it needs to be decided whether the program, when run on that input, loops forever or halts.

Problems (b) and (c) are the two problems of computer interest.

In both these problems, the statement of the problem does not give the actual values needed to provide the result but just tells what kind of objects they are. A set of actual values for a problem is called an instance of the problem (by this terminology, all homework problems done by school students are considered as instances of problems).

In all these problems an instance is required that is the input and the relationship between the input and the output is to be understood. In order to solve these problems, there are certain things one should know.

1. Can it be solved algorithmically – is there any definite procedure that solves any instance of the problem in a finite amount of time? In other words, is it computable? Not all problems are computable.