1
$\begingroup$

We know that checking whether some word w is accepted by a turing machine TM is undecidable. But what about the problem of finding one accepting word of a TM?

Are these two problems related in some way, i.e. undecidability of one implies the undecidability of other (in any structure, like FA, LBA, PDA etc)?

My hunch is that they are not related but I am not able to argue why?

$\endgroup$
1
  • 3
    $\begingroup$ Finding an accepted word is not a decision problem, so you can't immediately compare the two problems. The decision problem "Is there an accepted word?" is undecidable as well, and both are semi-decidable. Is that what you are after? $\endgroup$
    – Raphael
    Jul 6, 2015 at 11:43

1 Answer 1

2
$\begingroup$

The two problems are Turing equivalent: one is undecidable for Turing machines iff the other is.

Deciding whether a Turing machine (TM) $M$ halts on a specific input $x$ is the Halting problem for Turing machines.

Given a TM $M$, we want to know whether it halts on some word. From $M$ we build a TM $M^*$ that, independently of its input, dovetails the computation of $M$ over all inputs (i.e. it mimics the computation of $M$ on all possible inputs in parallel), and halts iff one of these computations halts. If we had an oracle $H$ that decided the halting problem, it could decide whether $M*$ halts or not, hence whether the TM $M$ halts on some input. This is only for the decision on the existence of that input, but the same dovetailing construction could then be used to compute the halting input when it is known to exist. Hence we could build a TM that always halts, either with a word on which $M$ halts if there is one, or with failure when there is none.

Hence, if the halting problem were decidable, the problem of deciding whether a TM halts on some input, and determining that input wold be decidable too.

Conversely, let us assume that it is decidable whether a TM halt on some input. Then given a Turing machine $M$ and and input $x$ we want to decide whether $M(x)$ halts (the halting problem for $M$ on input $x$). For this we build a machine $M'$ that, independently of its input, will simply mimic the machine $M$ running on input $x$. Hence the machine $M'$ halts on some input (thus on any input) iff $M$ halts on input $x$. Hence we have a decision procedure for the halting problem if we have a decision procedure for halting on some input.

Both problems are Turing reducible to each other. Hence they are Turing equivalent. If one were to be decidable, the other would be too. Or, to take the contrapositive, the undecidability of one implies the undecidability of the other.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.