Question: What can a computer algorithm not solve?

Giuseppe Cotugno answered on 2 Jan 2020:

The British scientist and mathematician Alan Turing was one of the first people to study which algorithms a computer can or cannot solve using formal mathematical derivations. However, you shall never forget that the computer which will execute the algorithm is a factor of fundamental importance.

For our practical purposes, a computer cannot solve problems called “intractable”. Those problems might have a theoretical solution but it doesn’t exist a real computer that can solve this problem. The limitation can be the current technology or, even worse, the current mathematical model of an algorithm solver (called Turing machine).

For example, you can’t use an algorithm to decide whether Windows Update will ever terminate or will loop forever. This is called “halting problem” which has no solution.

Another set of problems which cannot be solved in practice are those about finding passwords or decoding encrypted messages. In this case the algorithm to break the encryption or to find the password is known (i.e. try all possible combinations) but even the most powerful computer in the world would require several centuries before finding the solution.

Remember, algorithms, like mathematical models, are the theory. Even if the algorithm can solve a problem in theory you still need a real world computer which is able to execute them within acceptable time.

Just think of 3D computer graphics. Modern 3D graphics algorithms, which were intractable in the late 80s, can be now executed within acceptable times because of technological improvements in the computer hardware (GPUs and multicore CPUs).