What Computers Can’t Do
We will not consider Artificial Intelligence (“AI”) problems such as language translation, speech recognition, medical diagnosis, etc. because of the imprecise nature of the inputs and outputs, and the vague criteria for a solution being “correct”.
Instead we will only consider problems that have precise specifications for inputs, outputs and problem description. The problems usually have a mathematical description and apply not only to numbers but also to strings, graphs (containing vertices and edges), tiles, etc.
Are there are problems that cannot be solved because every algorithm to solve it requires too many resources? Perhaps it can be proved that for some problem there are inputs of a moderate size (say 100) that would require billions of years even assuming the use of millions of computers that are a million times faster than today’s computers. Perhaps the computers would require a humungous amount of megabytes of storage. Such problems are often called intractable: algorithms exists but they all require astronomical resources.(Perhaps Quantum Computers may change this. Currently they operate on only a few bits “qubits”, and many are skeptical that they can be scaled up to thousands of qubits.) One such intractable problem will now be described.
The problem concerns statements about integers using addition, but not multiplication. Example: for all x, there exist y and z so that x+x+x = y+y+z. This statement is true: for any x, say x = 7, simply let y = 0 and let z = x+x+x (21). Example: there exist x and y so that x+x+x+x = y+y+1. This one is false: x+x+x+x is always even, but y+y+1 is always odd. More precisely, the problem is to determine if a given statement about integers using addition is true or not. It turns out that there is an algorithm to solve this problem (and is certainly not obvious!) with time complexity – a triple exponential. What’s worse is that it has been proved thatall algorithms have complexity at least - a double exponential! (where n is the length of the input). Double exponentials grow astronomically so this problem is intractable! If you thought that is bad there are problems (concerning statements about sets of integers) for which every algorithm has a complexity greater than all of O(2^n), O(2^2^n), O(2^2^2^n), O(2^2^2^2^n), … Are there any applications of this? Yes, Microsoft developed a language Spec# using these statements about integers to help prove that programs are correct.
Are there problems that cannot be solved because no such algorithms exist? Yes, and they are called undecidable. Several undecidable problems will now be described.
The first problem concerns positiveinteger solutions to equations containing variables, addition and multiplication. Example: is there a solution to x2 + y2 = z2 ?(Note: x2 is just x multiplied by itself.)Yes: there are many such as x = 3, y = 4 and z = 5 or x = 5, y = 12 and z = 13. Example: is there a solution to x2 + 10 = y2 ? No: examine the squares 1, 4, 9 and 16 and note that after these: 25, 36, 49, 64, … the differences are all bigger than 10. Example: is there a solution to x2008 + y2008 = z2008 ? No: after about 350 years a mathematician proved that xn + yn = zn has no solutions for any n > 2. Example: is there a solution to x3 + y3 = z3 + 33? As of 2008, nobody yet knows the answer. This is an example of an unsolved problem: it is either true or false, but nobody yet knows which! (If you replace 33 with 30 a solution was found containing 9 digit numbers!) For the original problem of determining if such equations have a solution, it has been proved that this problem has no such algorithm: it is an undecidable problem. The proof requires advanced math!
Another problem of more interest to computer programmers is the Loop Detector (or the inverse HaltingProblem). When a given program is run on a given input, does it (eventually) stop, or does it loop forever? Often you can analyze a small program with a given input and after some reasoning conclude that it does loop. However, consider
for max 1, 2, 3, …
for x 1, 2, …, max
for y 1, 2, …, max
for z 1, 2, …, max
if x3 + y3 = z3 + 33 then
stop
This algorithm searches for a solution to the above unsolved problem by trying all possible values of x, y and z. Does this program loop? Nobody yet knows. So, it is unlikely that a general purpose Loop Detector could determine the answer.
Another unsolved problem is the “196 palindrome” problem. Start with a given number, successively add the number to its reverse, and continue until a palindrome is found. Example: starting with 68 you get 68+86 = 154 then 154+451 = 605 then 605+506 = 1111. Example: starting with 89 you get 187, then 968, 1837 and after 20 more iterations you finally get the palindrome 8813200023188. If you start with 196 what happens? As of 2008 nobody yet knows. Computer programs have been run for millions of iterations reaching a number with 300 million digits but no palindromes have yet been found! And, nobody has proved that a palindrome will never occur. So, consider this program:
input n
repeat while n is not a palindrome
n n + reverse of n
stop
Again it is unlikely that a general purpose Loop Detector would determine the answer. It has been proved that a Loop Detector algorithm is impossible.Here is an easy proof. Assume that an algorithm, Loop, is possible, where Loop( program , data ) stops and outputs “yes” if the given program when run on the given data loops, else outputs “no”. Now consider this program:
Self:
input x
if Loop(x,x) outputs “yes”
stop
else
loop
What happens to Loop(self, self)? Assume that it outputs “yes” then according to the specification of Loop, it means that the program Self when run with input Self loops. But if you look at the program Self, it only loops if Loop(self,self) does not output “yes”. This contradicts the assumption. So, assume that it outputs “no”. Then according to the specification of Loop, it means that the program Self when run with input Self stops. But if you look at the program Self, it only stops if Loop(self,self) outputs “yes”. Again, this contradicts the assumption. Conclusion: The algorithm Loop is impossible! If you are troubled by programs that input themselves, think about a program that checks if its input, a string, contains an even number of characters. You can now use this program to check if the program itself contains an even number of characters. Or, consider a “pretty printer” program that inputs any program and “pretty” prints it – aligns and indents it nicely. You can then pretty print the pretty printer program! Also, a program to compress a file can be applied to itself!
There are undecidable problems related to matching strings of text: see the Post Correspondence Problem. There are undecidable problems related to real strings! – if I give you a piece of horribly knotted string that is joined at the ends, can you unknot it to form a simple loop with no knots? There are undecidable problems related to tiles with colours on their edges – given a set of such tiles (and an infinite supply of them) can you tile the entire plane in all directions so that colours on adjacent edges match? Google: “wang tiles undecidable”.