A unary Turing Machine X has input alphabet Σ and tape alphabet Γ. We represent the blank symbol belonging to the tape alphabet as _ . Given as input 11111 X writes 1_1_11_1 as output.

Is the blank symbol discarded when considering the output, ie. is the input equivalent to the output in this case (regardless of how many blanks and where they are placed (1_11_11 = 1111_1 = ... = 11111)) or are they differnt?

  • 2
    $\begingroup$ $1\_11\_11$, $1111\_1$ and $11111$ are different words over the alphabet $\{1,\_\}$. $\endgroup$ – plop Sep 2 at 18:36
  • 1
    $\begingroup$ @plop The blank symbol is not part of the input alphabet, {1} (unary in this case). Blank symbol is only part of tape alphabet. $\endgroup$ – DeeDee Sep 2 at 18:55
  • 1
    $\begingroup$ @plop This is my point of confusion. Is the "output alphabet" equivalent to the tape alphabet or to the input alphabet? Do we get rid of all the blanks before reading out output or do we take them into consideration and the output includes the blanks and their placement? $\endgroup$ – DeeDee Sep 2 at 20:16
  • 1
    $\begingroup$ Words with different characters in some position are different. Whether one interpret some different words are equivalent according to some equivalence relation is up to whoever it using the Turing machine. The machine (the concept not a particular instance) doesn't have any notion of identification of words. The point of saying that the input is a word in the alphabet that excludes the blank character is just a way of saying that the input is a finite part of the (potentially) infinite tape. $\endgroup$ – plop Sep 2 at 20:25
  • 2
    $\begingroup$ It is not part of the Turing machine what you do with what is written in the tape, how you interpret it. $\endgroup$ – plop Sep 2 at 20:26

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.