$A=\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\}$

Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is possible. Then deciding whether cardinality is greater than 3 should be decidable. But the material that i have been studying says it is partially decidable. Which one is right?

  • 1
    $\begingroup$ You can't necessarily enumerate all the strings in finite time - in particular if there's an infinite number of them, this is impossible. In this case there is an infinite number of Turing Machines in $A$ themselves with infinite languages. $\endgroup$ – Luke Mathieson Feb 5 '15 at 6:46
  • $\begingroup$ What does "partially decidable" mean? $\endgroup$ – Andrej Bauer Feb 5 '15 at 7:59
  • $\begingroup$ @AndrejBauer It's yet another name for RE. $\endgroup$ – Luke Mathieson Feb 5 '15 at 8:07
  • $\begingroup$ Why do we need yet another name for c.e.? Oh well. $\endgroup$ – Andrej Bauer Feb 5 '15 at 8:12

The language is clearly not decidable; use Rice's theorem. See e.g. our reference question.

We can certainly simulate $M$ on every input by dovetailing and count accepted inputs; if $|L(M)| \geq 3$ our counter hits three after finite time and we accept, otherwise we loop. Therefore, $A$ is semi-decidable.


You can make a reduction from the HALTING problem({,w| is a turing machine that halts on w}), using pseudocode:

def R(<M>,w):
    def F(x):
        M(w) //run M on w, if it loops we are rejecting everything
        return x in ('1','2','3')
    return F

For every x in HALTING problem, there is some y in A, such that f(x) = y.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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