# 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$?

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$ ?

• In the first definition shouldn't the first "is" be "if"? From where did you take these definitions? (Book, lecture notes, web-site...) – fade2black Oct 17 '17 at 8:05
• I do not understand your question. You are given a total function $f$ and a decidable language $L$. Are you looking for a TM $M$ which both computes $f$ and decides $f$? They are two different problems. $f$ is computable and so there is a TM $M_1$ which computes $f$ and $L$ is decidable and so there is a TM $M_2$ that decides $L$. So, what do you confuse? – fade2black Oct 17 '17 at 8:14
• Yes, I want to know whether there is a TM $M$ which computes $f$ and decides $L$ at the same time. – TeamBright Oct 17 '17 at 8:18
• For suitable definitions of "decides L", there is no reason why the TM couldn't compute $f$ as well. – adrianN Oct 17 '17 at 8:22
• For suitable definitions of "computes $f$" and I change the $q_{accept}$ and $q_{reject}$. That is my original thought but I failed. – TeamBright Oct 17 '17 at 8:35

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)