Consider three-tape (tape $1$ for the input, tape $2$ for the computation, tape $3$ for the output) two-symbol (blank symbol and non-blank symbol) Turing machines.
Let $F(x, y)$ denote the minimal natural number greater than number of non-blank cells on the output tape when machine #$x$ halts given $y$ as the input in unary encoding ($0$ = “$1$”, $1$ = “$11$”, $2$ = “$111$” etc.), where $x$ is the natural number that identifies the corresponding Turing machine. For clarity, we assume that if machine #$x$ does not halt on $y$, then $F(x, y) = 0$.
Now we can note that each Turing machine #$i$ corresponds to a particular infinite sequence of natural numbers: $$S_i = (F(i, 0), F(i, 1), F(i, 2), \ldots).$$
Then we can define that two Turing machines #$p$ and #$q$ are $F$-different if the sequence $S_p$ differs from the sequence $S_q$.
The Dominating machine is defined as any $Z$-state Turing machine #$D$ such that there exist some minimal natural number $A$ and if you choose any natural number $B \geq A$, denote $F(D, B)$ by $a$, then choose any natural number $K$ that corresponds to any $z$-state machine (where $z \leq Z$ and $K \neq D$) and denote $F(K, B)$ by $b$, you will always observe that $a \geq b$.
Do such machines exist? If no, then why? If yes, then let $V$ denote the minimal number of states in the table of instructions of the first Dominating machine. Can we assume that if we choose any number $W$ from the set $\{V+1, V+2, \ldots\}$ and explore all $W$-state Turing machines, then $W$ will correspond to its own family of Dominating machines (assuming that the family contains at least one Dominating machine) and any Dominating machine from this family is $F$-different from any $(W-1)$-state Dominating machine?
Best Answer
A one-state machine whose single state is terminal will vacuously be "dominating" according to your definition, because no other machine of the same (or smaller) size can terminate at all.
There may be other machines of small sizes that are dominating, but as Ivan argues, the size of the smallest universal machine bounds how large a dominating machine can be, so there are only finitely many of them.
A streamlining of his argument, which avoids the slight handwaving about orders of growth: Because we know how to construct universal machines we can find a machine $\#M$ with the property $$ F(M,x) = 2\cdot F(g(x),x) $$ for all $x$, where $g(x)$ is the highest power of $2$ that divides $x$.
This $\#M$ will need a few more states than 14, to account for duplicating the input, computing $g(x)$, and doubling the output if it terminates, but by all accounts it will be small.
Now suppose someone claims they have a particular $\#M$ with at least as many states as $\#D$ that is dominating. They will be wrong: First ask for their $A$, and then give them $B=(2A+1)2^D$ and $K=M$. Since
this will work as a counterexample to $\#D$ being dominating, unless $F(D, B)=0$. But if it is $0$ then we can instead let $K$ be the number of the one-state machine that always halts immediately.
With a bit more care we can get back to the 14ish states of a plain universal machine, by moving complexity from the operation of $M$ into how we construct $B$ as a function of $D$ and $A$.