0
$\begingroup$

$L=\{\langle M \rangle \mid \text{There are infinitely many words accepted by M in less than 10 moves}\}$

I am having hard time understanding this language and I have several questions:

  1. How is it possible to derive infinite amount of words in finite moves?

  2. How can we determine if a word is or isn't in the language at all?

  3. Why is this language decidable? I understand that it is because it halts on every input, but what are we looking for after 10 moves to decide if it will reject or accept?

Any further clarifications on this language will be highly appreciated.

$\endgroup$
2
$\begingroup$

I'm going to assume that you mean

$\qquad L = \{ \langle M \rangle \mid |L_{\leq 10}(M)| = \infty \}$

with $L_{\leq m}(M)$ the set of words that $M$ accepts after at most $m$ steps. In particular, it does not say a thing about all the other inputs.

  1. How is it possible to derive infinite amount of words in finite moves?

    The Turing machine that does nothing but accept clearly accepts an infinite language. While it's true that machines that qualify for $L$ have to work with finite prefixes, but they can accept arbitrarily many inputs based on these prefixes!

  2. How can we determine if a word is or isn't in the language at all?

    I don't know what "we" is here; but clearly, we can just run $M$ on the input. If it accepts after at most ten steps, fine; otherwise, it's not relevant for the criterion of $L$.

  3. Why is this language decidable?

    Who says so?

    Hint: How many symbols of the input can any TM examine in ten steps? Let's call this number $k$. What does it tell you if it accepts or rejects an input of length at most $k$? What does it tell you if it accepts or rejects an input of length greater than $k$?

    I understand that it is because it halts on every input.

    How so? If you had an algorithm that decides $L$, then yes, it would halt on every input. But we can not assume that -- that's the claim we have to prove!

    The inputs for this algorithm are all Turing machines, in particular also such that don't halt.

    but what are we looking for after 10 moves to decide if it will reject or accept?

    You have one bit of information: did the machine accept or not? You can have some more, if that helps: did the machine visit a state twice? Did it move, and how?

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