patternMinor
Fastest algorithm to decide whether a (always halting) TM accepts a general string
Viewed 0 times
acceptsalwayshaltinggeneralalgorithmdecidefastestwhetherstring
Problem
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,w\rangle$ satisfies:
-
If $M$ is a TM that halts on all inputs, $A'$ will return what $M$ returns with input $w$.
-
$A'$ is faster than $A$.
$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,w\rangle$ satisfies:
-
If $M$ is a TM that halts on all inputs, $A'$ will return what $M$ returns with input $w$.
-
$A'$ is faster than $A$.
Solution
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$):
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.
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 resultYou 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.
Code Snippets
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 resultContext
StackExchange Computer Science Q#106329, answer score: 4
Revisions (0)
No revisions yet.