# Is a statement concerning the future part of a decidable problem?

Let Did I ever get 100% in an exam? be a problem and the corresponding (characteristic) function $$\chi(x)=\begin{cases}1,& \text{if the statement can be answered with yes},\\0,&\text{otherwise}.\end{cases}$$ This problem apparently seems to be decidable because we could look up all exam results and evaluate this function.

But what if we change the problem to Will I ever get 100% in an exam?

• Is this problem semi-decidable or undecidable?

In my opinion one could deduce with the theorem of Rice that this problem is not decidable. Furthermore having a problem $A$ we know that

$$A \text{ semi-decidable}\Leftrightarrow \chi_A' \text{ computable}\Leftrightarrow A \text{ recursively enumerable}$$

and therefore I think that our characteristic function will be computable because it will return 1 if I ever get 100% otherwise it will wait for the next exam to be done and this could be repeated until we get the result and then the problem would be semi-decidable. Furthermore I was thinking about a reduction of the problem to the general halting-problem but I have no idea right now.

• Has anyone a good explanation what to do with this? (This is no homework, just curiosity.)
-
The function itself is a decidable function, since it is a constant, and we can write a computer program which computes it. The fact that we don't know which computer program it is is irrelevant for the definition of "decidable." – Thomas Andrews Nov 15 '12 at 16:56
"Will I ever get 100%" is definitely decidable, by the way, since you will eventually die. So a program will only have to wait until that eventuality, monitoring all your test results. :) It's just a very slow program. – Thomas Andrews Nov 15 '12 at 17:00
@ThomasAndrews: What about a scenario where the monitored process will last infinite long? – Christian Ivicevic Nov 15 '12 at 17:07
Well, the second comment was snark. The first comment addresses whether the function is computable/decidable. It is, since the function is constant, and all constant functions are computable. The fact that we might never know which function it is does not matter for determining whether the function is decidable. – Thomas Andrews Nov 15 '12 at 17:16
@ThomasAndrews: Ah ok, one last question - is there any yes/no question which is NOT decidable? – Christian Ivicevic Nov 15 '12 at 17:17

In your case, your function is constant. It is either $\chi(x)=0$ or $\chi(x)=1$. Both of these functions are computable. We might not know which one of these functions agrees with your function, but we know one of them does, and hence the problem is decidable.
Therefore, "undecidable" problems are not a single "yes/no" question, but rather questions about inputs - propositions of a variable, $P(n)$.
The mathematical equivalent of your example would be to start with a decidable proposition, $Q(n,m)$, and define $P(n)=\exists m: Q(n,m)$. Even if $Q$ is easily and obviously decidable, $P$ might not be.
For a specific example, if $Q(n,m)$ is "$n$ is the code for a computer program and the input to the program, and the program halts in fewer than $m$ steps," then $Q$ is easily seen to be decidable, but $P$ is the halting problem, which is undecidable.