Is there such a thing as control logic complexity classes?

Question

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/2^k speed-up.

I have two questions, which revolve around the same thing:

1. 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?

2. 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?

Answer 1

1. 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.

2. 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.

Answer 2

After thinking about the first part of my question, I realised that any gain we have by increasing the head size is nullified by the time needed to perform every step. So if we use a head of logarithmic size, we will need logarithmic time steps. This argument can be made clear if one tries to simulate the two TMs with a universal TM.

The "speed-up lemma" that I mentioned before can bypass this difficulty, since it achieves only constant improvement, therefore it can be simulated by a universal TM with each step being executed in O(1) time. Equivalently, one can use a larger alphabet (which still is constant as required by the model). Using an alphabet whose size depends on the input size would result in non-uniformity.