πŸ“š

Β >Β 

⌨️ 

Β >Β 

πŸ“±

3.18 Undecidable Problems

1 min readβ€’june 18, 2024

Minna Chow

Minna Chow

Milo Chang

Milo Chang


AP Computer Science Principles ⌨️

80Β 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 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.

Fiveable
Fiveable
Home
Stay Connected

Β© 2024 Fiveable Inc. All rights reserved.


Β© 2024 Fiveable Inc. All rights reserved.