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.

  • 1
    $\begingroup$ There are countably infinite deciders ( and there are countably infinite TM ). So if your set S is not the deciders still there would be countably infinite machine descriptions in the set at best. How will you compare the sizes of two countably infinite sets ? $\endgroup$ Nov 19, 2015 at 3:47
  • $\begingroup$ @sasha Sorry, I mean maximal in the sense that there is no larger containing set, not in that it is of maximal size. I edited this into the question. $\endgroup$ Nov 19, 2015 at 3:49

2 Answers 2


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.

  • $\begingroup$ Ah, sure, I suppose that works. Maybe I'll ask a new question once I figure out what I'm actually looking for. $\endgroup$ Nov 19, 2015 at 4:16
  • $\begingroup$ But again when you say bigger , the previous problem arises. $\endgroup$ Nov 19, 2015 at 4:17
  • $\begingroup$ Yes, indeed! Anyway I think the idea of this answer may help create more general answers. $\endgroup$ Nov 19, 2015 at 4:18

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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