Classify language as decidable, undecidable but recognisable or unrecognizable

Question

I'm currently studying unrecognizable languages in Turing Machines and came across this problem

L1 := {< M > | M is a TM and M accepts at least one string w in {0,1}* with more zeros than ones}

I can't seem to understand whether this would be unrecognizable or simply Turing undecidable since for inputs 0000 and 00 I think it would be in the same state but for inputs 0000w and 00w where w = 111, the first one should be accepted while the second one should not.

Answer 1

In the traditional terminology, your set of Turing machines $L_1$ is recursively enumerable (r.e.) (i.e., there is a Turing machine that will terminate iff its input is a member of the set) but not recursive (i.e., there is no Turing machine that will terminate on any input and give a yes or no answer as to whether the input belongs to the set). I think this means recognisable but not decidable in the terminology your textbook uses.

It's not recursive by Rice's theorem. It's r.e., because you can simulate parallel execution of a Turing machine $M$ on all possible strings with more zeros than ones in such a way that if $M$ does terminate on one such string, the simulation will terminate.

Answer 2

Your observation on the state a Turing machine should be in after reading $0000$ or $00$ suggests that you are concerned with the status of the language

$$L_0 = \{ w \in \{0,1\}^* \mid w \text{ contains more $0$s than $1$s}\} \enspace.$$

In fact, $L_0$ is context-free because it is accepted by a (deterministic) push-down automaton. One such PDA would be in the same state after reading $0000$ and $00$. However, the stack contents would be different in the two cases.

Language $L_1$, on the other hand, consists of strings encoding the Turing machines that accept at least one string with more $0$s than $1$s. The fact that $L_0$ is decidable (or recursive) has little bearing on whether $L_1$ is recursive. In fact, $L_1$ is only recursively enumerable (as noted by @RobArthan).

If you've gotten far enough in Sipser to read about nonrecognizable languages, you should have come across the observation that the complement of a language that is r.e., but not recursive, is not r.e.. Hence the complement of $L_1$ is a Turing-unrecognizable language.