Csdrhrt

Given a TM $M$ that halts on all inputs, and a general string $w$, consider the most trivial algorithm (Call it $A$) to decide whether $M$ accepts $w$:

$A$ simply simulates $M$ on $w$ and answer what $M$ answers.

The question here is, can this be proven to be the fastest algorithm to do the job?

(I mean, it's quite clear there could not be a faster one. Or could it?)

And more formally and clear:

Is there an algorithm $A'$, that for every input $langle M,wrangle$ satisfies:

1. If $M$ is a TM that halts on all inputs, $A'$ will return what $M$ returns with input $w$.




2. $A'$ is faster than $A$.

Is there an algorithm $A′$, that for every input $langle M,wrangle$ satisfies:

1) If $M$ is a TM that halts on all inputs, $A′$ will return what $M$ returns with input $w$.

2) $A′$ is faster than $A$ (In worst case terms)

It's not possible to be asymptotically faster by more than a log factor. By the time hierarchy theorem, for any reasonable function $f$, there are problems that can be solved in $f(n)$ steps that cannot be solved in $o(f(n)/log n)$ steps.

Other answers point out that you can get faster by any constant factor by the linear speedup theorem which, roughly speaking, simulates a factor of $c$ faster by simulating $c$ steps of the Turing machine's operation at once.

Dkaeae brought up a very useful trick in the comments: the Linear Speedup Theorem. Effectively, it says:

For any positive $k$, there's a mechanical transformation you can do to any Turing machine, which makes it run $k$ times faster.

(There's a bit more to it than that, but that's not really relevant here. Wikipedia has more details.)

So I propose the following family of algorithms (with hyperparameter $k$):

def decide(M, w):

    use the Linear Speedup Theorem to turn M into M', which is k times faster

    run M' on w and return the result

You can make this as fast as you want by increasing $k$: there's theoretically no limit on this. No matter how fast it runs, you can always make it faster by just making $k$ bigger.

This is why time complexity is always given in asymptotic terms (big-O and all that): constant factors are extremely easy to add and remove, so they don't really tell us anything useful about the algorithm itself. If you have an algorithm that runs in $n^5+C$ time, I can turn that into $frac{1}{1,000,000} n^5+C$, but it'll still end up slower than $1,000,000n+C$ for large enough $n$.

P.S. You might be wondering, "what's the catch?" The answer is, the Linear Speedup construction makes a machine with more states and a more convoluted instruction set. But that doesn't matter when you're talking about time complexity.

Of course there is.

Consider, for instance, a TM $T$ which reads its entire input (of length $n$) $10^{100n}$ times and then accepts. Then the TM $T'$ which instantly accepts any input is at least $10^{100n}$ times faster than any (step for step) simulation of $T$. (You may replace $10^{100n}$ with your favorite largest computable number.)

Hence, the following algorithm $A'$ would do it:

1. Check whether $langle M rangle = langle T rangle$. If so, then set $langle M rangle$ to $langle T' rangle$; otherwise, leave $langle M rangle$ intact.


2. Do what $A$ does.

It is easy to see $A'$ will now be $10^{100n}$ faster than $A$ if given $langle T, w rangle$ as input. This qualifies as a (strict) asymptotic improvement since there are infinitely many values for $w$. $A'$ only needs $O(n)$ extra steps (in step 1) before doing what $A$ does, but $A$ takes $Omega(n)$ time anyway (because it necessarily reads its entire input at least once), so $A'$ is asymptotically just as fast as $A$ on all other inputs.

The above construction provides an improvement for one particular TM (i.e., $T$) but can be extended to be faster than $A$ for infinitely many TMs. This can be done, for instance, by defining a series $T_k$ of TMs with a parameter $k$ such that $T_k$ reads its entire input $k^{100n}$ times and accepts. The description of $T_k$ can be made such that it is recognizable by $A'$ in $O(n)$ time, as above (imagine, for instance, $langle T_k rangle$ being the exact same piece of code where $k$ is declared as a constant).