πŸ“š

All Subjects

Β >Β 

⌨️ 

AP Comp Sci P

Β >Β 

πŸ“±

Big Idea 3: Algorithms and Programming

Undecidable Problems

1 min readβ€’october 12, 2021

minnachow

Minna Chow


AP Computer Science Principles ⌨️

BookmarkedΒ 2.6kΒ β€’Β 69Β resources
See Units

https://firebasestorage.googleapis.com/v0/b/fiveable-92889.appspot.com/o/images%2F-omABbLUa01Qn.gif?alt=media&token=b8f7afd5-3c7f-4f8f-9061-10f46f1e666e

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's a crash course in programming, AP CSP style! In our next guide, we'll be discussing the Internet.

Was this guide helpful?

Fiveable logo
Join Fiveable for free
Create a free account to bookmark content and compete in trivia
Hours Logo
Studying with Hours = the ultimate focus mode
Start a free study session
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
πŸ“± Stressed or struggling and need to talk to someone?
Talk to a trained counselor for free. It's 100% anonymous.
Text FIVEABLE to 741741 to get started.
Β© 2021 Fiveable, Inc.