π

All Subjects

Β >Β

β¨οΈΒAP Comp Sci P

Β >Β

π±Big Idea 3: Algorithms and Programming

1 min readβ’october 12, 2021

Minna Chow

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.

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

Join Fiveable for free

Create a free account to bookmark content and compete in trivia

Browse Study Guides By Unit

πΉBig Idea 1: Creative Development

βοΈBig Idea 2: Data

π±Big Idea 3: Algorithms and Programming

π₯Big Idea 4: Computer Systems and Networks

β¨οΈBig Idea 5: Impact of Computing

βοΈFrequently Asked Questions

πExam Prep