Let TOT be the set of all Turing Machines that halt on all inputs. Find a computable set B of ordered triples such that:

TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B]

This definition means that TOT is a set of all Turing machines e such that they halt on all inputs. The "for all" x denotes all inputs to that machine, and "there exists" a y denotes that e halts under y steps. x consists of 0s and 1s, y and e are Natural numbers too ( e denotes Turing machine $T_e$ if we were to number all our turing machines)


  • $\begingroup$ What do $e$, $x$, and $y$ represent? I guess that $e$ is a Turing machine, to be coherent with the definition of TOT. What is $x$ and what is $y$? $\endgroup$ – Steven May 10 '20 at 15:32
  • $\begingroup$ The definition of TOT is clear to me. From your comment, I get that $x$ belongs to $\{0,1\}^*$. It is still not clear the set to which $y$ belongs to. Is it an integer? A word in \{0, 1\}^*? The condition "Turing machine e halts under y steps" does not appear at all in your problem statement... $\endgroup$ – Steven May 10 '20 at 15:45

Let $T$ be the set of all Turing machines.

Let $B = \{ (e,x, y) \in T \times \{0,1\}^* \times \mathbb{N} : e(x) \text{ halts in $y$ steps}\}$, and define $C = \{e \in T : \forall x \in \{0,1\}^*, \; \exists y \in \mathbb{N}, \; (e, x, y) \in B]$.

We start by proving $\text{TOT}=C$.

If $e \in \text{TOT}$ then, $\forall x \in \{0,1\}^*$, $e(x)$ halts. Let $y_x$ be the number of steps needed for $e(x)$ to halt. Then $ \forall x \in \{0,1\}^*$ there is a choice of $y \in \mathbb{N}$, namely $y = y_x$, such that $(e,x,y) \in B$, showing that $e \in C$ and hence $\text{TOT} \subseteq C$.

If $e \not\in \text{TOT}$, then $\exists x \in \{0,1\}^*$ such that $e(x)$ does not halt. Then $\exists x$, such that $\forall y \in \mathbb{N}$, $(e, x, y) \not\in B$, showing that if is false that $\forall x \in \{0,1\}^*, \exists y \in \mathbb{N}$ such that $(e, x, y) \in B$. As a consequence $e \not\in C$ implying $\text{TOT} \supseteq C$.

It remains to show that $B$ is computable. To decide whether any given triple $(e, x,y) \in T \times \{0,1\}^* \times \mathbb{N}$ belongs to $B$ it suffices to consider a Turing machine $T'$ that simulates $e(x)$ for $y$ steps. If $e(x)$ halts, then $T'$ accepts. Otherwise, if $e(x)$ does not halt by the end of the $y$-th step, $T'$ rejects.


Your Answer

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