1
$\begingroup$

Is it possible to construct a Turing Machine such that given any finite input on a tape $s$, it clears the tape in a finite amount of time?

I have used such a TM as an intermediate step to show a reduction from the State Entry Problem to is $w \in L(M)$ problem but I don't know if it is feasible to construct one.

Even if we assume that the head of the TM always starts at the leftmost character on the tape and keep moving write, clearing each symbol we encounter, if the tape is infinite, how will we know when to stop moving right?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ when the head reaches a special symbol say #. Initially tape of Turing machine is infinite cells each with symbol #. When a finite input is written on tape # denotes end of input. $\endgroup$
    – advocateofnone
    May 1, 2016 at 13:40
  • $\begingroup$ In other words, the input alphabet excludes the special character, so starting at the leftmost character on the tape and moving right, as soon as you see a special character you know you've reached the end of the input $\endgroup$
    – Rick Decker
    May 1, 2016 at 18:11

1 Answer 1

Reset to default
2
$\begingroup$

While the tape is infinite, the amount of characters written on it is finite at any given point in time.

As sasha indicates in their comment, we usually assume that the tape is initialized with a special blank character. Given a Turing machine, you can modify it so that whenever it visit a cell having the special blank character, it replaces it with some other blank character, which it treats the same as the special blank character. Now at any given point in time you can find the (finite) extent of tape which has been visited, and clear it if you wish.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.