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?

  • $\begingroup$ $L$ may be undecidable (or there may exist no machines meeting the property) so $d$ is not properly defined for all $L$. $\endgroup$ Aug 2 '16 at 10:11
  • $\begingroup$ I should say that $L$ is always decidable, otherwise it makes no sense to talk about the time of the machine deciding $L$. $\endgroup$
    – user41014
    Aug 2 '16 at 10:13
  • $\begingroup$ Also to every dTM $M$ which decides $L$, there exists an equivalent dTM $M'$, with the property $t_M(xy) \ge t_M(x) + t_M(y)$. See here : cs.stackexchange.com/questions/60952/… $\endgroup$
    – user41014
    Aug 2 '16 at 10:19

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.

  • $\begingroup$ @stackExchangeUser That can be worked around, for instance by making the machine do a idle loop of length $n^3$ (where $n$ is the input size), which means the property is satisfied even if you spend $n$ time checking for equality with $x$. You don't need to wait for the full $T$ steps, just long enough to make the running time different of that for $y$. $\endgroup$ Aug 2 '16 at 10:14
  • $\begingroup$ @stackExchangeUser I believe your derivation, but I also believe my intuition. The $1$ may be wrong, but I still think you can give an infinite sequence of machines in $X^L_*$ with continuously growing values; they would have to approach $1/2$ or some other constant. Please let me know if you can either refute this, or ar able to expand my sketch into a full proof! $\endgroup$
    – Raphael
    Aug 3 '16 at 13:02
  • $\begingroup$ @Raphael: The "real" problem with the definition of the "distance" is that there is nor reason why it would fullfill the triangle inequlity, at least I can see none: $d(x,z) \le d(x,y)+d(y,z)$. Your intuition might be right, that would say that $d(x,y) = 1/2$ for all $x \neq y$, which make the "distance" trivial. Thanks for your help, I will accept your answer! $\endgroup$
    – user41014
    Aug 3 '16 at 13:08
  • $\begingroup$ @stackExchangeUser We have not talked about whether you get a metric out at all; well-definedness is a more rudimentary problem. (That would be like talking about the running-time of an algorithm that does not terminate.) No, what I write does not imply the distance is 1/2 as you write; "the maximum does not exist" is worse. You would need to use the supremum in your definition, which you have already shown to exist (but we don't know that it's 1/2!). $\endgroup$
    – Raphael
    Aug 3 '16 at 13:12

Raphael's answer explains why $d$ as defined doesn't work. You stated that you want a metric, ideally. To explain why you will have trouble defining it with any kind of max/min relating running time: for every string x in L, there is a machine that first reads in the input, checks if it is x, and if so immediately returns; otherwise it resorts to some "standard" machine's algorithm. Thus, for every x, there is a machine that checks x in linear time.

It is possible to define a metric in runtime on languages, instead of strings. For instance, dividing them into classes such as P, (NP-P), and (Decidable-NP), we can define a metric between two languages that is 1 if they belong to the same class, or 2 otherwise. This of course can be generalized to any number of runtime classes, and this discusses the minimum (over machines) of the supremum (over strings in the language) of runtime, as compared to input length. This gets around the "hard code a given string" problem.

If you really want a metric for strings relevant to their position in the language, min and max clearly don't work, so you must use some type of averaging. This will require defining a measure over machines of interest, or somehow weighting the machines based on their runtimes on other inputs. However, all the constructions I could think of for this would end up very sensitive to the particulars of the construction of Turing machines, or vulnerable to similar "hard coded answer" problems.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy