1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why oh why oh why are educators continually reinventing the terminology of recursion theory? I think "decidable" and "recognisable" here mean what has traditionally been called "recursive" and "recursively enumerable". The effort involved in finding that out has nearly drained away all my enthusiasm for answering this MSE question. $\endgroup$ – Rob Arthan Apr 18 '18 at 22:44
  • $\begingroup$ Our reference book in class is Sipser so this is the terminology I'm used to but I see your point, why reinvent the wheel? $\endgroup$ – Vinamra Misra Apr 18 '18 at 22:50
  • $\begingroup$ @VinamaraMisra: thanks for letting us know what the source was. My enthusiasm didn't quite all drain away - I hope my answer helps $\ddot{\smile}$. $\endgroup$ – Rob Arthan Apr 18 '18 at 22:56
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.