0
$\begingroup$

Is the following problem is decidable? Given a Turing machine M inputs x,y,z does M halts on these 3 instances? Hint: make y and z any two artificial inputs that the program stops with these inputs. My thoughts that this problem is undecidable because Turing machine M inputs X,Y,Z and as M halts on these 3 instances, and the input may loop forever in turing machine. We can never know that it will be accepted or rejected. Turing machine is undecidable even on single instance. I am in the right direction?

$\endgroup$

1 Answer 1

0
$\begingroup$

The key idea, which you mentioned, is to show that this problem is equivalent to the halting problem (on a single input). Suppose you had a decider $D$ for the 3-input problem, and use this to get a decider for the usual halting problem. Since we know that the halting problem is undecidable, our assumption must have been wrong and there is no such $D$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .