A language $S$ is called Turing recognizable if for some Turing machine $S$ is exactly the set of inputs when the machine halts. How can we call the language which is the set of outputs for some Turing machine? How are these two classes related?
Analogue of Turing recognizable languages
computabilityformal-languagesturing-machines
Related Solutions
To decide whether a string is in the union of two recursive (= Turing decidable) languages $A$ and $B$, you (or an algorithm) can first check whether it's in $A$ and then, if necessary, check whether it's in $B$. In the case of recursively enumerable (= Turing recognizable) languages, that won't work, because, if your string isn't in $A$, then the "check whether it's in $A$" part will run forever and you'll never get around to checking whether it's in $B$.
Whenever you approach one of these problems, the first thing to do is what Rogers calls a Tarski-Kuratowski computation: find the level of the arithmetical hierarchy where the set in question lives. In this case, we have that $e \in \text{Tot}$ if for every $n$ there exists an $s$ with $\phi_{e,s}(n)\downarrow$ (that is, $\phi_e(n)$ halts in $s$ steps). Therefore Tot is $\Pi^0_2$ and its complement is $\Sigma^0_2$.
So how can we diagonalize against Tot to show it is not computably enumerable? Well, we can use the leading $\forall$ quantifier in its definition, and the fact that the halting set $K$ is already $\Sigma^0_1$, to show that if Tot was $\Sigma^0_1$ then the halting set would be computable. Recall that, in general, a set is computable if both it and its complement are $\Sigma^0_1$, which is equivalent to the set and its complement both being $\Pi^0_1$.
Let $e$ be given. We want to tell whether $e \in K$, that is, whether $\phi_e(0)$ halts. Let $g$ be such that $g(s) = 0$ if $\phi_{e,s}(0)\uparrow$ and $g(s)$ diverges if $\phi_{e,s}(0)\downarrow$. Notice that $g$ is a partial computable function, and $g$ is total if and only if $\phi_e(0)\uparrow$, and we can compute an index $\gamma_e$ for $g$ uniformly from an index $e$. Therefore, we have $$ e \in K \leftrightarrow (\exists s)[\phi_{e,s}(0) \downarrow]\\ e \not \in K \leftrightarrow \gamma_e \in \text{Tot} $$ So, if Tot was computably enumerable, the two facts there the would show that $K$ is computable, which is impossible. The method here was to leverage the $\forall$ quantifier in Tot; if we had a way to decide membership in Tot, that gives us a "free pass" to decide that universal quantifier. The definition of $\gamma_e$ leverages the universal quantifier to tell whether $\phi_e(0)$ does not halt.
How can we show that Tot is not $\Pi^0_1$? Well, we can use the inner $\exists$ quantifier in the definition of Tot, and the fact that the complement $\bar K$ of the halting problem is not computable. In the first part we used Tot to tell whether $\phi_e(0)\uparrow$. Now we will use Tot to tell whether $\phi_e(0)\downarrow$. Given $e$, let $h(x) = \mu s [\phi_{e,s}(0) \downarrow]$. Then $h$ is total if and only if $\phi_e(0)\downarrow$, which is equivalent to $e \not \in \bar K$. Also, we can compute an index $\eta(e)$ for $h$ uniformly from $e$. Thus: $$ e \in \bar K \leftrightarrow (\forall s)[\phi_{e,s}(0)\uparrow]\\ e \not \in \bar K \leftrightarrow \eta(e) \in \text{Tot} $$ Therefore, if $\text{Tot}$ was $\Pi^0_1$ then $\bar K$ would be computable, which is impossible.
Best Answer
Any language "generated" by a Turing machine that always halts the way you mentioned (i.e., $s\in S$ iff $T(x)=s$ for some input $x$ to the fixed Turing machine $T$) will be Turing recognisable.
The way to recognise the language $S$ is to use the Turing machine which does the following:
Machine A: Turing machine to recognise the language $S=\{s\mid \exists x : T(x)=s\}$, where $T$ always halts
If $s\in S$, then the above machine will eventually halt and accept when it comes to a string $x$ such that $T(x)=s$; if $s\notin S$ then this machine will run forever.
Nonempty Turing recognisable languages can also be "generated" by a Turing machine in this way too. Suppose $S$ is a language recognised by the Turing machine $T$ that is nonempty, so that we have some known element $s_0\in S$, then consider the following algorithm:
Machine B: Turing machine which always halts to generate the nonempty language $S\ni s_0$ recognised by $T$
The language generated by the above machine will be $S$: for any $s\in S$, suppose $T(s)$ accepts $s$ in $n$ steps, then the above machine will print $s$ after input $(s,n)$. If $s\notin S$, then no possible input will make the above machine print $s$.
However, the Turing recognisable language $\varnothing$ cannot really be generated by a Turing machine that always halts.
If we become more flexible and consider languages generated by a Turing machine which is allowed to run forever, then we can modify the machines to fix this
Machine A': Turing machine to recognise the language $S = \{s \mid \exists x:T(x)=s\}$ where $T$ may not halt
Machine B': Turing machine which may not always halt that generates a language $S$ recognised by $T$
Therefore, in summary: