0
$\begingroup$

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.)
  • 0
    For example, if $Q(n,m)$ is a proposition about two natural numbers, and $P(n)$ is the statement $\exists m: Q(n,m)$, then it is quite possible that $P$ is not decidable. For example, if $Q(n,m)$ is the statement "$n$ is a code for a Turing machine and some input, and it halts in $m$ or fewer steps." Then $Q(n,m)$ is decidable, but $P(n)$ is the halting problem, and is undecidable.2012-11-15

1 Answers 1

2

Undecidability is stronger than saying that a problem cannot be solved. It actually says that there isn't a program that even accidentally solves your problem. That is, for all programs, we can show that the program does not output the same values as the function we are looking for.

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.