Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Membership problem of Recursive languages are decidable.
My approach:
Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it. For string $w,$ if $w ∈ L,$ then $M$ halts in final state. If $w ∉ L,$ then $M$ halts in non-final state. (halts always!). That's why Recursive languages are decidable for Membership problem
My question is in same logic, why finiteness, emptiness is undecidable? Don't want any concrete proof. I just want brief concepts like my approach.
To decide whether a language is empty you'd have to run $M$ on all possible input strings and verify that $M$ always rejects. How are you going to do that in a way that ensures that your algorithm always terminates?
Similarly, to decide whether $L$ is finite you'd have to check that $M$ rejects almost always, i.e., always except for at most a finite number of inputs.
Formally, you can reduce the halting problem to problem of deciding whether a language $L$, encoded as a decider machine for $L$, is empty/finite.
For example, given Turing machine $T$ you can define a Turing machine $T'$ that takes a string $x$ as input and simulates $T$ on empty input for $|x|$ steps. If the simulation ends, $T'$ accepts. Otherwise $T'$ rejects. Then, you can decide if $T$ halts on empty input by checking if the language recognized by $T'$ is not empty.
