Undecidable Problems (College Board AP® Computer Science Principles): Flashcards
0Still learning
Know0
Define decidable problem.
Was this flashcard helpful?
Cards in this collection (9)
Define decidable problem.
A decidable problem is one where an algorithm exists that can always produce a correct yes/no answer for every possible input.
Define undecidable problem.
An undecidable problem is one where no algorithm can be constructed that always produces a correct yes/no answer for every possible input.
Why is "Is the number n even?" a decidable problem?
It is decidable because dividing by 2 and checking the remainder always gives a definitive answer.
What does an algorithm for a decidable problem guarantee?
It is guaranteed to terminate and give the correct answer in a finite number of steps.
Define halting problem.
The halting problem asks: given a program and an input, will the program eventually stop or run forever?
True or False?
The halting problem is undecidable only because today's computers are not powerful enough.
False.
It is not a limitation of current technology. It is a fundamental mathematical impossibility.
True or False?
It has been mathematically proven that certain problems cannot be solved by any algorithm in all cases.
True.
Some problems are proven to be undecidable, such as the halting problem.
Although undecidable problems cannot be solved in all cases, _______ solutions may exist.
Although undecidable problems cannot be solved in all cases, partial solutions may exist.
What does it mean for an algorithm to terminate?
An algorithm terminates when it finishes running.
Sign up to unlock flashcards
or