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.

We can fix your definition by observing that the following theorem holds:

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

You are close to reinventing the notion of many-one reduction, by the way.

  • $\begingroup$ 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$. $\endgroup$ – StefanH Feb 7 '17 at 15:54
  • 2
    $\begingroup$ 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\})$. $\endgroup$ – Andrej Bauer Feb 7 '17 at 15:56
  • 1
    $\begingroup$ The "specified output" is just toally irrelevant and can be completely ignored. Any machine which terminates can be modified to terminate with the specified argument. And any machine which may terminate with an unspecified argument can be modified to instead run forever whenever it would terminate with the unspecified argument. $\endgroup$ – Andrej Bauer Feb 7 '17 at 15:58
  • $\begingroup$ Yes, thats the right way to read it. I somehow understood "specified output" to mean an output "coming from some specified set", but it certainly just means one single value. $\endgroup$ – StefanH Feb 7 '17 at 15:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.