Is everything computable?

By McDonald, T. | Last updated 30th of November
 
Do you think your computer is amazing? It can do so much and reasonably quick most of the time, yes?  Perhaps you are beginning to think it will not be long before a computer can accomplish any task especially with knowledge of Moore’s law whereby the number of transistors per square inch on an integrated circuit doubles every eighteen months.  Nevertheless, some problems are not just difficult they are impossible to solve.

For some problem to be computable, it would need to be possible to solve it in a finite number of steps for every instance of that problem; we call this effective procedure.  Alan Turing came up with the idea of a machine that could solve a problem if given a set of precise instructions called a program, which he called a Turing machine.  In addition, he theorised of a universal Turing machine that could take the state of any other Turing machine.  It is important to remember that at the time, modern day computers did not exists and a computer was someone who worked out problems on paper.  Following from this, if a problem is solvable in a finite number of steps the Turing machine must, at some point, halt.  If it is possible to create a Turing machine to solve a problem in a finite number of steps we say it is computable and if not then it is incomputable/undecidable.

Some problems are just not computable.  For instance, such a problem exists in set theory called Russell’s paradox where if we say that R is a set of all sets that are not members of themselves, which means that R cannot contain itself, which puts it in its own set that are not members of themselves! The definition contradicts itself.  Put another way, if we say the hairdresser only cuts the hair of people that do not cut their own hair, who cuts the hairdresser's hair?  If the hairdresser does not cut her own hair that puts her in the group that do not cut their own hair.  If she does not cut her own hair, she is no longer someone that only cuts the hair of people that do not cut their own hair.  These types of problems are contradictions because they are always false; thus, is unsolvable.  In other words, it is impossible to think of a Turing machine to solve this problem because it contradicts itself; it has not a yes or no answer, which in turn means it is incomputable/undecidable.

Additionally, although possible to compute, some problems would take millions or even billions of years to complete. For example, the travelling salesperson problem (TSP) is one such problem.  The problem consists of travelling to a large number of cities one once and returning to the original city using the shortest path possible.  As the number of cities grows, the longer it takes to compute a solution until it becomes impractical to use.  Therefore, although the problem is computable, it is not practical in real terms.

In conclusion, it is notable that solving some problems is not possible even with advancements in technology because it is just not possible to solve them under any circumstances.  While other problems are computable, the time these problems take to compute is by no means practical.  Some problems will never be computable while others may be realistically computable if computer scientists can find better ways to compute the problem if indeed it is possible.  Certainly, however, computing has its limitations.