Given a computable function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$?

Question

1) (cited from "Introduction to the Theory of Computation" by Michael Sipser)

Let $M$ be a Turing machine, we say that $M$ decides a language $L$ if $M$ is a decider which recognizes $L$.

2) (cited from "Computational complexity: a modern approach" by Boaz Barak and Sanjeev Arora)

Let $f \colon \Sigma^{∗} \rightarrow \Sigma^{∗}$ and let $T \colon \mathbb{N} \rightarrow \mathbb{N}$ be some functions, and let $M$ be a Turing machine. We say that $M$ computes $f$ if for every $x \in \Sigma^{∗}$, whenever $M$ is initialized to the start configuration on input $x$, then it halts with $f (x)$ written on its output tape.

I think these two definitions shows two different functions of TMs, and it seems that there is not conflict between them.

So, given a computable total function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$ ?

Answer 1

Yes it clearly exists; informally you can build such $M$ in this way:

• $M$ makes a copy of its input $x$
• then without touching such a copy, $M$ decides if $x$ is in $L$ (possibly "destroying" the working copy of $x$),
• if $x \in L$ it enters a "subprogram" (set of states) in which all states are accepting and such subprogram uses the copy of $x$ to compute $f(x)$ (leaving the result in the output tape and ending in an accepting state)
• if $x \notin L$ it enters a "subprogram" (set of states) in which all states are NON accepting and such subprogram uses the copy of $x$ to compute $f(x)$ (leaving the result in the output tape and ending in a NON accepting state)