# will this be decidable or partially decidable?

$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?

• 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. – Luke Mathieson Feb 5 '15 at 6:46
• What does "partially decidable" mean? – Andrej Bauer Feb 5 '15 at 7:59
• @AndrejBauer It's yet another name for RE. – Luke Mathieson Feb 5 '15 at 8:07
• Why do we need yet another name for c.e.? Oh well. – 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.