2
$\begingroup$

I have a Turing Machine M with a binary alphabet {1,2} that accepts a language L(M) that has infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to determine if L(M) is decidable, semi-decidable (computably enumerable) or undecidable.

Using Rice's Theorem, I believe I can prove that L(M) is not decidable:

P is the property of a language where the language has infinitely many strings that start with one symbol and finitely many strings that start with another symbol. P is non-trivial and is a property of languages of TMs. Therefore, according to Rice's Theorem, M = {⟨M⟩∣L(M) has has infinitely many strings that start with 1 and finitely many strings that start with 2 and Σ = {1,2}} is undecidable.

But I'm struggling to prove whether it's semi-decidable or completely undecidable. This post mentions using an Generalized Rice's Theorem to prove that a language is recursively enumerable (aka semi-decidable) but I'm having trouble understanding their approach.

Can anyone shed some light on this approach and/or if I'm heading down the right path? Many thanks in advance.

$\endgroup$
  • $\begingroup$ You don't have a Turing machine $M$. In fact, you're interested in the language $L$ of (descriptions of) Turing machines $M$ that accept infinitely many strings starting with 1 and finitely many strings starting with 2. This is not what you wrote. You're not after $L(M)$. You're after $L$. $\endgroup$ – Yuval Filmus Jan 5 '15 at 8:59
  • $\begingroup$ Have you tried applying the generalized Rice's theorem? Did you get stuck? The generalized Rice's theorem is not so complicated, I suggest you try it out. $\endgroup$ – Yuval Filmus Jan 5 '15 at 9:00
  • 2
    $\begingroup$ Also, Rice's theorem cannot be used to prove decidability (at least not directly). It shows that the given language is undecidable or even not r.e. $\endgroup$ – Yuval Filmus Jan 5 '15 at 9:01
1
$\begingroup$

I'm going to ignore the second half of your post, and answer the question that appears at the first half. If this is not what you meant - post another question or edit as necessary.

Given a machine $M$ we define $L(M)$ to be the language recognized by that machine. In other words, $L(M)$ is the set of all the words $w\in \Sigma^*$ such that $M$ accepts $w$.

Thus, by its definition $L(M)$ is at least semi-decidable (because $M$ is accepting it!!)

To clarify whether $L(M)$ is decidable or semi-decidable(but not fully decidable), we need more information on $M$.

For instance, it can be that $M$ is the trivial machine that immediately go to the accepting state. In that case $L(M)=\Sigma^*$ (all the possible words), and $L(M)$ is decidable.

On the other hand it can be that $M$ does the following:

1. it ignores the first symbol of the input
2. it runs HP on the rest of the input

where HP is the machine that accepts the Halting Problem language. It is not too difficult to see that in this case $L(M)$ cannot be fully decidable (or otherwise the halting problem will be decidable), but, as said above, it is semi-decidable by definition (that is, it is in $RE\setminus R$).



Now, if you don't care about a specific machine $M$, but instead about all the machines that accept infinitely many words that begin with 1 and infinitely many words that begin with 2, the language that contain all such machines cannot be decidable due to Rice's theorem.

Just to be clear on the statement: let $S \subset RE$ be all the languages that contain infinitely many words that start with 1 as well as infinitely words that start with 2, then

$$L_S = \{ \langle M \rangle \mid L(M) \in S \}$$ cannot be decidable, $L_S\notin R$. Note that $L_S$ contains all the (encodings of) machines that satisfy the property $S$ defined in your question.

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