New answers tagged

0

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


Top 50 recent answers are included