Recently I have been reading about Kolmogorov Complexity. As such I started thinking about the "fastest turing machine". In particular I am not interested in finding such a machine, I am only interested in the time complexity of it. By googling I found the blog, and the definition of the "fastest turing machine" is exactly the same as mine:

Let $L(M) = \{ w \in \Sigma^* | M \text{ accepts } w \}$, $M=$ TM = Turing Machine.

$T_M(n) = \text{ max } \{ t_M(w) | w \in \Sigma^n \}$, where $t_M(w)$ is the computation time of $M$ on $w$.

Fix some universal Turing machine $U$. Then we can define:

$T_U(L,n) := min_M \{ T_M(n) : M \text{ recognizes the language } L \}$ The $min$ is taken with respect to lexicographic ordering of the programs $M$ in the UTM $U$.

This $T_U(L,n)$ measures the time of the fastest Turing machine to recognize words of length $n$ of the language $L$.

Then by definition of $T_U(L,n)$ we have for each TM $M$:

$T_U( L(M), n ) \le T_M(n)$

I was wondering if changing the UTM from $U$ to $V$ will have much impact on $T_U(L,n)$.

I guess that $T_U(L,n) \le c_{UV} \cdot T_V(L,n)$ for some constant $c_{UV}$, which depends solely on $U$ and $V$ and not on $L$ and $n$. The intuition behind it, is the same as in the Kolmogorv Complexity case. First on has an interpreter from $U$ to $V$, than one runs the programs using this interpreter. But how does one make this into a formal proof?

Do you have any idea?

  • $\begingroup$ The blog you link to writes, "Theorem: There is an effective procedure for finding the fastest Turing machine that computes a function f with finite domain. The fastest Turing machine takes just 1 step." This does not sound like sound computer science to me. I have not taken the time to understand your question, but I'm not sure I would trust your source. There's another part where your source says, "Without any limitations on the Turing machine, we can simply construct a Turing machine that computes f in one step - you basically encode f into the transition function of the Turing machine." $\endgroup$ – Philip White Oct 9 '15 at 1:25
  • $\begingroup$ This is quoted without context. The "Theorem" is about encoding a function with finite domain in a simple if domain=b then return f(b) $\endgroup$ – orgesleka Oct 9 '15 at 5:22
  • $\begingroup$ So this is possible in one step if the alphabet is huge enough. In the next "Theorem" the same question is considered with a finite alphabet. I was mainly concerened with the definition of the fastest turing machine: "the fastest turing machine that computes the function f will be the machine that takes the least number of steps for its worst case input", which is a "natural measure" to consider, and which coincides with what I have been thinking about. $\endgroup$ – orgesleka Oct 9 '15 at 5:25
  • $\begingroup$ Ok, I missed the part about "finite domain." $\endgroup$ – Philip White Oct 9 '15 at 22:07

Probably the best one can say at this level of generality is that $T_U(L,n)$ and $T_V(L,n)$ are computably related (if $U$ and $V$ are both universal), i.e. there are computable functions $f,g$ such that $T_U(L,n) \leq f(T_V(L,n))$ and $T_V(L,n) \leq g(T_U(L, n))$. The proof is exactly as you suggest, using an interpreter for one universal TM in the other one.

If one restricts attention to efficiently universal TMs - i.e. a universal TM that can simulate any other TM with only polynomial slow-down (fairly common when studying computational complexity rather than computability) - then the computable functions above are replaceable by polynomials. But that's almost by definition.

Let me also draw your attention to two closely related topics:

  1. Circuit complexity. The circuit complexity of $L$ is very close to your $T_U(L,n)$, since for each $n$ you allow a different TM that decides $L$.

  2. The Speed-Up Theorem. When you don't allow different TMs for $n$ and $n'$, there are languages which have no optimal-running-time TM.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your answer and mentioning circuit complexity and the speed-up theorem. This answer referes to the definition of $T_U(L,n)$ where the fastest worst-case computing time is measured on $U$. But as you pointed out this definition makes one "prefer" unnarturally some UTM over the other, and measures in one UTM are not directly comparable to other UTMs. As such it is better to use the version which does not prefer any UTM over the other. Thanks again for the clarification! $\endgroup$ – orgesleka Oct 11 '15 at 16:17

The statement $T_U(L,n) \le c_{UV} \cdot T_V(L,n)$ is not true for all choices of $U$. It's easy to think of a Universal Turing Machine that is simply inefficient. For example choose $U$ as the Machine that is equivalent to $V$ but does a useless iteration over the input tape between any two steps of $V$. This would result in a slowdown linear in $n$ compared to $V$ and thus no such constant $c_{UV}$ exists.

| cite | improve this answer | |
  • $\begingroup$ Ok, agreed, but does this mean, there is no "connection" at all between the values $T_U(L,n)$ and $T_V(L,n)$? $\endgroup$ – orgesleka Oct 10 '15 at 17:23

One might define $T_U(L,n)$ using $U$ only for the lexicographic ordering of the programs $M$ which could run on $U$ but whose worst case computation time $T_M(n)$ is not measured on $U$ but measured when the TM $M$ runs with the input $x$ of length $|x|=n$. Hence $T_U(L,n) = T_V(L,n)$ for two UTM $U,V$ and as such one might define $T(L,n) := T_U(L,n)$ without mentioning the UTM $U$ at all.

So to clarify: The UTM $U$ is only needed to make clear, that one is able to order every TM $M$ lexicographically as they are parsed in $U$. But once they are ordered, one can choose one $M$ which has the smallest worst case $T_M(n)$, and hence one might define $T(L,n)$ without reference to the UTM $U$.

I agree, that defining $T_U(L,n)$ as the smallest worst case time $T_M(n)$ when run on $U$, then $T_U(L,n)=T_V(L,n)$ is not more valid.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.