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