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.)