I know that
- decidable problem: has both counting (bijection with $\mathbb N $) and membership algorithm (TM halts for both member and non member strings )
- semidecidable problem: has counting algorithm and TM halts for member strings
- countable problem: has only counting algorithm
Now I have come across undecidable language set which does not have membership algorithm (as semi decidable languages at least have TM which halts for member strings, which is not the case for undecidable problems), that is it does have TM that halt neither for member string nor for non member string.
I have doubt about the relationship between these language classes.
I know "decidable $\subset$ semi decidable $\subset$ countable".
Where does "undecidable" fit here?
Is it like this?:
(Match the color of text with that of the border. Region color is lighter shades of corresponding enclosed texts.)
Q. Is above diagram correct? Also I want to add "countable" to above. I feel, for finite alphabet languages, countable will be proper superset of "undecidable". Is it right?
PS: I feel, earlier I based my understanding of "undecidable" on incorrect definition given in this question. So I draw wrong diagram earlier. I believe its correct now.