Set of Turing machines $S$ such that any $A \in S$ halts on input the description of any $B \in S$

Question

Does there exist a maximal set of Turing machines $S$ over the alphabet $\{0,1\}$ such that any $A \in S$ halts on input the description of any $B \in S$?

Take S to be the set of deciders. Then S satisfies the property, but is not maximal, because for example we can take:

• The set of TMs which are not equal to 0 and which halt on input any string not equal to 0. (Assuming 0 is not a deciding TM.)

• Where $A$ is any set of non-deciding Turing machines, the set of TMs which are not in $A$ and halt on input any string not in $A$.

Maybe we can construct such a set $S$ by infinite recursion or by Zorn's lemma, but I haven't been able to see how.

Edit: By maximal, I mean there is no $S' \supsetneq S$ satisfying this property.

Answer 1

Let us construct a Turing machine $M$ such that $M$ first generates its own description $\langle M \rangle$ by recursion theorem. Then for any input $w$ it first checks if $w=\langle M \rangle$, if yes it halts. If not it starts counting infinitely. Now let $S=\{\langle M \rangle\}$. If you try to add any other Turing machine $T$ to $S$ , it could not be part of $S$ as $M$ won't halt on $\langle T \rangle$. Thus following your definition of a maximal set, $S=\{\langle M \rangle\}$ is such a set.

Answer 2

I'm not sure why I thought Zorn's lemma doesn't work, because it does, easily, and gives a stronger result than just a single example. Let's say that a set of Turing machines $S$ is self-deciding if, for any $A, B \in S$, $A$ halts on input $\langle B \rangle$. Then I claim that any self-deciding set $S$ can be extended to a maximal self-deciding set $S' \supseteq S$. (Since $\varnothing$ is self-deciding, this also shows at least one such set exists.)

Proof. Fix $S$. Let $\mathcal{A}$ be the collection of self-deciding sets containing $S$. $\mathcal{A}$ is partially ordered by inclusion (nothing to prove there). To apply Zorn, we need that any maximal chain has an upper bound. So take a chain $\mathcal{T} \subseteq \mathcal{A}$ and, as is usual, we just need to show that $\cup \mathcal{T} \in \mathcal{A}$. Fix $A, B \in \cup \mathcal{T}$. Then there exists $S \in \mathcal{T}$ such that $A, B \in S$, and since $S$ is self-deciding, $A$ halts on $\langle B \rangle$.