Complete problems and universal simulator machines I'm trying to get straight in my mind the relation between complete problems and universal simulator machines.  Some notions of computability have universal machines (Turing-computability) and some don't (FDAs).   

When we say that there are $\mathsf{NP}$-complete problems (to take an example) is this the same as saying that a polynomially hampered universal Turing machine is universal for the notion of polytime-computability?  

My colleague Ashley Montanaro here (who kindly told me about this site) told me once that the class of $\mathsf{DSPACE}(o(\log\log n))$ problems is the same as the class of regular languages.   Does this mean that there is no universal machine for the $\mathsf{DSPACE}(o(\log\log n))$ problems?
There is a universal simulator for $\mathsf{DSPACE}(o(\log \log n)) = \mathsf{DSPACE}(O(1))=\mathsf{REG}$. Namely, $U_{REG}(p,x)$ treats the first input $p$ as the description of a DFA, and then runs that DFA on input $x$. The universal simulator, however, is not itself in $\mathsf{DSPACE}(o(\log \log n))$---the $U_{REG}$ I just described uses space essentially $O(p)$---so I don't know about complete languages in this case.

More generally, complete problems and universal simulators are related, but not equivalent. For one, a universal simulator for a class $\mathcal{C}$ need not be (and in general won't be) in the class $\mathcal{C}$ itself, as in the above example. Your example of "polynomially-hampered universal TMs" for $\mathsf{P}$ exhibits this distinction even better: let $M_1, M_2, \dotsc$ be an enumeration of poly-time TMs, where $M_i$ is hampered to use time at most, say, $n^i + i$. Then let $U(i,x) = M_i(x)$. $U$ is a universal simulator for $\mathsf{P}$, but there is no single polynomial that bounds the runtime of $U$, so $U$ itself is not in $\mathsf{P}$ and hence not complete. 

Furthermore, there cannot be a single polynomial that bounds the runtime of a universal simulator for $\mathsf{P}$: if the universal simulator ran in time $n^k$, it would never be able to decide a language which required more time, say, $n^{k+1}$. We know that such languages exist by the Time Hierarchy Theorem.

However, the other direction usually holds. That is, if a class has a complete language under essentially any of the natural types of reductions, then it has a universal simulator. As an example, consider $\mathsf{NP}$ and its standard complete language SAT. Then we construct a universal machine for $\mathsf{NP}$ as follows (we knew how to do this for $\mathsf{NP}$ already using polynomially-hampered nondeterministic machines, but you'll see how this construction generalizes to any class with a complete language). $U(i,x) = SAT(M_i(x))$ where $M_i$ is the $i$-th poly-time deterministic TM, as above. Here we are using the $M_i$ to list out the possible reductions to the complete language, rather than the deciders of languages themselves.