Lets say you are given $n$ programs and you
want to determine EXACTLY which ones halt.
If you can ask the HALTING PROBLEM $n$ questions then you
could certainly deterimine this.
If you can ask the HALTING PROBLEM only $n-1$ questions
then could you do this?
More generally we ask the following:
Let $A$ be a set and $n$ be a number.
How hard, in terms of queries to $A$,
are the following problems.
1) Given $n$ numbers, exactly which ones are in $A$?
2) Given $n$ number, how many are in $A$ ?
3) Given $n$ number, is the number that are in $A$ even?
4) Are there functions that can be computed with
$n$ queries to $A$ that cannot be computed with $n-1$ queries
to $A$.
5) Are there sets that can be decided with
$n$ queries to $A$ that cannot be computed with $n-1$ queries
to $A$.