# Can there exist a single Turing machine complete for PTIME, or for $\#P_1$?

In "The Complexity of Enumeration and Reliability Problems", Valiant mentions the existence of a single Turing machine that is complete for the class $\#P_1$ (i.e., $\#P$ with unary input). On page 419, he writes:

it is sufficient to simulate just the following fixed TM, $M$, which is clearly complete for $\#P_1$: on unary input $n$, $M$ first verifies that ... and then simulates the $i$th machine in $\#TIME(n)$ on input $j$ (or vice versa)

I find the existence of such a machine surprising:

• Does there exist a machine complete for PTIME that can simulate any other PTIME machine. That is, a PTIME machine that takes a number $i$ and a string $s$ as input, and then executes the $i$th PTIME machine with input $s$?
• Would the existence of such a machine not lead to a contradiction, because it would have a complexity $O(n^k)$, which means that no PTIME machine can have complexity $O(n^{k+1})$.
• If this is indeed not possible for PTIME, why is it possible for $\#P_1$?
• The machine can convert the unary input to binary, and work on it (the input length changes from $|x|$ to $\log |x|$). – Marzio De Biasi Mar 31 '14 at 8:23
• If some machine solves a PTIME-complete problem $Q$ in $O(n^k)$ time, that doesn't mean that every problem $Q'$ in PTIME is also in $DTIME[n^k]$: the reduction of $Q'$ to $Q$ generally increases the size of the instance. – András Salamon Mar 31 '14 at 17:18