13
$\begingroup$

In Sipser's Introduction to the Theory of Computation, the author explains that two strings can be compared by “zigzagging” back and forth between them and “crossing off” one symbol at a time (i.e., replacing them with a symbol such as $x$). This process is displayed in the following figure (from Sipser):

Diagram that shows how a Turing machine can compare two strings

However, this process modifies the strings being compared, which would be problematic if the Turing machine needs to access these strings in the future. What are ways of performing a string comparison without modifying the strings?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
29
$\begingroup$

Create two new types of marks: $\dot{0}, \dot 1$. Those two will act "like" $x$, but can still keep the information about the string.

So when you cross-off a letter, add a "dot" to it at the top instead of fully replacing it with $x$.

Then, if you want the original strings back, after you are done comparing, go through the entire strings and remove the "dots": replace $\dot 0$ with $0$ and $\dot 1$ with $1$.

Improve this answer
$\endgroup$
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$
    – terdon
    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$
    – nir shahar
    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$
    – terdon
    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$
    – nir shahar
    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$
    – dionyziz
    Aug 11, 2021 at 14:08
24
$\begingroup$

One simple way is to create a copy of the entire input right after the original input, if your TM only has a single tape. To distinguish the original from the copy you can use ## as separator. So the first step is to scan the entire input to reach the end, add ##, go back to copy the entire input to the right side of ## and finally apply the comparison used in Sipser to the copy.

Improve this answer
$\endgroup$
12
  • 3
    $\begingroup$ Arguably the better method, because this one doesn't require modification to the Turing Machine's set of allowable symbols, which effectively makes it into a different Turing Machine. $\endgroup$
    – The_Sympathizer
    Aug 10, 2021 at 8:58
  • 3
    $\begingroup$ @The_Sympathizer but it does have the drawback of requiring an additional $O(n)$ space. And anyways it still needs some additional symbol as a "separator". This answer is still very good considering that it is more practical :) $\endgroup$
    – nir shahar
    Aug 10, 2021 at 11:55
  • 6
    $\begingroup$ @nirshahar worrying about space overhead is silly when the topic is Turing machines – they have infinite memory... — If you're going to discuss anything resembling real-world performance, then you should just allow for two registers that can store the positions as addresses, instead of encoding them in unary on the tape. $\endgroup$
    – leftaroundabout
    Aug 10, 2021 at 14:46
  • 3
    $\begingroup$ How does the Turing machine create the copy? I'm wondering about how you indicate where in the input you are while copying -- can this be done without introducing new symbols like @The_Sympathizer says? Maybe you overwrite the symbol you're copying with $\sqcup$? $\endgroup$
    – Kyle Miller
    Aug 10, 2021 at 22:04
  • 2
    $\begingroup$ I accepted the other answer because this answer seems to mask its elegance behind "creating a copy of the input." Like Kyle mentions, I think some kind of marking procedure or some more complicated state representation would be required to actually create a copy. $\endgroup$
    – Frank
    Aug 10, 2021 at 22:42
9
$\begingroup$

Here is an alternative solution using the original binary alphabet of $\{0,1\}$ (without adding extra letters, apart from $x$ which can also be replaced with $\sqcup$), that also manages to work without allocating extra memory from its tape:

We only keep one "$x$" per string, moving it one right for each comparison we did. That being said, to know what letter was there before we replaced it with $x$, we can utilize the fact that its possible to encode it within the turing machine's internal state.

Improve this answer
$\endgroup$
3
$\begingroup$

In general, it can't be done.

E.g., if the strings are length-prefixed, and writing to the cells containing the strings is not allowed, then there is no way that a machine of $n$ internal states can traverse a string longer than $n$ from end to end, and so there is no single program that can compare strings of arbitrary length (or do much of anything with them).

You have to be able to "bring information with you" on the tape, since there isn't enough memory in the internal state space to store anything of interest. Unless the input is encoded in a way that gives you some working space – leaving alternate cells blank, for example – you have no alternative but to rewrite the tape to create space for yourself.

You can always modify the strings in a reversible way, and restore them to their original positions after you've worked out and recorded the answer. But Turing machines aren't normally expected to do that.

Improve this answer
$\endgroup$
1
  • $\begingroup$ What you are saying is interesting. But rather, I also think its an interesting concept to allow one to modify the data however they like, for as long as at the end the modified data is exactly equal to the original data. This allows us to think of the TM as a "black box" that we know what to expect from, and this line of thinking allows us to use such a weird turing machine without worrying too much $\endgroup$
    – nir shahar
    Aug 12, 2021 at 12:46
2
$\begingroup$

You can get along without a copy and without more symbols than used in the strike-out solution - at the cost of increasing the number of states. That is, you only ever have one $x$ per string and (per additional states) keep in mind what was under them, thus allowing you to restore the info upon the next round.

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.