Skip to main content

Section 3.18 Undecidable Problems (2026)

45 minutes
Weโ€™ve been using algorithms to build our apps and weโ€™ve learned about algorithms for solving certain types of problems, such as searching and sorting problems.
It may seem that no matter what the problem, we can find an algorithm to solve it. But that is not true. And in this lesson we want to look at some problems that algorithms cannot solve or cannot solve efficiently.

Subsection 3.18.1 Problems that Cannot Be Solved by Algorithms

There are two categories of problems that an algorithm cannot solve.
  1. Undecidable Problems. These problems are the theoretically impossible to solve โ€” by any algorithm. The halting problem is a decision problem (with a yes or no answer) that is undecidable. A computer cannot tell if it is in an infinite loop or it will at some point stop!
  2. Intractable Problems. These problems are theoretically impossible to solve in a reasonable time โ€” i.e., there are known algorithmic solutions, but the algorithms are too inefficient/slow to solve the problem when the number of inputs grows large.
The following video will give us an overview of these types of limits to algorithms and will illustrate how we can use the fact that certain problems are intractable to protect our passwords and other information.

Subsection 3.18.2 Creating a Strong Password

To give us a better sense of what it takes to create a strong password -- i.e., one that can withstand a brute force attack -- weโ€™re going to use the Password Strength Calculator to test the strength of various password schemes. (Open widget in a separate window)
According to Wikipedia, an ordinary desktop computer equipped with special password cracking software can test more than 100 million passwords per second. The goal of this activity is to come up with the optimal password scheme that would take an ordinary PC, equipped with password-cracking software, more than 10 years to crack.

Activity 3.18.1.

A password scheme consists of a minimum password length and the different types of symbols (i.e., letters, numbers, specials) that can be used in the password. Using the Password Strength Calculator, determine the optimal scheme for withstanding a brute force attack of at least 10 years by an ordinary PC performing 100 million tests per second.

Activity 3.18.2.

According to this 2020 article, a password-cracking computer can try 669 billion passwords per second. How would you have to modify your scheme to withstand a 10-year attack by this specially designed computer?

Activity 3.18.3.

After youโ€™ve calculated the estimated number of passwords that can be checked per second for the next year, use the Password Strength Calculator to determine an optimal password scheme.
  • How long should the password be?
  • What combination of characters should it include?

Subsection 3.18.3 Heuristic Solutions to Intractable Problems

For some intractable problems, we need to have practical solutions. One such example is the Traveling Salesman Problem: Construct the most efficient route, the optimal route, that visits N cities. This is an optimization problem where the goal is to find the "best" (most optimal) solution among many.
This is a problem we would like to be able to solve. Variations of this problem are the kinds of problems that Google maps and other apps solve for us when we ask for driving directions.
Fortunately, there are so-called heuristic algorithms that computer scientists use to solve such problems. A heuristic algorithm is one that provides a solution to a problem, although in many cases the solution may not be the best possible solution -- i.e., it may not be an optimal solution.
The following video will give us an overview of the Traveling Salesman Problem.

Subsection 3.18.4 Traveling Salesman Activity

Winnie the Pooh is looking for his friends. He must visit every location once and return home. Which route is shortest?
Use the activity to answer the following questions.

Activity 3.18.4.

Starting from Pallet Town, how many different round trips visit all 6 cities exactly once? (Direction counts: going clockwise vs. counter-clockwise are different.)
  • 6
  • Not quite. Poohโ€™s House is fixed as the start, leaving 5 cities to order: 5! = 5ร—4ร—3ร—2ร—1 = 120. (Ignoring direction, thatโ€™s 60 distinct loops.)
  • 30
  • Not quite. Poohโ€™s House is fixed as the start, leaving 5 cities to order: 5! = 5ร—4ร—3ร—2ร—1 = 120. (Ignoring direction, thatโ€™s 60 distinct loops.)
  • 120
  • Correct! Poohโ€™s House is fixed as the start, leaving 5 cities to order: 5! = 5ร—4ร—3ร—2ร—1 = 120. (Ignoring direction, thatโ€™s 60 distinct loops.)
  • 720
  • Not quite. Poohโ€™s House is fixed as the start, leaving 5 cities to order: 5! = 5ร—4ร—3ร—2ร—1 = 120. (Ignoring direction, thatโ€™s 60 distinct loops.)

Activity 3.18.5.

The โ€œnearest-neighborโ€ strategy always goes to the closest unvisited city. Press the Nearest-neighbor button. Does it always find the shortest route?
  • Yes, always
  • Not quite. Nearest-neighbor is fast but greedy: an early short hop can force a very long hop later. Compare its total to the shortest one.
  • No, not always
  • Correct! Nearest-neighbor is fast but greedy: an early short hop can force a very long hop later. Compare its total to the shortest one.

Activity 3.18.6.

With 20 cities there are 19! โ‰ˆ 1.2 ร— 10ยนโท routes. A computer checks 1 million routes per second. About how long to check them all?
  • About 2 minutes
  • Not quite. 1.2ร—10ยนโท รท 10โถ โ‰ˆ 1.2ร—10ยนยน seconds โ‰ˆ 3,800 years. Checking every route doesnโ€™t scale!
  • About 4 days
  • Not quite. 1.2ร—10ยนโท รท 10โถ โ‰ˆ 1.2ร—10ยนยน seconds โ‰ˆ 3,800 years. Checking every route doesnโ€™t scale!
  • About 3,800 years
  • Correct! 1.2ร—10ยนโท รท 10โถ โ‰ˆ 1.2ร—10ยนยน seconds โ‰ˆ 3,800 years. Checking every route doesnโ€™t scale!
  • About 1 second
  • Not quite. 1.2ร—10ยนโท รท 10โถ โ‰ˆ 1.2ร—10ยนยน seconds โ‰ˆ 3,800 years. Checking every route doesnโ€™t scale!

Activity 3.18.7.

Why do computer scientists care about this problem?
  • Itโ€™s only about salespeople
  • Not quite. TSP is a famous โ€œhardโ€ problem: real tools use clever shortcuts and good approximations.
  • It models delivery, circuit boards, DNA sequencing, and more โ€” and no fast exact method is known
  • Correct! TSP is a famous โ€œhardโ€ problem: real tools use clever shortcuts and good approximations.
  • Computers canโ€™t add distances
  • Not quite. TSP is a famous โ€œhardโ€ problem: real tools use clever shortcuts and good approximations.
  • Itโ€™s solved instantly for any size
  • Not quite. TSP is a famous โ€œhardโ€ problem: real tools use clever shortcuts and good approximations.

Subsection 3.18.5 Still Curious?

Subsection 3.18.6 Undecidable Problems Review

Activity 3.18.8 Undecidable Problems Vocabulary.

Activity 3.18.9.

Is the following problem tractable (solvable in a reasonable amount of time) or intractable (cannot be solved in a reasonable amount of time)?
For any length string of letters using any combination of the letters โ€™aโ€™ through โ€™zโ€™, write down all possible strings.
  • Tractable
  • Let me add new information to help you solve this question. There are 26 possible 1-letter words, 26 ร— 26 2 letter words, 26 ร— 26 ร— 26 3-letter words, and so on. So there would be 26N N-letter words. This is exponential.
  • Intractable
  • Yes. If the string has N letters โ€™aโ€™ to โ€™zโ€™, then there are 26N possible strings, which is exponential. This is similar to trying to crack a long password made up of lowercase letters. In this case, each letter in the password can be one of 26 possible letters. If you made such a password long enough (e.g., more than 15 letters), it would be fairly secure from brute force attack.

Activity 3.18.10.

An algorithm can be found for any computational problem whatsoever.
  • True
  • This is challenging, but rewarding! The Halting Problem is an example of an unsolvable problem.
  • False
  • Yes. The Halting Problem is an example of an undecidable problem, as Turing proved.

Activity 3.18.11.

The Halting Problemis an example of
  • a difficult problem.
  • an undecidable problem.
  • Yes. As Turing proved, it is impossible to solve the Halting Problem.
  • an intractable problem.
  • Intractable problems are those for which there are known algorithms but the algorithms are exponential and therefore too inefficient to solve the problem for large N.
  • an exponential problem.

Activity 3.18.12.

Under which of the following conditions is it most beneficial to use a heuristic approach to solve a problem?
  • When the problem can be solved in a reasonable time and an approximate solution is acceptable.
  • When the problem can be solved in a reasonable time and an exact solution is needed.
  • When the problem cannot be solved in a reasonable time and an approximate solution is acceptable.
  • When the problem cannot be solved in a reasonable time and an exact solution is needed.

Activity 3.18.13.

Explain in your own words what it means for a problem to be intractable. Why is that a good thing when it comes to passwords?

Activity 3.18.14.

Describe a heuristic you use in your everyday life. Why is a heuristic needed for this situation?
You have attempted of activities on this page.