If I have a turing machime TM, can I recognize end of input on the tape?

I know that the "end of input" in a turing machine is signaled with a special character, $\sqcup$.

Can I do this -

Let $TM$ be a turing machine.

Until we reach the first $\sqcup$, continue. If we reached $\sqcup$, replace it with a special character - #.

Is it "legal" to that this?


There are many possible input conventions for Turing machines. The one I know has the tape initialized by the input word (in case of a single input) surrounded by blanks, where a blank is a symbol of the tape alphabet that isn't in the input alphabet. The Turing machine treats all tape symbols in the same way, so you can do with them whatever you want.

Other conventions are also possible. For example, we might want to forbid writing blank for some reason. Only you know which convention is used in your class. The various input conventions are mostly equivalent, so in practice it usually doesn't matter which one is used.

  • $\begingroup$ Thank you! In that sense, can I make a reduction for $EQ_{TM}$ problem with that sense? Let's say I assume that $EQ_{LBA}$ is decidable, can I find the end of input in $EQ_{TM}$, run $EQ_{LBA}$ and "decide" $EQ_{TM}$? In that method, I prove that $EQ_{LBA}$ is undecidable. @Yuval Filmus $\endgroup$ – Alan Jul 6 '18 at 13:45
  • $\begingroup$ This seems like a new question. $\endgroup$ – Yuval Filmus Jul 6 '18 at 13:46
  • $\begingroup$ OK, I will post a new one shortly. $\endgroup$ – Alan Jul 6 '18 at 13:47

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.