Decision problems
Computational problems with yes/no answers. Decision problems form basis of computability theory. Solvability classification: decidable, undecidable, semi-decidable.
Real World
Microsoft's compiler team cannot build a tool that checks whether any arbitrary C++ program will ever crash, because this is an undecidable problem — so instead Visual Studio uses heuristic analysis that catches common bugs without guaranteeing detection of all.
Exam Focus
Distinguish decidable, undecidable, and semi-decidable clearly — state whether the algorithm always halts, never halts, or halts only on 'yes'.
How well did you know this?