For which problems do algorithms that generate a solution exist? This question defines the study of computability.

A programmer can direct a computer to repeat a series of arithmetic operations until some logical condition is satisfied. If the programmer fails to specify the terminating condition correctly, the computer will continue executing the instructions forever.

Will a given program complete its work in finite time?

Before anyone had built a computer, Alan Turing proved the impossibility of writing a program to answer that question. He supposed that a program-checking program could be written and then showed that a logical contradiction followed when he imagined using the program to check itself.

There are, of course, programs that check other programs for misspellings, unbalanced parentheses, and other kinds of errors. However, while it is possible to recognize an infinite loop in some programs, it is not possible to write a program that will reliably tell us whether or not any program that we give it contains an infinite loop.

Leave a Reply