# A new definition of recursively enumerable set?

Given a Turing machine $M$, we associate a partial function $f_M : \Sigma^{\ast} \to \Sigma^{\ast}$ to it (this is called the function computed by the machine), where $\Sigma$ denotes the finite input and output alphabet, defined as $$f(u) = v :\Leftrightarrow \mbox{The machine halts on input u with output v}.$$ Then we say an arbitrary partial function $f : \Sigma^{\ast} \to \Sigma^{\ast}$ is called computable iff $f = f_M$ for some Turing machine $M$.

Then we define a language $A \subseteq \Sigma^{\ast}$ to be recursively enumerable iff it is the domain of some computable function. Clearly with the above definition $\operatorname{dom}(f_M) = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts on input$w$.} \}$, i.e. this is equivalent to say that a language is recursively enumerable iff we can find a machine that halts exactly for the words in the language.

But on other sources I found the following definition, a language $A \subseteq \Sigma^{\ast}$ is recursively enumerable, iff there exists a Turing machine such that $$A = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts in an accepting state} \}$$ or $$A = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts and outputs a specified output } \}.$$ Both notions, by special state or special output, are clearly equivalent. But they do not require the machine to run forever if $w \notin A$. This could be fixed, by letting the machine enter an endless loop if it enters a non-accepting state after finishing its computation. But this seems quite unnatural to me.

But I think a better definition, more closely at the definition by acceptance states or special output, in terms of computable functions, would be to call a language $A$ recursively enumerable iff there exists a computable partial function $f : \Sigma^{\ast} \to \Sigma^{\ast}$ such that $A = f^{-1}(B)$ for some $B \subseteq \Sigma^{\ast}$.

Surely with the above definition we can enlarge $B$ always by values not in the range of $f$, so $B$ is not unique, but it would be no problem that the machine halts on some other input $\notin B$ and we would have $A \subseteq \operatorname{dom}(f)$.

So is this definition used anywhere, does it make sense? I could not find it, so I am asking here. Also nobody discusses the two definitions together, either in books they always work with Turing machines, or they work with primitive and $\mu$-recursive functions.

Your definition makes no sense because according to it every language is recursively enumerable. Given any $C \subseteq \Sigma^*$, take $B = C$ and $f(x) = x$, the identity function, which is computable. Then $f^{-1}(C) = C$, therefore $C$ is recursively enumerable.
Theorem: A language $A$ is recursively enumerable if, and only if, there is a partial computable $f$ and a recursive set $B$ such that $A = f^{-1}(B)$.
• Thanks for your answer. If I see it right by the same argument the definition $$A = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts and outputs a specified output}\}$$ is wrong, as the specified output corresponds to the set $B$. – StefanH Feb 7 '17 at 15:54
• No, that definition is correct. It corresponds to the case where $B$ is a singleton (the specified output). We have the theorem: $A$ is r. e. if, and only if, there is a partical computable $f$ and a number $n$ (the specified output) such that $A = f^{-1}(\{n\})$. – Andrej Bauer Feb 7 '17 at 15:56