1
$\begingroup$

I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language

$$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has 101 as a prefix} \}. $$

I have made an attempt at showing decidability of $L$:

On input $\langle M, w\rangle$ (where $M$ is a TM and $w \in \sigma^*$):

  1. Simulate $M$ on $w$.
  2. If $M$ rejects and halts, reject. If $M$ accepts and halts, accept.

However, I'm not sure about moving forward after this. I do not want a solution, but I want some ideas/techniques as to what else I can prove about $L$.

$\endgroup$
3
$\begingroup$

First, it should be intuitive that L is not decidable. Decidable means that you can can tell in finite amount of time if a word (in this case, coding of turing machine) is in L. In m opinion, this should be one of the first things that should come in mind while solving these kinds of questions.

Note that there are infinitely many string that have $101$ as prefix (for example $101, 1011, 10111$, or in general, $101^i$ for $ i \geq 1$).

There are several problems with your solution. First, the input for a TM for $L$ is $\langle M\rangle$, and not $\langle M, w\rangle$. Second, what happens if $M$ doesn't halt on $w$? Your TM for $L$ also doesn't halt, and hence can't decide $L$.

You can show that $ L \in RE\setminus R $.

Show that $L \in RE $ by describing a TM $M'$ that recognizes $L$ (meaning, on input $\langle M\rangle$, if $ \langle M\rangle \in L$ then $M'$ accepts $\langle M\rangle$, otherwise $M'$ rejects or doesn't halt.

An easy way to show that $L\notin R$ is a reduction $f$ from the halting problem $HP$ to $L$, such that if $\langle M,w\rangle \in HP$ , then $f(\langle M,w\rangle) \in L$ (Hint: $f(\langle M,w\rangle)$ we accept any input if and only if $M$ stops on $w$).

$\endgroup$
  • $\begingroup$ Please mention that $HP$ is the halting problem. It could also be useful to single out a specific variant of the halting problem. $\endgroup$ – Yuval Filmus Mar 31 '14 at 22:35
2
$\begingroup$

Hint: It is undecidable whether a given Turing machine accepts the empty string, or any other fixed string for that matter. Given a Turing machine, we can come up with a different Turing machine that rejects immediately if the input is not (say) $101$, and otherwise simulates the original Turing machine. What does that imply?

$\endgroup$
  • $\begingroup$ I don't think I can immediately reject if the input is not 101, since M can accept other strings (but does not have to). All we know is that it does accept some string that starts with 101. $\endgroup$ – Bob Mar 31 '14 at 21:53
  • $\begingroup$ Well, the hint is aimed at showing that $L$ is not decidable. $\endgroup$ – Yuval Filmus Mar 31 '14 at 22:07
0
$\begingroup$

According to $Rice's$ $theorem$,

$\qquad$ $L$ = { $\langle M \rangle$ | $L (M) ∈ P$ } is undecidable if $P$ is a non-trivial semantic property of $\qquad$$L(M)$.

$\qquad$ P is the set of all languages that satisfies a particular property

If the following two properties hold, it is proved as undecidable −

Property 1 (Semantic) − If $M_1$ and $M_2$ recognize the same language, then either $\qquad$$\qquad$$\langle M_1 \rangle ,\langle M_2\rangle \in L$ or $\langle M_1 \rangle ,\langle M_2\rangle \notin L$.

Property 2 (Non-trivial) − There exists $M_1$ and $M_2$ such that $\langle M_1 \rangle \notin L$ and $\langle M_2 \rangle \notin L$.

Now,

$\quad$ 1) For any two TMs, $M_1$ and $M_2$ with $L(M_1) = L(M_2)$ either both $M_1$ and $M_2$ both accept all strings starting with 101 or both don't accept.

$\quad$ 2) There exists TMs that accepts strings starting with 101 and not accepting strings that starts with 101.

Therefore, the property of the language of a TM to start with 101 is a semantic and non-trivial. Hence, according to Rice's theorem, the given language is undecidable.

$L$ is recognizable as TMs that accepts when given as input strings starting with 101 always accepts and halts. But complement of $L$ isn't recognizable as both $L$ and complement of $L$ being recognizable will mean that $L$ is decidable(why?).

$\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.