2
$\begingroup$

Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$ Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm?

My attempt:

I wanted to study reachability the same way one does with DFA/NFA. However although a transition might be defined between $q_i$ and $q_j$ for $ x \in \Gamma $ is no guarantee that the configuration is possible.

$\endgroup$
1
$\begingroup$

I will use the following definition of $L(M)$: it is the set of inputs for which $M$ halts.

I will use the following definition of recognizable: a language $L$ is recognizable if there exists a Turing machine $M$ such that $L = L(M)$.

In order to recognize $L_1$, on input $\langle M \rangle$, we simulate $M$ on all possible inputs (using dovetailing), and if $M$ halts on any input, we halt.

In order to simulate $M$ on all possible inputs, we list all possible inputs in a sequence $x_1,x_2,\ldots$, and then work as follows:

  • Initiate a run of $M$ on $x_1$, and advance it one step.
  • Initiate a run of $M$ on $x_2$, and advance both existing runs by one step each.
  • Initiate a run of $M$ on $x_3$, and advance all three existing runs by one step each.
  • And so on.

If $M$ halts on any input, then we will eventually notice it, and then immediately halt. Conversely, if $M$ never halts, then we will also never halt.

$\endgroup$
1
$\begingroup$

Reachability is unlikely to work. For a DFA/NFA, there are only finitely many states to consider but, for a Turing machine, there are infinitely many possible configurations of the tape and state.

Instead, you need to simulate the machine you're interested in on possible inputs and see if it accepts any of them. In principle, you'd want to try each possible input in order (e.g., $\epsilon$, $0$, $1$, $00$, $01$, $10$, $11$, $000$, ...) but there's a problem with this. If the machine doesn't halt on some input, you'll never begin to consider the next input. You get around this with a technique known as "dovetailing". You simulate your machine running for one step on the first input. If that's enough to work out the answer, you're done. Otherwise, you simulate the machine running for two steps on each of the first two inputs. If that's not enough, three steps on the first three inputs, and so on.

I'll leave it to you to check that this technique really works and to use it to answer 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.