1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There is no such machine. Objection 1: Diagonalization considerations. You have defined $D$ so that it dominates all other machines in the sense you have specified. But using $D$ you can define another $E$ which strictly dominates $D$ in the same way, e.g. by simulating $D$ and then filling the tape with 10 times as much garbage-data. Objection 2: Halting Problem considerations. Depending on how we fill in some details in your specification, such a $D$ will either compute the Halting Problem, or be of $\mathit{high_1}$ Turing degree, neither of which is possible for a Turing machine. $\endgroup$ – realdonaldtrump Aug 22 '18 at 8:04
  • $\begingroup$ @realdonaldtrump: Regarding Objection 1 — doesn't simulating $D$ require some number of additional states for $E$? But in this case, $E$ is not a competitor for $D$ because the number of states in the program for $E$ is greater than the number of states in the program for $D$. $\endgroup$ – lyrically wicked Aug 22 '18 at 8:36
  • $\begingroup$ Your description is quite hard to decipher. You define a concept of "$F$-different" but never use it for anything. Why do you introduce the names $a$ and $b$ rather than just writing $F(D,B)\ge F(K,B)$? And the condition $K\ne D$ is immaterial. It looks like you could just say $$\text{for all but finitely many $B$: }\forall K:|K|\le|D| \to F(D,B)\ge F(K,B)$$ and save half of your variables. $\endgroup$ – Henning Makholm Aug 22 '18 at 10:57
  • 1
    $\begingroup$ @lyrically_wicked, oh, I had missed the significance of $z$. Is your question really: Is there for each $n$ an $n$-state total Turing machine that dominates all $n$-state total Turing machines? Here 'total' means it terminates on every input. If this is your question it is an interesting one, and I am as yet unsure as to the answer. $\endgroup$ – realdonaldtrump Aug 22 '18 at 18:01
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.