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).


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.