Is it possible to assume the existence of “Dominating Turing Machines”?

Question

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?

Answer 1

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

• $B= (2A+1)2^D > A$
• $F(K,B) = F(M, B) = 2\cdot F(g(B), B) = 2\cdot F(D, B)$

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

Answer 2

I can tell you that if Dominating machines exist, at most they have 14 states. Checking all small machines for a property as complicated as yours will be too laborious without some idea for why it is important or interesting.

Let's look at a concept of Universal Turing machine. There is 2-symbol, 1-tape Universal Turing machine with 15 states. For 3-tape machine number of states might be fewer. Universal machine simulates a machine encoded in its input until halting. That means your function $F(u,y)$ for Universal machine #u would have two key properties:

1. There are infinitely many numbers $y$ such that $F(u,y)=0$, as there are infinitely many non-halting machines.
2. Define function $G(Y)=max_{y\leq Y}(F(u,y))$. $G(Y)$ grows on the order of Busy Beaver numbers.

Any machine with property (1) cannot dominate a simple machine that always outputs a single 1, and so cannot be Dominating. Any machine that has property (2) should also have property (1), otherwise it can be used to solve Halting problem. Any machine that dominates #u should have property (2), therefore it should have property (1), therefore it cannot be Dominating. And if it doesn't dominate #u, it obviously cannot be Dominating either.

Therefore any Dominating machine must have fewer states than smallest Universal machine for your particular model of computation, which cannot be more than 15.