CS 4, Summer 2009

Concepts in Computing

[prev]

This course has focused on what we can do with computers. But what about things that computers cannot do well, or perhaps not even at all? It turns out that there are "reasonable-sounding" tasks that fall into those categories -- they are in some sense "officially hard" or "officially impossible". If we want to show that a problem is possible / easy, all we have to do is provide an algorithm that solves it. Thus, for example, searching and sorting fall into that category. It's actually much more difficult to show that a problem is hard / impossible, but it's important to know that it is, so we don't waste a lot of effort trying to come up with a good solution, and keep thinking that maybe we just haven't thought hard enough about it.

One little bump in the road to showing that a problem is officially hard or impossible is the question of how we might express the solution. Does it matter whether we're using pseudocode, Javascript, machine-level language, or something else? The Church-Turing Thesis basically says that it doesn't matter -- there is a simple computational model into which any algorithm expressed in any other language can be converted. Nobody has ever found an algorithm for which that wasn't the case. For this reason, although the Church-Turing Thesis is a "leap of faith" -- it must simply be believed, since it cannot be proven -- it is a very reasonable belief to hold, given our experience as scientists studying the properties of algorithms and computers. Instead of going into the computational model here, we'll just talk intuitively about the types of problems and rest assured that the results hold no matter how we might try to express a solution.

• NP-complete problems
• Undecidable problems
• The halting problem

NP-complete problems

When we talked about algorithms, we looked at some relatively efficient ones, including linear search (could take time proportional to the length of the array), binary search (logarithmic) and sorting (the length squared). These and many others are all "polynomial-time" algorithms -- how long they take is at most some polynomial in the input size. We also looked at how bad exponential time is. Clearly if we have to enumerate or explicitly consider an exponential number of things, we'd better have small inputs.

There's an interesting class of problems for which we just don't know whether or not there exists a polynomial time solution. Most computer scientists would bet not, but there's no proof of that (if you can, let me know -- you'll definitely earn extra credit for this class, along with numerous awards). These so-called NP-complete problems are all in some sense equivalently as hard as each other, so if we could find an efficient solution to one, we'd be able to solve them all. Nonetheless, nobody has been able to.

Here are some examples of such problems.

Satisfiability

Given a Boolean formula (like those we saw in circuit construction), does there exist a choice of true/false for each of the variables, such that the whole thing evaluates to true?
As we saw, a Boolean formula corresponds to a truth table. So basically we're asking if any row of that table has a "true" output. But for n variables, the truth table has 2ⁿ rows, so in general we can't just enumerate them all. We just don't know if there is an efficient algorithm (avoiding enumeration) that's always correct.

Traveling Salesperson

Given some cities that we want to visit, what's the shortest route that visits each city exactly once?
There are a lot of possible routes, so again in general we can't just enumerate them all. But is there an efficient algorithm?

Knapsack

Given some items that we want to carry, each with a weight and a value, fill up our knapsack with the most expensive load that's not too heavy (below a weight limit).
Again, there are lots of possible sets of items we could consider, so the question is whether we can efficiently determine the best.

All these problems are NP-complete, which means that (most computer scientists believe that) in general we can't efficiently find the answer. In any particular case, we might be able to. For example, if someone asked whether the Boolean formula A + B could evaluate to true, we'd immediately say sure. The point is that there are lots of other cases, and we can't guarantee that we can efficiently determine whether or not any given formula is satisfiable. Since these problems (and variations on them, and related ones) are actually very important in a number of real-life sitations, we do need to solve them. So we either give up on always being efficient (we might not find a solution in a reasonable time) or always being correct (we might give the wrong answer, or a not-quite-best answer).

Note that having a large number of possible solutions doesn't imply that a problem is NP-complete. For example, there are an exponential number of ways to sort an array, but we can do that very efficiently without considering them all. It takes clever proofs to show that a problem indeed is NP-complete, and I encourage you to take CS 39 (after a few more CS courses) if you want to learn how to do that.

Undecidable problems

Informally, we say that a problem is decidable if we can construct an algorithm that computes the answer to that problem, for any input of the correct form. If we cannot construct such an algorithm, we say that the problem is undecidable.

Here are some problems that cannot be solved by algorithms -- they are undecidable:

Program equivalence

Suppose we have two computer programs -- perhaps one of them is the sample solution to a homework problem, and the other is a student's homework submission for that problem. These two programs are not identical, but we would like to determine if they do the same thing. Doing this by hand seems practically impossible. Ideally, we'd like to be able to write a third program which, given both of these programs, will tell us whether they compute the same results for any given input. Unfortunately, we cannot write such a program.

Halting

Suppose we have written a computer program which performs a large and sophisticated computation. We feed it an enormous set of data, and set it running. After a while, we begin to wonder, "is this program ever going to stop and give me an answer? What if there is some kind of error in the program, which will cause it to run forever and ever without giving me a result?" We could stop the program, but what if it was only a few seconds away from being finished? We'd like to design a computer program which could look at our code, and tell us right away "if you run this program, it will never halt." Sadly, this too is undecidable, and we cannot write such a program.

Program usefulness

Along the same lines as the halting problem, we cannot write a program which will determine if there is any input value for which a given program will eventually halt. That's a very basic property we'd like any program to have -- it halts for at least some input -- but we can't even verify that.

As we've seen, the limitations of what is computable are not just esoteric -- even questions we care about, like the Halting Problem or the Program Equivalence Problem, are impossible in the general case.

On the other hand (just as with NP-complete problems), that does not mean we can't solve these problems in special cases. In fact, it may be possible to examine a particular program and determine that it will never halt:

  function P(x)
  {
    while (true) { }
  }

The point is, we could never write a program that would give the correct answer for any Javascript program that it is given.

The halting problem

How do we prove that there is no algorithm to solve some problem? We might sit down, think really hard, and realize that we cannot think of any algorithm that will always work. We might, then, conclude that no such algorithm exists. But what if some really clever person comes along a few minutes later -- or a few weeks, months, or even years later -- and comes up with an algorithm that does work correctly? It's not sufficient that we can't find an algorithm by thinking really hard -- we need to prove that such an algorithm cannot exist, in order to show a problem to be undecidable.

Let's consider the Halting Problem, and state it a little more formally:

Design an algorithm M which takes a program P and an input value x for that program. Algorithm M should halt and return 1 if running P(x) would eventually stop and return an answer; otherwise, M should halt and return 0, indicating that P(x) would run forever without stopping.

The actual proof requires some mathematical formalism that I don't want to go into. But I think you can get the intuition for it from two different representations. It's kind of brain-twisting, relying on deriving a contradiction. That is, we assume that we have an M that works as advertised, and back ourselves into a corner with a logical inconsistency. The only way to get out of the corner is to recognize that our original assumption must be bogus.

The other brain-twisting aspect of what we'll do is it's self-referential. We get a paradox kind of like:

This sentence is false.

(Thanks to Douglas Hofstadter's classic book Godel, Escher, Bach: An Eternal Golden Braid, which I encourage you to read.)

Intuition

Suppose we have a program M that takes as input an encoding of some program P, along with the input for P. M then returns whether or not P halts when given the input. An encoding is just a way to represent the program in a way that we know what it means (maybe a string holding a piece of Javascript, as below); I denote encodings with quotes in the following figures.

Now we build a program Q that takes as input an encoding of a program P and runs the program M to see whether P halts when given its own encoding as input. If M indicates that P halts, then Q enters an infinite loop; if M indicates that P doesn't halt, then Q halts.

What happens when we give Q as input an encoding of itself? If M decides that Q halts, then Q doesn't halt; if M decides that Q doesn't halt, then it does. The way out of this contradiction is to conclude that there is no such M.

Javascript

Suppose someone has given us a Javascript function called M. M takes two parameters, both strings. The first parameter is a string containing a Javascript function. For example, it could be the string:

  var P = "function hello(name) { alert('hello '+name); }";

The second parameter is a string containing the parameter to that function. For example, it could be the string:

  var who = "Chris";

We are told that M returns whether or not a given function (described in a string) halts, when called with a given parameter value (another string). Thus in our example, calling M(P,who) should tell us whether or not hello("Chris") halts in a finite amount of time.

With such an M available, we can write another function Q:

  function Q(A)
  {
    var result = M(A,A);
    if (result) {
      while (true) { 
        /* Do nothing -- an infinite loop */
      }
    }
    return 1;
  }

This is just some simple Javascript, which calls the M function with a couple of parameters (they happen to be the same), and doing something depending on what M returns. But now we can stick this Javascript into a string:

  var B = "function Q(A) { var result = M(A,A); ... }";

Finally, we can call our Q function with parameter value B (which holds the string "function Q(A) { ... }").

  var C = Q(B);

Now the question is: what is C?

• If C is 1, then Q(B) must have halted. That means that M(B,B) returned false (since if it returned true, Q wouldn't have halted). By the definition of M, since M(B,B) is false, calling the function described in B on the parameter B does not halt. But the function described in B is Q itself. So M says Q(B) doesn't halt, contradicting the first sentence in this paragraph.
• Suppose Q(B) didn't halt (so C never got a value). That means M(B,B) returned true, and thus calling the function described in B on the parameter B halts. But since B encodes Q, M says Q(B) halts, and again we have a contradiction.

In either case, there is a contradiction between what M says and what Q does. So M doesn't do what it is advertised to do -- accurately tell us whether or not a function halts given an parameter. Since we didn't assume anything about M, this means that no such M can do that.

As with the NP-hard problems, there are important practical applications involving undecidable problems (e.g., in analyzing high-level programs to generate efficient machine code). Thus people still attack the problems, but under the warning that they are up against something that is "provably impossible" and in fact might bite them.