Big Idea 3 · Topic 3.18 · Exercise 1
Decidable or Not?
25 minutes
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.
Part B, from your handoutNot recorded
Your handout says these are the same items available here. Part A stays on paper.
Q1 · 3 points on the handout
Write your OWN example of a decidable decision problem that is not already in the log, and name the single algorithm that answers it correctly for every input.
Q2 · 3 points on the handout
Explain the difference between a problem that is UNDECIDABLE and a problem that simply takes an UNREASONABLE amount of time. Give one example of each, and say which one still has a correct algorithm.
Q3 · 2 points on the handout
ENRICHMENT: A classmate says, 'Since the Halting Problem is undecidable, it is pointless - a computer can't tell us anything about whether programs halt.' Using the idea of solvable instances, explain what is right and what is wrong about this claim.
Q4 · 0 points on the handout
Next step: you classified and explained these by hand. Now head to the Topic 3.18 page, confirm your reasoning on the auto-graded version of this exercise, and bring your best explanation to the class discussion.
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.