Fiveable
Fiveable
try guided practice free
try guided practice free
AP Computer Science Principles
Find gaps with guided practice
Guided practice grid visualization
Table of Contents
Unit 3 Overview: Algorithms & Programming Fundamentals
Big Idea 3: Algorithms and Programming
3.1 Variables and Assignments
3.2 Data Abstraction
3.3 Mathematical Expressions
3.4 Strings
3.5 Boolean Expressions
3.6 Conditionals
3.7 Nested Conditionals
3.8 Iteration
3.9 Developing Algorithms
3.10 Lists
3.11 Binary Search
3.12 Calling Procedures
3.13 Developing Procedures
3.14 Libraries
3.15 Random Values
3.16 Simulations
3.17 Algorithmic Efficiency
3.18 Undecidable Problems

⌨️ap computer science principles review

3.18 Undecidable Problems

Verified for the 2025 AP Computer Science Principles exam•Citation:

Image source: GIPHY

A decidable problem is a decision problem (one that has a yes/no answer) where an algorithm can be written to produce a correct output for all inputs. 

If an algorithm can't be written that's always capable of providing a correct yes or no answer, it's an undecidable problem. An undecidable problem might be able to be solved in some cases, but not in all of them.

The classic example of an undecidable problem is the halting problem, created by Alan Turing in 1936. The halting problem asks that if a computer is given a random program, can an algorithm ever be written that will answer the question, will this program ever stop running?, for all programs? By proving that there wasn't, Turing demonstrated that some problems can't be completely solved with an algorithm.

Conclusion

There are some problems (undecidable problems) that computers just cannot solve. An undecidable problem may be solvable for some cases, but there is no algorithm that will solve the problem in all cases.

There's a crash course in programming, AP CSP style! In our next guide, we'll be discussing the Internet.

Key Terms to Review (4)

Alan Turing: Alan Turing was a British mathematician, logician, and computer scientist who is widely considered the father of theoretical computer science and artificial intelligence. He made significant contributions to the development of modern computing by creating the concept of a universal machine, known as the "Turing machine," which laid the foundation for modern computers.
Decidable Problem: A decidable problem is a computational problem for which there exists an algorithm that can determine whether a given input has a specific property or satisfies a certain condition.
Halting Problem: The halting problem refers to the question of whether an arbitrary program will halt (terminate) or run forever when executed on some input.
Undecidable Problem: An undecidable problem is a computational problem for which no algorithm can determine whether a given input has a specific property or satisfies a certain condition.
Back
Practice QuizGlossary
Next