1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In the first definition shouldn't the first "is" be "if"? From where did you take these definitions? (Book, lecture notes, web-site...) $\endgroup$ – fade2black Oct 17 '17 at 8:05
  • $\begingroup$ 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? $\endgroup$ – fade2black Oct 17 '17 at 8:14
  • $\begingroup$ Yes, I want to know whether there is a TM $M$ which computes $f$ and decides $L$ at the same time. $\endgroup$ – TeamBright Oct 17 '17 at 8:18
  • $\begingroup$ For suitable definitions of "decides L", there is no reason why the TM couldn't compute $f$ as well. $\endgroup$ – adrianN Oct 17 '17 at 8:22
  • $\begingroup$ For suitable definitions of "computes $f$" and I change the $q_{accept}$ and $q_{reject}$. That is my original thought but I failed. $\endgroup$ – TeamBright Oct 17 '17 at 8:35
3
$\begingroup$

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)
$\endgroup$

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.