# Concept derivation guides

299 concept teaching guides, separate from the 36,000 individual question derivations.

[Search all questions & derivations →](/en/explore/)

1 1 results · Page 1 of 1



Concept guide



## [Decision problem: proving that a trial-division procedure is a decider on an explicit finite input set](/en/derivations/derivation-mko-decision-problem-01/?from=%2Fen%2Fderivations%2F%3Fq%3Dmko-decision-problem)

Take the input set X={0,1,2,3,4,5,6,7,8,9}, the specification P(x): 'x is prime', and the yes-instance set Y={x∈X ∣ P(x)}. In the explicit while-program model W, prove that the trial-division procedure D1 terminates on every x∈X and that D1(x)=true exactly when x∈Y, so D1 is a decider for (X,Y); then show that D2, which halts only on yes-instances, and D3, which tests only parity, are not deciders.

Decision problem

derivation-mko-decision-problem-01





1 1 results · Page 1 of 1