0
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ one thing tell reduction only possible to undecidable to undecidable? Reduction Decidable to undecidable possible? $\endgroup$
    – S. M.
    Oct 14, 2021 at 11:09
  • $\begingroup$ empty input means $\endgroup$
    – S. M.
    Oct 14, 2021 at 12:09
  • $\begingroup$ I'm not sure how it helps, but yes: it is possible to reduce a decidable language to an undecidable one. Empty input means that the contents of the tape are the empty word, usually denoted with $\varepsilon$. $\endgroup$
    – Steven
    Oct 14, 2021 at 12:29
  • $\begingroup$ Your answer is good.. I need understand your last paragraph... $\endgroup$
    – S. M.
    Oct 14, 2021 at 12:36
  • 2
    $\begingroup$ The first two paragraphs are only intuition. In mathematics, intuition is important, but only proof counts. $\endgroup$ Oct 14, 2021 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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