Show that checking if a TM accepts some input string of length greater than some constant $k$ is undecidable. Here the constant $k$ is publicly known.

I tried solving this problem by trying to reduce the "Acceptance Problem" i.e. the problem where we have to check whether a TM $M$ accepts a string $w$ or not.

One idea I had was that we can modify the input $M$ to $M'$ such that $M'$ simply increases the length of the string to become greater than $k$ but that is wrong since by input we strictly mean what was provided and any thing that the TM does cannot be considered as part of the input.

How can I solve this?


So the question is, for a particular constant $k$, is there a TM which decides on input $\langle M_i \rangle$ whether there exists a string $w$ with $|w|\geq k$ such that $M_i$ halts on input $w$? Your reduction is almost correct, let me show you: Suppose that this problem is decidable, then the acceptance problem is decidable.

If the problem is decidable, then if you wanted to know whether TM $A$ accepts $w$, you could build a machine that accepts $1^kw$ only if $A$ accepts $w$, and accepts no other string, and then you would ask your question about that Turing Machine. Let me say this with more detail.

Let $BT$ (for Banach Tarski) be the Turing Machine that decides the problem you describe, and suppose we want to know whether some TM $A$ halts on input $w$ with $|w|<k$. Then we construct a TM $H_{A,w}$ as follows: $H_{A,w}$ checks whether the input is $1^kw$, i.e. $w$ padded at the beginning with $k$ ones (so $w$ is "hard-coded" into this machine). If not, it stops. If the input is $1^kw$, then it moves to the first symbol of $w$ and simulates $A$. Does $H_{A,w}$ accept any input longer than $k$? If so, then it accepts $1^kw$, because that is the only string it could possibly accept. If it accepts $1^kw$, then $A$ accepts $w$, because we were simulating $A$ on $w$. If it accepts $1^kw$, then you could ask $BT$ the question you describe about $H_{a,w}$, i.e. run $BT$ with input $H_{A,w}$. If it returns yes, then $A$ accepts $w$. If not, not.

We have now provided a reduction from the Acceptance Problem to your problem. But we know that the Acceptance Problem is undecidable! So it cannot be that your problem is decidable, because then the Acceptance Problem would be decidable. $\square$

  • 1
    $\begingroup$ Not a problem. It was a nice opportunity for myself to polish my reduction skills: the first proof I wanted to post was wrong! $\endgroup$ – Lieuwe Vinkhuijzen May 1 '16 at 20:15

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.