World's most popular travel blog for travel bloggers.

[Solved]: Are two strings equal if all deciders for a language take the same amount of time for both?

, , No Comments
Problem Detail: 

Let $X_*^L$ be the set of all deterministic Turing machines $M$ which decide the language $L$ and have the property:

$\forall x,y \in \Sigma^*: t_M(xy) \ge t_M(x) + t_M(y)$ (**)

where $t_M(w)$ is the time of $M$ on input $w$.

Define for all $x,y\in \Sigma^*$:

$d(x,y) := \max_{M \in X_*^L} \frac{|t_M(x) - t_M(y)|}{t_M(xy)+t_M(yx)}$

Then, because of (**) we have $t_M(yx) + t_M(xy) \ge 2(t_M(x)+t_M(y))$ from which it follows that: $\frac{|t_M(x) - t_M(y)|}{t_M(xy) + t_M(yx)} \le 1/2 \frac{|t_M(x)-t_M(y)|}{t_M(x) + t_M(y)} \le 1/2 \frac{ |t_M(x)| + |t_M(y)|}{t_M(x) + t_M(y)} = \frac{1}{2}$ Hence we get $d(x,y) \le 1/2$.

My question is this:

Does $d(x,y) = 0$ which is equivalent to $\forall M \in X_*^L: t_M(x) = t_M(y)$ imply that $x = y$?

The reason for asking this question, is that I am trying to define a metric on strings which has "something to do with the time-complexity of Turing machines". If we define $d(x,y) = \max_{M \in X^L} |t_M(x) - t_M(y)|$ (where the maximum is taken over all machines which decide $L$.). Then I can show, that $d(x,y) = 0$ implies $x = y$. But the problem with this definition, is that $d(x,y)$ can be $\infty$. Or am I wrong with this?

Asked By : stackExchangeUser

Answered By : Raphael

Your "distance" $d(x,y)$ is never zero for distinct, non-trivial $x$ and $y$.

Let $M$ be a decider for $L$ and $x,y \in \Sigma^*$ with $\varepsilon \neq x \neq y$. Let furthermore $T = 1 + \max \{ t_M(x), t_M(y) \}$. Now we construct a machine $M'$ like this:

M'(z) {   if x == z or xy is a prefix of z     wait for T steps   return M(z) } 

We observe that $t_{M'}(x) - t_{M'}(y) \geq T > 0$ since $x \neq y$. Condition (**) is satisfied by increasing the running-time on all inputs that begin with $xy$ as well; hence, $M' \in X^L_*$ and thus $d(x,y) > 0$.

This constructions works for all pairs of distinct $x$ and $y$, proving the claim. Your claim follows since trivially $d(x,x) = 0$ for all $x$.

I think the problem is that $d(x,y)$ is not well-defined. With a similar construction as above, we can increase the difference between $t_M(x)$ and $t_M(y)$ by an additional $i$ for all $i \in \mathbb{N}$. Since the sum of $t_M(xy)$ and $t_M(yx)$ grows with $i$ as well (unless either is $\varepsilon$), $d(x,y)$ approaches a constant for $i \to \infty$ and the maxium does not exist.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback