I am trying to show that this is Turing Recognizable.

The language A, that is a DTM, T, that halts on a minimum of one input.

My justification is that of course it is because, you just need to check if an accept state is reachable. However, this seems like I am making it trivial.

Is there something larger I am missing?

EDIT: New Idea

Let M be a DTM that does this:

For every string w in the language, simulate w on T. if it halts, accept.

The only problem I see with this, is if a string causes it to loop forever, then it will never try the others.

  • $\begingroup$ How do you propose to check reachability? In, e.g., a DFA, you just have to check reachability in the state graph, which is guaranteed to be finite. But the state graph of a Turing machine is potentially infinite, since the state includes the whole contents of the tape. $\endgroup$ – David Richerby Jul 1 '15 at 19:43
  • $\begingroup$ Oh, I see. That makes sense. I had another thought that doesn't stand on this idea. $\endgroup$ – csonq Jul 1 '15 at 19:48
  • 2
    $\begingroup$ You're almost there, now. You just need to use the technique known as "dovetailing". $\endgroup$ – David Richerby Jul 1 '15 at 21:08
  • 1
    $\begingroup$ Regarding your last question, what happend if a string causes the TM to loop forever, Imagine a real life situation. For example, you need a loan from a bank, anyone of the many banks in town. But they do not always answer when the loan is rejected. What do you do? $\endgroup$ – babou Jul 1 '15 at 21:45
  • 1
    $\begingroup$ What I would do is ask all the banks at the same time, and take the loan from the first that answers. Turing machines are very much like banks. The technique is called "dovetailing" as @DavidRicherby already told you. $\endgroup$ – babou Jul 2 '15 at 0:42

Hint: Use the technique of dovetailing, mentioned in several of the comments. The idea is to maintain a growing list of simulated Turing machines, all of them copies $T_1,T_2,\ldots$ of the input Turing machine $T$, operating as follows:

  1. Initialize $T_1$ with the $1$st possible input, and run $T_1$ for one step.

  2. Initialize $T_2$ with the $2$nd possible input, and run $T_1$ and $T_2$ for one step each.

  3. Initialize $T_3$ with the $3$rd possible input, and run $T_1,T_2,T_3$ for one step each.

  4. And so on.

You get the idea. It is perhaps not obvious how to maintain the states of several Turing machines at once, but you can figure it out on your own.

  • $\begingroup$ Why would you only run them for one step each? $\endgroup$ – csonq Jul 2 '15 at 1:41
  • $\begingroup$ EDIT: I see that you are moving the previous ones by one as well. So it is moving them all forward. Thank you. $\endgroup$ – csonq Jul 2 '15 at 1:49
  • $\begingroup$ You don't have to move them one step forward, it's completely arbitrary. In fact, for some purposes (such as Levin's optimal algorithm) you should use a more sophisticated regime. $\endgroup$ – Yuval Filmus Jul 2 '15 at 4:14

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.