Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

8
  • 1
    $\begingroup$ Wouldn't that require keeping some form of array that links 0˙ to 0? Is that any different to just using different symbols, where 0 maps to y and 1 maps to h or anything else? $\endgroup$ Commented Aug 10, 2021 at 10:57
  • 2
    $\begingroup$ You can use any two distinct symbols you will like, for as long as you know what was mapped from $0$ and what from $1$. The symbols $\dot 0$ and $\dot 1$ are just for the sake of convenience. $\endgroup$ Commented Aug 10, 2021 at 11:53
  • 2
    $\begingroup$ Yes, of course. I am just trying to understand how this is different to just making a copy of the string and operating on that copy. Is there any benefit in using an associative array-like structure (I assume that's how this would have to be implemented) instead of making a copy? Also, I am a biologist and wouldn't know a Turing machine if it bit me on the nose, so I could just be missing something blindingly obvious here. $\endgroup$ Commented Aug 10, 2021 at 11:57
  • 5
    $\begingroup$ This is by no means an "associative array-like structure". The only thing we do here is replace $0$ by a different letter $\dot 0$ in-place (we don't create extra memory for it, we replace the existing memory), so we would know that we have seen it already. Turing machines, in the formal world have some alphabet they operate on. This alphabet doesn't necessarily have to be the binary one, and the solution I proposed uses a $4$ letter alphabet: $\{0,1,\dot 0,\dot 1\}$. This was done for the sake of convenience, so it would be easier to implement $\endgroup$ Commented Aug 10, 2021 at 12:01
  • 3
    $\begingroup$ @terdon You don't need an associative array, no. The code of the Turing machine itself (i.e., its transition function) knows how to make these replacements. They are hardcoded. If you were writing this in a normal programming language, there would literally be an "if c == '$\dot{0}$' then set c = '0' else if c == '$\dot{1}$' then set c = '1'". There is just a 0 and 1, no more. So all of them can be literally in the code. $\endgroup$ Commented Aug 11, 2021 at 14:08