Analogue of Turing recognizable languages

Question

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?

Answer 1

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

• given an input $s$ (to check whether $s\in S$)
• for all possible input strings $x$:
  • simulate $T(x)$
  • if $T(x)=s$, then accept

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$

• take as input a string $s$ and a number $n$
• simulate $T(s)$
  • if $T(s)$ halts in $n$ steps and accepts, then print $s$
  • otherwise, print $s_0$

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

• given an input $s$
• for some enumeration of pairs $(x,n)$ where $x$ is a string and $n$ is a number
  • simulate $T(x)$ for $n$ steps
  • if $T(x)$ halts and outputs $s$, then accept

Machine B': Turing machine which may not always halt that generates a language $S$ recognised by $T$

• takes as input a string $s$
• simulate $T(s)$
  • if $T(s)$ eventually halts and accepts, print $s$
  • if $T(s)$ halts and rejects, loop forever

Therefore, in summary:

Nonempty Turing recognisable languages are equivalently sets of outputs generated by some Turing machine that always halts

Turing recognisable languages are equivalently sets of outputs generated by some Turing machine that may not halt at every input