Work through the list without notes. If you cannot do a statement, follow the pointer, then come back. Guide = the study guide; Practice = the practice questions.
Understanding
- I can define a decidable problem (Guide: Decidable problems; Practice: Question 1)
- I can define an undecidable problem (Guide: Undecidable problems; Practice: Question 2)
- I can state what the halting problem asks and that it is undecidable (Guide: The standard example: the halting problem; Practice: Question 4)
- I can explain that an undecidable problem can have solvable instances (Guide: Undecidable problems; Practice: Question 7)
Skills
- I can give examples of decidable problems and the algorithm that decides them (Guide: Decidable problems; Practice: Question 3)
- I can decide by inspection whether a simple program stops (Guide: The standard example: the halting problem; Practice: Question 6)
- I can classify a problem as quick, decidable but slow, or undecidable (Guide: Worked example 1; Practice: Question 10)
Reasoning
- I can distinguish undecidable from unreasonable running time (Guide: Worked example 1; Practice: Questions 5 and 8)
- I can explain why a perfect infinite-loop checker cannot exist (Guide: Worked example 2; Practice: Question 9)
- I can explain why a faster computer does not make a problem decidable (Guide: Common misconceptions; Practice: Question 8)
- I can explain why testing a program is not the same as proving it stops (Guide: Worked example 2; Common misconceptions)
- I can place a problem in one of three groups (reasonable time, unreasonable time, unsolvable) (Guide: Putting topics 3.17 and 3.18 together)
When every line is secure, move on. The revision notes are here: revision notes.