Fastest Turing Machine

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.