HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
suchhaltsthedescriptionanyinputthatmachinesturingset

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#49667, answer score: 3

Revisions (0)

No revisions yet.