# Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?

Say I'm given an oracle that tells me whether or not $$L(M)$$, the set of words accepted by a Turing Machine $$M$$, is finite.

By leveraging this oracle, can I solve the halting problem? That is, on an arbitrary input $$$$, can I tell if M is going to halt on $$x$$ or will it loop forever?

My intuition says no because I don't see a way to leverage the oracle. For example, even with a stronger oracle that tells me if $$x \in L(M)$$, I still don't know, for inputs $$x \notin L(M)$$, how $$M$$ is going to behave. It could either reject (and halt), or loop forever.

Hence, I can't seem to solve the problem even with a stronger oracle that computes $$L(M)$$ explicitly in case it's finite. So, I believe merely knowing $$L(M)$$ is finite or not doesn't lead to a solution for the halting problem.

Is my reasoning correct, or am I overlooking something here?

• I would not judge "your reasoning" or "your intuition" as correct or wrong, since it is rather vague. Please see my answer that provides correct reasoning and answers, from which you may draw better intuitions. Mar 15 at 6:54

Yes, with such a powerful oracle, the halting problem can be solved.

To be clearer, given an arbitrary Turing machine, the oracle will tell the set of words accepted by that Turing machine is finite or not.

Suppose we are given a Turing machine $$M$$ and an input $$x$$. Let us construct Turing machine $$M'$$ such that on all inputs, $$M'$$ will simulate $$M$$ running with input $$x$$. Furthermore, when the simulation of $$M$$ halts (because $$M$$ halts on $$x$$), $$M'$$ will accept, regardless of whether $$M$$ accepts or rejects.

Note that $$M'$$ either always accepts or always runs forever. Now let us apply the oracle to $$M'$$.

• If the oracle says $$L(M')$$ is not finite, it implies $$M'$$ always accepts. That means $$M$$ halts on $$x$$.

• If the oracle says $$L(M')$$ is finite, it implies $$M'$$ always runs forever. That means $$M$$ on $$x$$ runs forever.

So, we have solved the halting problem on $$(M,x)$$, thanks to the oracle.

Here is a similar question, which might be the question intended by the OP as well.

Suppose (without any oracle) we are given an arbitrary Turing machine $$M$$ that accepts only finitely many words and an arbitrary word $$x$$, can we decide whether $$M$$ will halt on $$x$$?

For a pair of Turing machine and input $$(M,x)$$, we construct Turing machine $$M'$$, which checks if its input is $$x$$. If yes, it will run as $$M$$; otherwise, it will loop forever. Since $$M'$$ accepts at most 1 word, our assumption says that we can decide whether $$M'$$ on $$x$$ will halt or not. But that is exactly the same as whether $$M$$ halts on $$x$$ or not.
• The end behavior of $M'$ is the same, independent of its input. More specifically, given any arbitrary word as input, $M'$ will first erase that input completely, and then write $x$ at the place where it expects input, and then run in the same way as $M$ would run with $x$ as input. Mar 15 at 23:13
• A better notation for $M'$ could be $M_x$ or $T_{M,x}$. Mar 15 at 23:19