0
$\begingroup$

The problem:

Is it decidable that the set of pairs $(M,w)$ such that TM $M$, started with input $w$, never scans any tape cell more than once.

How can I easily prove above to be decidable. I found following proof confusing:

enter image description here

How is $l+m$ is upper bound on number of steps? I feel we should be doing at least $l\times 𝑄\times \Gamma\times\{𝐿,𝑅\}+1$ steps ($Q$ being number of states,$\Gamma$ being set of tape alphabet, $l$ is string length, $L$ and $R$ are head movement directions).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.