Mathematicians including Kurt Godel, Alan Turing, and Alonzo Church concluded that some basic problems cannot be solved by computers. One such problem is determining whether a mathematical statement is true or false.Though it seems that this kind of problems can be solved by computer because they lies strictly within the realm of mathematics, no computer algorithm can perform this task. This situation results in development of ideas pertaining to theoretical models of computers which in turn may lead to the construction of actual computers.
The theories of computability and complexity are closely related. The objective of complexity theory is to classify problems as easy ones and hard ones, whereas computability tends to classify problems as solvable and not solvable. Computability theory introduces many concepts used in complexity theory.
Aspects of Computability Theory
Fig: Aspects of Computability Theory
Turing machine is a powerful model proposed by Alan Turing in 1936. It is the best mathematical model for computability theory. It can do whatever a typical computer can do but it cannot solve some problems that are beyond the theoretical limits of computation. Decidability is a kind of computability theory that investigates power of algorithms to solve problems. It is also necessary to know the unsolvability of some problems. The unsolvable problems, once found, may be simplified or altered so that an algorithmic solution can be found. Reducibility is a primary method of proving that certain problems are computationally unsolvable.
Reduction is a way of converting one problem to another problem in such a way that a solution to the second problem can help solving the first problem. For example, you cannot repair an electric fan if you don’t know about electrical works. So it is unsolvable problem for you. But if you find an electrician he can get it repaired. So finding the electrician is the second problem. If solve the second problem then you can solve the first problem of repairing the electric fan. Recursion theorem and logical theories are other aspects of computability theory.
Related Articles
What is hard computing? Hard computing is a traditional computing. It requires a precisely stated…
Soft computing is a problem solving technology. It tends to fuse synergically different aspects of…
Cluster computing is an approach to achieve high performance, reliability or high throughput computing by…
Magnitude Comparator is a combinational circuit capable of comparing the relative magnitude of two binary…
Full subtractor is a combinational circuit capable of performing subtraction on two bits namely minuend…
Half-subtractor is a combinational circuit capable of subtracting a binary number from another binary number.…