I am currently reading the paper On the computational complexity of Algorithms by J. Hartmanis and R. E. Stearns ( http://www.jstor.org/pss/1994208 )It includes a proof that any $T$-computable sequence is also $\lceil kT \rceil$-computable, where $k$ is a computable, positive real number, $T$ a time-function and $\lceil kT \rceil$ denotes the smallest integer $m$ such that $m \ge kT$.The proof idea is to use a (multitape) TM that has a head that can read 2 symbols at once, while storing internally the symbol to the left and right of that head, so that the new TM can simulate 2 steps of a normal (multitape) TM in only once step. By doing the same trick on the new TM using induction, one can prove 1/2k speed-up. I have two questions, which revolve around the same thing: First of all, can I extend this idea and use a head so large that reads the entire input at once? That would require to save a super-constant number of symbols internally in the TM. Would that be a violation of the model?Reflecting to my first question, whatever the answer is : Are there complexity classes that restraint the TM's control logic somehow? e.g. allowing up to a specific number of states or for a specific structure of the automaton?
Is there such a thing as control logic complexity classes?
cc.complexity theory;complexity classes
One should be careful about having a head that large. If your tape head can read the entire input, then technically speaking all inputs can be decided in one step. This is because making a head so large you can read the input is formally equivalent to making the tape alphabet so large that it contains all input strings. But if this is the case then your entire function can be encoded in the transition table of the Turing machine, so every input can be decided in one step. It makes perfect sense to have a superconstant number of symbols in the TM, but when you do that you are no longer talking about uniform computation (fixed-size programs) but rather non-uniform computation, where the size of the program can grow with the input length. In complexity theory, non-uniform computation is typically studied in the language of circuit complexity: having a polynomial-size Boolean circuit family for solving a problem is equivalent to having a polynomial-size transition table for solving a problem with a polynomial-time TM, and the general feeling is that circuits are more natural to reason about. But it's possible that the TM perspective could be useful too.Allowing a specific number of states or specific structure probably will not change the definitions of the standard complexity classes. This is because there are universal Turing machines which have a small number of states and/or simple structures in the transition table, which can simulate arbitrary Turing machines with polynomial time overhead. (Sorry, don't have references at the moment.) Restricting yourself to these machines does not change the overall difficulty, up to polynomials in the running time.