Big Idea 3 · Topic 3.18 · Exercise 2
Explain Why
25 minutes - 5 decision problems - classify and justify
Back to the Topic 3.18 lessonAll CSP topics
How this page works
The writing boxes below are yours. What you type stays in this browser, is saved here as you go, and is never sent to us or to your teacher. Hand the written work in the way your teacher asked for it.
The graded check at the bottom is the part that records to your teacher's gradebook.
The cases, from your handoutNot recorded
The same cases as your handout, in the same order.
Scenario 1 · Foundational
Problem: 'Is a given whole number positive?' You must answer yes or no for any integer someone provides.
Decidable or undecidable + a one-sentence reason:
Enrichment - a subtler point (solvable instance, or slow vs impossible):
Scenario 2 · Core
Problem: 'Is a given word a palindrome (reads the same forward and backward)?' for any word provided.
Decidable or undecidable + a one-sentence reason:
Enrichment - a subtler point (solvable instance, or slow vs impossible):
Scenario 3 · Core
Problem: 'For ANY program and its input, will the program eventually stop, or will it run forever?' This is the Halting Problem, which computer scientists have PROVEN cannot be solved by any algorithm.
Decidable or undecidable + a one-sentence reason:
Enrichment - a subtler point (solvable instance, or slow vs impossible):
Scenario 4 · Challenge
Problem instance: 'Does this exact program halt? - number <- 0; REPEAT 3 TIMES { number <- number + 1 }; DISPLAY(number).' Just this one specific program.
Decidable or undecidable + a one-sentence reason:
Enrichment - a subtler point (solvable instance, or slow vs impossible):
Scenario 5 · Challenge
Problem: 'Given a list of cities, is there a route visiting all of them whose total distance is below a given limit?' A correct algorithm exists (check every possible ordering), but for many cities it would take an astronomically long time.
Decidable or undecidable + a one-sentence reason:
Enrichment - a subtler point (solvable instance, or slow vs impossible):
No graded check on this page yetNot recorded
About the line in your handout
Your handout says this exercise is available online and auto-graded. The exercise IS here, and it is the same work in the same order, but the auto-graded half is not written for this topic yet. Nothing on this page is scored or sent to your teacher.
Hand this in the way your teacher asked for it. Topic 1.1 has its graded check today, and the rest follow.