2
$\begingroup$

Why is a Language L(M) {has at least 10 strings} recognizable and L(N) {has at most 10 strings} is not?

{⟨𝑀⟩:𝐿(𝑀) has at least 10 strings}

{⟨N⟩:𝐿(N) has at most 10 strings} 

My proof (I dont know if I'm wrong)

L(N) => I could think of a turing machine that takes as an input 10 strings of the language and accept them, if the turing machine accepts them then it's turing recognizable but not turing decidable (given Rice's Theorem)

But I can't figure it out a proof for L(M) even though I know it's undecidable also fro Rice's Theorem

Please, If I'm doing something wrong also on L(N) reasoning, let me know

$\endgroup$
4
  • $\begingroup$ Welcome! Your language definitions are not written quite correctly. Do you mean the language $\{\langle M \rangle : L(M) \text{ has at least 10 strings}\}$? $\endgroup$ Dec 13, 2021 at 20:46
  • $\begingroup$ A language has to be a set of strings, so you have to specify what strings are in the language -- in this case, the strings are descriptions of Turing machines $\endgroup$ Dec 13, 2021 at 20:47
  • $\begingroup$ Sorry for the mistake, your notation is correct! I will edit my question $\endgroup$
    – karalis1
    Dec 13, 2021 at 20:52
  • $\begingroup$ Looks better, thanks for the edit. $\endgroup$ Dec 13, 2021 at 20:55

2 Answers 2

2
$\begingroup$

Let $S_\ge = \{\langle M \rangle \mid |L(M)| \ge 10\}$. You can prove that it is Turing-recognizable by applying the definition directly. The following algorithm terminates on machines in $S_\ge$ and runs forever on machines that are not in $S_\ge$:

  • For $k = 0,1,2,\ldots$:
    • Let $c := 0$
    • For every string $w$ of length at most $k$:
      • Run $M$ on the input $w$ for at most $k$ steps. If $M$ halts, increment $c$.
      • Terminate if $c$ reaches $10$.

If this algorithm terminates on a machine $M$, then it has run $M$ on 10 string on which $M$ terminates. Conversely, if $M$ is in $S_\ge$, then take 10 strings that it accepts, let $k_1$ be their maximum length and let $k_2$ be the maximum number of steps that it takes to accept one of them; the algorithm above terminates with $k \le \max\{k_1, k_2\}$.

This algorithm only proves recognizability, not decidability, since it'll go on forever on machines that don't accept at least 10 strings. This doesn't prove that $S_\ge$ is not Turing-decidable: there could be another algorithm that works. A straightforward application of Rice's theorem does prove that $S_\ge$ is not Turing-decidable.

Now let's look at $S_\le = \{\langle M\rangle \mid |L(M)| \le 10\}$. Note that $S\le \cup S_\ge$ is Turing-decidable: it's the set of all machines. And $S_\le \cap S_\ge = \{\langle M\rangle \mid |L(M)| = 10\}$ is not Turing-decidable, by Rice's theorem.

If $S_\le$ was Turing-recognizable, then $S_\ge \cap S_\le$ would be Turing-decidable by the following algorithm:

  • Run the recognizer for $S_\le$ and the recognizer for $S_\ge$ in parallel, doing one step of each at a time. Terminate if one of the two terminates.

Since every input is recognized by one of the two recognizers, this process terminates on all inputs, so $S_\ge \cap S_\le$ is decidable. But we saw abov that it isn't. So $S_\le$ cannot be Turing-recognizable and $S_\ge$ is not Turing-decidable.

$\endgroup$
1
  • $\begingroup$ So in principle, if it recognises 10 strings then you know it recognises at least 10 strings. If you only find 9 strings then you can never know that there isn't another string lurking around that it would recognise. $\endgroup$
    – gnasher729
    Nov 24, 2023 at 15:47
1
$\begingroup$

I had to dig a little bit because 2nd Rice's Theorem wasn't included in my lectures

I proved this example using 2nd Rice's Theorem on Language N:

given 2 Turing Machines N1 and N2, N1 exists for L(N1) = Ø and N2 exists for L(M2) = Σ* . since L(N1) ⊂ L(N2) then the language N is not turing recognizable

Given that it's easy to prove that the complement (M) is turing recognizable

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.