I take the definition from Computability and Complexity Theory by Steven Homer and Alan L. Selman, 2011.

In their book they said that the domain of a computably enumerable (c.e.) function (f) can be the range of another partial function (p). In particular, the partial function can be the universal Turing machine. The universal Turing machine takes a machine description and input word (e, x) and effectively maps the domain (S) of the c.e. function (f).

My question is : what is the range of the universal Turing machine - shouldn't it just accept or reject ? then how could it map the domain of the c.e. function (f)....


When you use Turing machines to compute functions, they typically write down the result on their tape and halt.

Note that recognising words from a language can be thought of as computing a function from $\Sigma^* \rightarrow \{0,1\}$, so you don't have to accept via declaring some state accepting.

How exactly your TM works depends on the definition you use and you have considerable freedom to use something that fits your problem domain. It's all about communicating with your readers.


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.