3
$\begingroup$

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 $<M, x>$, 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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – John L. Mar 15 at 6:54
6
$\begingroup$

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$?

The answer is no.

Otherwise, we can solve the original halting problem in the following way, which is known to be impossible.

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.

$\endgroup$
6
  • $\begingroup$ Thanks a lot for your detailed answer. This is a follow-up question, might be a bit naive but here it is: how do we conclude that M' always accepts given L(M') is infinite? Couldn't M' loop on some inputs, and yet have infinite L(M') ? $\endgroup$ – SpiderRico Mar 15 at 22:20
  • $\begingroup$ 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. $\endgroup$ – John L. Mar 15 at 23:13
  • $\begingroup$ A better notation for $M'$ could be $M_x$ or $T_{M,x}$. $\endgroup$ – John L. Mar 15 at 23:19
  • $\begingroup$ I see. So, whether M' accepts an arbitrary input y purely depends on whether M halts on input x. So, if M' is of infinite length, then it must be that M halts on x. Because, it's going to either accept everything in case M halts on x, or will loop forever, and hence not accept anything in case M loops on x. $\endgroup$ – SpiderRico Mar 15 at 23:27
  • $\begingroup$ You said it better than me. $\endgroup$ – John L. Mar 15 at 23:29

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.