tomtom2357 wrote:My question is: Is there an algorithm that, given the original turing machine, can find a macro machine (it does not have to be optimal or anything like that) that groups n symbols (n is also given) in the way mentioned above, and speeds up the simulation of the turing machine?
Yes. Your recipe for a maco machine that groups blocks of n symbols wouldn't be hard to formalize. As you say, take a Turing machine T and create a new Turing machine T' which simulates T with a speedup factor of roughly n. The tape symbols are strings of n original symbols, the Turing machine states are pairs (original Turing machine state, L/R), together with a "loop" state, where the symbol L or R indicates whether the simulated T is reading the leftmost or rightmost cell of the current string, and the transition functions take the machine T' to a state simulating where T would be when it first leaves the current n-cell string and enters a neighboring string (or, if it loops infinitely within the current n-cell string, it enters the loop state, and gets stuck there). It wouldn't exactly be a factor of n speedup, because it can take more or fewer than n steps between T entering a strip of n cells coded by a single cell of T' and leaving that strip. But it takes at least n steps between entering and leaving if it didn't leave on the same side that it entered, so I think you can prove that if n is sufficiently large, you can make the speedup factor arbitrarily large (assuming T halts).
However, as mfb says, an arbitrary constant speedup factor doesn't get you very far, if you need to have a Turing machine which is 213
times as complicated to get a speedup factor of 13. What would be nice is a machine which is faster by more than just a constant, which computes the same function as the original Turing machine, but where the time or space complexity is lower. This is what mfb was driving at:
mfb wrote:The square root? This would be an exceptional speedup by a factor of 1028177. Now it is >1028177.
A logarithmic reduction would help, but how do you get this?
However, while this may be possible for some machines, it is not possible in general, by the time hierarchy theorem
. By arguments similar to the proof of the time hierarchy theorem, there's no general procedure which tells you whether a Turing machine can be replaced by a significantly asymptotically faster Turing machine, and no general procedure for finding one if it exists. Here, "significantly asymptotically faster" should be about the same as the bound in the Time hierarchy theorem.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson