Turing Machines can be used to compute functions.

For example f(x)=x-1.

0011 is on the tape. Turing Machine computes for some time and finishes in accept state. On the tape, we see: _00_10_. Where _ is a blank symbol. Is it correct? Meaning 0011 == _00_10_.

For exaple in Python: [] + [1] + [] + [2] + [] == [1,2] is True.

When Turing Machine is used for recognizing language everything is clear. It is not important what is on the tape. Only final state: accept or reject.

  • 1
    $\begingroup$ You might want to check this: Why is the blank symbol not considered part of the input alphabet of a turing machine $\endgroup$
    – Russel
    Jan 26, 2023 at 15:57
  • $\begingroup$ As I understand the blank is used to detect the end of its input. It does not tell how to use it when Turing Machine is used as a function. $\endgroup$
    – Oleg Dats
    Jan 26, 2023 at 16:04
  • $\begingroup$ In your example you are using the blank symbol as part of your input to a TM, which the link I provided, would show that this should not be the case. If you need to use the blank as a delimiter or to represent an empty collection or null, then the way to go is not to use the blank tape symbol but instead use some encoding based solely on the available input symbols. $\endgroup$
    – Russel
    Jan 26, 2023 at 16:56
  • $\begingroup$ The blank symbol is not a part of my input. Input is 0011 and output is _00_10_ $\endgroup$
    – Oleg Dats
    Jan 26, 2023 at 17:02


Your Answer

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

Browse other questions tagged or ask your own question.