HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMajor

How can a Turing machine compare two strings without modifying them?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canwithouthowmodifyingtwothemmachineturingcomparestrings

Problem

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):

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?

Solution

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$.

Context

StackExchange Computer Science Q#143026, answer score: 29

Revisions (0)

No revisions yet.