Checking acceptance of a word vs finding an accepted word

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?

• 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? Jul 6, 2015 at 11:43

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