1
$\begingroup$

I am trying to find the following:$$ \text{For a given TM M with initial empty tape is it possible to decide whether there} $$ $$\text{exists a constant K such that the head of M remains within the first K slots?} $$

I thought this was possible if you know $K$, since you could add the current configuration to a separate tape and understand whether the machine is looping or not as there exists finitely many configurations with length $K$. But what if you don't know this number? Is it still possible to find a TM that decides this language or is there a reduction from another undecidable language?

Any help will be appreciated.

$\endgroup$
1
$\begingroup$

Hint: Given a Turing machine $M$, you can construct another Turing machine $M'$ with the following properties:

  1. If $M$ halts then $M'$ halts.
  2. If $M$ doesn't halt then the head of $M'$ eventually reaches the $K$th square from the right for every $K$.

This construction can be used to show that the halting problem reduces to your problem.

As you mention, given $K$, your property is decidable. This shows that your problem is $\Sigma_1$-complete.

$\endgroup$

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.