2 ms·
> We always come to decision. There is no "semi" here. That's not really how I understand the "semi" in the terminology. For a decidable question, you can reco
by thaumasiotes 5y ago
> We always come to decision. There is no "semi" here.
That's not really how I understand the "semi" in the terminology. For a decidable question, you can recognize when the answer is yes, and you can recognize when the answer is no. For a semidecidable question, you can recognize when the answer is yes.
It doesn't take much of a stretch to describe that as cutting your capabilities in "half".
The way I usually think about this is that with full decidability, you can rule something in or out. With semidecidability, you can rule something in, but you can't rule things out.
That framework extends well to the situation described above, where if the compiler chooses to compile a program, then the typing in that program was valid, and if the compiler chooses to complain about the typing, we can't draw any conclusions. It doesn't match your example; you can't rule anything in or out.