Is this language recognizable (Turing machines)

formal-languagesturing-machines

$L = \{ \langle M \rangle \mid \text{ M is a TM, M accepts some string of length 3 \}}$ Is this language recognizable? A string is $\Sigma = \{0, 1\}$.

my attempt to prove its recognizable:

let $w_1, w_2, w_3, \dots$ be an effective enumeration of $\Sigma^*$ where $\Sigma$ is the input alphabet. We give a TM R recognizes $L$

R = "On input <M>
    for s = 1 to infinity
        for i = 1 to s
            run M on w_i for s steps
            if M accepts w_i within s steps then
                if len(w_i) == 3 then accept

I don't know if this is correct. My confusion is I don't know if we can use input alphabet method. I used input alphabet method to try and exhaust the number of strings but we limited the length to 3 so I think it would be better if we chose a enumerator of TM description. Not sure

Best Answer

1) R = "On input <M>
2) for s = 1 to infinity
3)    for each string w of length 3
4)        run M on w for s steps
5)        if M accepts w within s steps then
6)            accept

You are using a "dove tailing" technique.
Note that there are only 8 possible strings of length 3.
So, the loop in line 3 is guaranteed to terminate.
In addition, if M accepts w, it must do so in a finite number of steps s.
So, the loop in line 1 is also guaranteed to terminate if M accepts w.

However, M may possibly loop if it does not accept any string of length 3.

Related Question