Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)
share|improve this question
3  
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
1  
"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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.