Unsolvable Problems

Computers are amazing, and it seems like there must be nothing a computer cannot do. They are the artificial intelligence that underpins some of our favorite video games, they can beat human beings at checkers, chess, and Jeopardy, and they can even automatically and safely drive cars on the road, even with unpredictable human drivers alongside them. But as it turns out, computers can’t do everything, and never actually will be able to.

In this section, you will consider unsolvable problems in computer science, including one of the most famous problems in that category: the halting problem. You will also consider how practical workarounds can be made for unsolvable problems, and how unsolvable problems affect program design.

• Videos

  • Explanimator on Unsolvable Problems
  • Udiprod on the Halting Problem
  • It turns out, many practical problems reduce to the halting problem or other unsolvable problems. However, rather than giving up on these problems entirely, computer scientists use guidelines, or heuristics, to reach good-enough solutions. Check out this page by 101 Computing on heuristic approaches to problems and this thread by Quora on different ways of thinking about heuristics.

• Notes

  • Unsolvable Problems

• Thought Questions

  • Can you come up with other questions that a computer would never be able to answer?
  • Given these unsolvable problems, are popular perceptions of the power and potential of computers reasonable?
  • How might these unsolvable problems affect program design?
  • What might be a program that is affected by the halting problem?