decidability across the Chomsky hierarchy
The Chomsky hierarchy stacks language classes by expressive power, like a ladder: at the bottom the regular languages (recognized by finite automata), then the context-free languages (recognized by pushdown automata), and at the top the recursively enumerable languages (recognized by Turing machines), with the decidable languages tucked just inside the top rung. A natural question runs alongside this ladder: as you climb to more powerful models, how much can you still ALGORITHMICALLY decide about the languages? The answer is a steady, honest trade-off — power up, decidability down.
Reading the ladder for membership and the basic structural questions: for REGULAR languages essentially everything is decidable — membership, emptiness, finiteness, equivalence, subset, universality — all settled by finite state searches. For CONTEXT-FREE languages, the news is mixed: membership is decidable (CYK) and emptiness is decidable (generating-symbol marking) and finiteness is decidable, but equivalence is UNDECIDABLE, as are ambiguity and universality. For the RECURSIVELY ENUMERABLE languages (the Turing-machine level), membership is only semi-decidable — recognizable but not decidable — so the basic acceptance question A_TM is already undecidable, and emptiness and equivalence are undecidable too. The decidable languages themselves form their own class sitting strictly between context-free and recursively enumerable: closed under complement, every membership question in it answerable, by definition.
The lesson to carry away is the shape of the trade-off, stated honestly. Climbing the hierarchy is not free: each step up in what the model can express tends to cost you decidability of the questions you most want to ask about it. The regular and context-free rungs are the 'tame' part of the world where membership and emptiness always halt; the line where things go wrong is right at the jump to unbounded Turing-machine memory. This field has mapped the tame side; the very next field shows that the questions you cannot answer at the top — starting with the halting problem — are not just hard but provably impossible for any algorithm.
Equivalence is the cleanest litmus: 'do these two recognize the same language?' is decidable for two DFAs (regular), undecidable for two context-free grammars, and undecidable for two Turing machines. Same question, three rungs, three fates — power rises, decidability falls.
Up the hierarchy: more expressive power, fewer questions that any algorithm can settle.
Do NOT read this as 'higher = uniformly less decidable for every question'. It is question-by-question: CFG membership stays decidable while CFG equivalence does not. The trade-off is a tendency made precise problem by problem, not a blanket law.