patternMinor
Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?
Viewed 0 times
problemcanfinitetheknowhaltingsolvemachineturinggiven
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#136651, answer score: 6
Revisions (0)
No revisions yet.